Schematy BGV i BFV do operacji na liczbach całkowitych

BGV (Brakerski-Gentry-Vaikuntanathan, 2012) to schemat FHE o warstwach, oparty na RLWE. Obsługuje dowolne dodawanie i mnożenie spakowanych tekstów jawnych zawierających liczby całkowite. Termin „o warstwach” oznacza, że schemat obsługuje obwody o głębokości do ustalonej wartości L bez bootstrappingu.

BGV i BFV kodują teksty jawne jako wielomiany w Z_t[x]/(x^n+1), gdzie t jest małym modułem tekstu jawnego (np. t=65537). Każdy wielomian koduje n wartości całkowitych (po jednej na współczynnik). Arytmetyka na szyfrogramach działa jednocześnie na wszystkich n wartościach — równoległość SIMD.

BGV zmniejsza szum przez przełączanie modułu: po każdym mnożeniu moduł szyfrogramu q jest zmniejszany z Q_L do Q_{L-1}. Dzieli to szum przez Q_L/Q_{L-1}, utrzymując go w zakresie umożliwiającym odszyfrowanie. Głębokość obwodu L odpowiada L poziomom modułu.

BFV (Brakerski/Fan-Vercauteren, 2012) jest podobny do BGV, ale wykorzystuje inną strategię zarządzania szumem: niezmienność skali. BFV nie wymaga przełączania modułu; zamiast tego po mnożeniu ponownie skaluje szyfrogram. Jest prostszy w implementacji i jest używany w Microsoft SEAL.

Dzięki chińskiemu twierdzeniu o resztach zastosowanemu do pierścienia tekstu jawnego każdy szyfrogram może zawierać n/2 niezależnych wartości całkowitych (slotów). Operacja dodawania szyfrogramów dodaje równolegle wszystkie n/2 par. Mnożenie mnoży wszystkie pary. Przepustowość: n/2 operacji na liczbach całkowitych na operację szyfrogramu.

Po pomnożeniu dwóch szyfrogramów stopnia 1 wynik ma stopień 2 (3 składowe). Relinearyzacja wykorzystuje klucze ewaluacyjne (klucze relin), aby przywrócić stopień 1 kosztem dodatkowego szumu. Ten krok jest wymagany po każdym mnożeniu.

from seal import EncryptionParameters, scheme_type, SEALContext, KeyGenerator, Encryptor, Evaluator, Decryptor parms = EncryptionParameters(scheme_type.bfv) parms.set_poly_modulus_degree(4096) parms.set_coeff_modulus(CoeffModulus.BFVDefault(4096)) parms.set_plain_modulus(PlainModulus.Batching(4096, 20))

Rotacja szyfrogramu cyklicznie przesuwa n/2 slotów tekstu jawnego. Jest przydatna do: redukcji sumy (gromadzenia wszystkich slotów w jednym), mnożenia macierzy przez wektor (rotacji i akumulacji), splotów (przesuwania i mnożenia). Wymaga kluczy Galois (wstępnie obliczonych kluczy rotacji).

BFV z n=8192: dodawanie ~10 µs, mnożenie ~5 ms (z relinearizacją). Bootstrapping (jeśli jest potrzebny): 30–60 sekund. Pakiet 4096 liczb całkowitych: średnio ~1 µs na liczbę całkowitą na mnożenie. Rozwiązanie niepraktyczne w czasie rzeczywistym, ale przydatne w analityce offline.

Przy wyborze n i q: SEAL zaleca n=4096 dla 128-bitowego poziomu bezpieczeństwa przy Q < 2^109; n=8192 dla większych obwodów. Standard HE (homomorphicencryption.org) udostępnia tabele parametrów. Należy zawsze używać zalecanych parametrów — niestandardowy wybór łatwo może osłabić bezpieczeństwo.

Zaszyfrowane zapytania do baz danych (wyszukiwanie zaszyfrowanych rekordów bez ich odszyfrowywania). Prywatna analiza genomu (obliczanie statystyk na zaszyfrowanym DNA). Zaszyfrowane agregacje finansowe (sumowanie zaszyfrowanych sald kont bez dostępu do informacji o poszczególnych osobach). Bezpieczna ewaluacja modeli.

Jaką technikę BGV wykorzystuje do zarządzania wzrostem szumu po mnożeniach?

BGV i BFV wykonują zaszyfrowaną arytmetykę na liczbach całkowitych z użyciem RLWE. Kodowanie pakietowe zapewnia równoległość SIMD. BGV wykorzystuje przełączanie modułu, a BFV — niezmienność skali. Relinearyzacja przywraca stopień po mnożeniu. Dalej: CKKS do arytmetyki przybliżonej i uczenia maszynowego.