Czym jest szyfrowanie homomorficzne?

Szyfrowanie homomorficzne (HE) umożliwia wykonywanie obliczeń bezpośrednio na zaszyfrowanych danych, tworząc zaszyfrowany wynik, który po odszyfrowaniu jest równy wynikowi tych samych operacji wykonanych na tekście jawnym. „Obliczanie na szyfrogramie bez odszyfrowywania”.

Wyobraźmy sobie umieszczenie liczb w zamkniętej skrzynce, której boki mają wbudowane specjalne rękawice. Mogą Państwo manipulować liczbami przez rękawice (dodawać i mnożyć), nigdy nie otwierając skrzynki. Tylko właściciel klucza może zobaczyć wynik po odblokowaniu skrzynki.

Częściowe szyfrowanie homomorficzne obsługuje bez ograniczeń jeden typ operacji: RSA (w wersji podręcznikowej) jest homomorficzne multiplikatywnie: Enc(m1)*Enc(m2) = Enc(m1*m2). Paillier jest homomorficzne addytywnie: Enc(m1)*Enc(m2) = Enc(m1+m2). Stosowane w głosowaniu elektronicznym i prywatnym wyszukiwaniu informacji.

Częściowo homomorficzne szyfrowanie obsługuje zarówno dodawanie, jak i mnożenie, ale tylko przez ograniczoną liczbę mnożeń (głębokość obwodu). Szum narasta przy każdym mnożeniu; po przekroczeniu progu odszyfrowanie kończy się niepowodzeniem. Pierwszą konstrukcję przedstawił Gentry (2009).

W pełni homomorficzne szyfrowanie obsługuje dowolne obliczenia (dowolny obwód boolowski lub arytmetyczny) na zaszyfrowanych danych. Gentry (2009) wykazał, że FHE jest możliwe dzięki „bootstrappingowi” — homomorficznemu obliczaniu obwodu odszyfrowywania w celu odświeżenia szyfrogramu i wyzerowania szumu.

Większość schematów HE jest oparta na kratach (BGV, BFV, CKKS). Szyfrowanie dodaje szum do szyfrogramu. Dodawanie: szum rośnie addytywnie. Mnożenie: szum rośnie multiplikatywnie. Bootstrapping: homomorficzne odszyfrowanie szyfrogramu, które przywraca szum do poziomu początkowego. Bootstrapping jest kosztowny.

FHE jest nadal 10^6 razy wolniejsze od obliczeń na tekście jawnym. Zaszyfrowanie jednej 32-bitowej liczby całkowitej wymaga kilobajtów szyfrogramu. Bootstrapping trwa kilka sekund na bramkę. Praktyczne zastosowania FHE dotyczą konkretnych obciążeń: wnioskowania modeli uczenia maszynowego, zapytań do baz danych i analizy genomu.

Większość schematów HE opiera się na trudnym problemie Learning With Errors (LWE) lub Ring-LWE (RLWE), który uważa się za odporny na ataki kwantowe. Złamanie HE wymaga rozwiązania RLWE — nie jest znany żaden algorytm kwantowy zapewniający istotne przyspieszenie dla tego problemu.

SEAL (Microsoft, obsługuje BFV/CKKS), HEAAN (Seoul National University, CKKS), OpenFHE (open source, BGV/BFV/CKKS/FHEW/TFHE), HElib (IBM, BGV). Wszystkie są bibliotekami klasy badawczej; wdrożenia produkcyjne są rzadkie i specyficzne dla danej dziedziny.

Medyczna genomika: odpytywanie bazy genów bez ujawniania własnego genomu. Zaszyfrowane wnioskowanie ML: chmura uruchamia sieć neuronową na danych bez uzyskiwania do nich dostępu. Prywatna analityka: agregowanie statystyk na zaszyfrowanych danych użytkowników. Obliczanie ryzyka finansowego na podstawie poufnych portfeli.

HE: jedna strona wykonuje obliczenia na danych zaszyfrowanych przez inną stronę. MPC: wiele stron wspólnie wykonuje obliczenia, nie ujawniając sobie nawzajem danych wejściowych. Podejście hybrydowe: HE do wstępnego przetwarzania offline, MPC do protokołów interaktywnych. Kompromisy: HE = wysokie opóźnienia; MPC = narzut komunikacyjny.

Jakie jest najważniejsze ograniczenie Somewhat Homomorphic Encryption (SHE)?

Szyfrowanie homomorficzne umożliwia wykonywanie obliczeń na szyfrogramie. PHE obsługuje jedną operację; SHE obsługuje ograniczoną głębokość; FHE obsługuje dowolne obwody dzięki bootstrappingowi. Opiera się na trudnych problemach LWE/RLWE. Dalej: matematyczne podstawy LWE.