W pełni homomorficzne szyfrowanie: technologia obliczająca na tajnych danych

Craig Gentry udowodnił, że jest to możliwe w 2009 roku, po mniej więcej trzech dekadach zastanawiania się kryptografów, czy w ogóle może istnieć. Idea jest następująca: szyfrujesz swoje dane, przekazujesz je komuś innemu, ta osoba wykonuje na nich obliczenia, zwraca wynik, a gdy go odszyfrujesz, jest on poprawny. Osoba wykonująca obliczenia nigdy nie widziała Twoich danych. Nie okrojonej wersji. Nie skrótu. Rzeczywistych wartości źródłowych, nigdy nieujawnionych, nawet przez mikrosekundę. To właśnie jest w pełni homomorficzne szyfrowanie — forma szyfrowania, która pozwala stronie trzeciej wykonywać obliczenia na Twoich danych bez ich odszyfrowywania.

Czym więc jest FHE (w pełni homomorficzne szyfrowanie)? To nie jest sztuczka. To właściwość matematyczna pewnych schematów szyfrowania. Wysyłasz komuś zamkniętą skrzynkę. Przestawia jej zawartość. Otwierasz ją, a układ jest poprawny. Ta osoba nigdy nie miała klucza.

Dlaczego alternatywy nie wystarczają

Zanim przejdziemy do tego, jak działa FHE, warto dokładnie określić problem, który rozwiązuje, ponieważ większość podejść do „obliczeń na wrażliwych danych" wiąże się z kompromisem, który ludzie nauczyli się akceptować bez kwestionowania.

Standardowe podejście: szyfruj dane w spoczynku i podczas przesyłania, odszyfrowuj przed przetworzeniem. Twój dostawca chmury, dostawca analityki, usługa ML — wszyscy potrzebują tekstu jawnego, aby wykonać swoją pracę. Z konieczności obdarzasz ich zaufaniem. Działa to do pewnego momentu: naruszenie bezpieczeństwa, nakaz sądowy, zagrożenie wewnętrzne, błędnie skonfigurowana polityka dostępu.

Zaufane środowiska wykonawcze (TEE), takie jak Intel SGX, tworzą chroniony obszar pamięci, którego nie może odczytać nawet system operacyjny. Wrażliwe obliczenia odbywają się wewnątrz enklawy. Jest to naprawdę użyteczne, ale polegasz na dostawcy sprzętu i zakładasz, że implementacja enklawy nie ma żadnych możliwych do wykorzystania luk. SGX miał ich kilka.

Prywatność różnicowa dodaje skalibrowany szum statystyczny do wyników zapytań, co ogranicza możliwość wnioskowania przez atakującego o osobach na podstawie zagregowanych wyników. Chroni agregacje, a nie obliczenia na poszczególnych rekordach.

FHE to jedyne podejście, w którym dane nie są nigdy odszyfrowywane na serwerze, a dowód bezpieczeństwa nie wymaga zaufania do żadnego sprzętu ani strony trzeciej. Gwarancja jest matematyczna.

Mechanika w skrócie

Schematy FHE definiują operacje arytmetyczne bezpośrednio na szyfrogramach. Homomorficzne dodawanie i homomorficzne mnożenie zaszyfrowanych wartości dają po odszyfrowaniu taki sam wynik, jak wykonanie tych operacji na odpowiadających im tekstach jawnych.

Dwie operacje brzmią ograniczająco. Tak nie jest. Dodawanie i mnożenie w ciałach binarnych dają bramki AND i XOR, które dają dowolne układy cyfrowe. Każdą funkcję, którą może obliczyć komputer, można wyrazić za pomocą tych dwóch operacji. To pomost między „arytmetyką na zaszyfrowanych liczbach" a „dowolnymi obliczeniami na zaszyfrowanych danych".

Strukturalnym problemem jest szum. Każda operacja FHE wprowadza do szyfrogramu mały błąd. Błędy kumulują się. Przeprowadzenie wystarczającej liczby operacji sprawia, że szum przytłacza sygnał — szyfrogram staje się niemożliwy do odszyfrowania. Spostrzeżeniem Gentry'ego było bootstrapping: homomorficzne ewaluowanie obwodu deszyfrowania na zaszumionym szyfrogramie w celu uzyskania świeżego, niskoszumowego szyfrogramu z tą samą wartością tekstu jawnego. Innymi słowy, uruchamiasz deszyfrowanie wewnątrz szyfrowania. Szum resetuje się bez ujawniania danych.

Schematy obsługujące ograniczoną liczbę operacji, zanim szum stanie się krytyczny, nazywane są poziomowymi lub częściowo homomorficznymi. Bootstrapping jest tym, co nadaje „w pełni" w FHE.

Gdzie jest wdrażane obecnie

W przypadku większości zastosowań FHE jest nadal zbyt wolne. Aplikacje działające obecnie mają wspólny profil: ograniczona głębokość obwodu, wysoka wrażliwość danych i strona, która może pokryć koszty obliczeniowe w zamian za matematyczną gwarancję prywatności.

Prywatna inferencja ML to najlepsze dopasowanie. Klient ma wrażliwe dane wejściowe. Serwer ma zastrzeżony model. FHE pozwala serwerowi ewaluować model na zaszyfrowanych danych wejściowych i zwracać zaszyfrowany wynik. Żadna ze stron nie ujawnia tego, co chroni. Zama dostarcza to dla określonych architektur modeli. Głębokość obwodu jest przewidywalna i zarządzalna.

Prywatna analiza genomiczna była wzorcowym obciążeniem od czasu, gdy iDASH zaczął organizować zaszyfrowane konkursy genomiczne w 2014 roku. Ocena ryzyka chorób, badania asocjacyjne całego genomu i wyrównanie sekwencji mają wszystkie konstrukcje FHE. Dane genomiczne należą do nielicznych typów danych, w przypadku których ryzyko naruszenia prywatności jest zarówno trwałe, jak i dotyczy osób, które nigdy nie wyraziły zgody na udostępnienie czegokolwiek.

Poufne zapytania finansowe obejmują zapytania zakresowe, zaszyfrowane wyszukiwania w bazach danych i ocenę fraudów na zaszyfrowanych historiach transakcji. Te obciążenia są wykonywane na tyle rzadko, a dane są na tyle wrażliwe, że narzut obliczeniowy jest akceptowalny.

Poufność blockchain to aktywny obszar. Domyślnie inteligentne kontrakty są wykonywane publicznie w łańcuchu. Systemy oparte na TFHE pozwalają uruchamiać logikę kontraktu na zaszyfrowanym stanie, co umożliwia takie rzeczy jak prywatne aukcje, poufne głosowanie i mechanizmy zamkniętych ofert, w których poprawność jest publicznie weryfikowalna, ale dane wejściowe nie są ujawniane. Projekt fhEVM firmy Zama jest konkretnie nakierowany na ten cel.

Podstawy bezpieczeństwa

Bezpieczeństwo FHE sprowadza się do trudności problemu uczenia się z błędami (LWE) i jego wariantu pierścieniowego (RLWE). Problemy te pytają: mając wiele przybliżonych równań liniowych nad pierścieniem lub kratą, odtwórz sekret. Nie jest znany żaden algorytm wielomianowy dla żadnego z nich, ani na sprzęcie klasycznym, ani kwantowym.

Umieszcza to FHE w rodzinie kryptografii post-kwantowej. Standaryzacja post-kwantowa NIST jest zbudowana na problemach z rodziny LWE, co zapewnia podstawowym założeniom dodatkową kontrolę i pewność. Niemniej jednak LWE jest poddawany poważnym atakom od mniej niż 20 lat. RSA i krzywe eliptyczne mają za sobą ponad 40 lat nieudanej kryptoanalizy. Poziom zaufania jest wysoki, ale nie identyczny.

Parametry rządzą bezpieczeństwem. Stopień wielomianu, rozmiar modułu i rozkład szumu muszą być dobrane tak, aby instancja LWE była trudna na pożądanym poziomie bezpieczeństwa. Konsorcjum HomomorphicEncryption.org publikuje zalecane zestawy parametrów. Zdecydowanie preferowane jest używanie domyślnych ustawień biblioteki, które zostały zwalidowane zgodnie z tymi zaleceniami, zamiast niestandardowych konfiguracji.

Kontekst konkurencyjny

FHE jest jedną z kilku technologii obliczeniowych chroniących prywatność i coraz częściej są one używane razem, a nie jako substytuty.

Bezpieczne obliczenia wielostronne (MPC) rozdzielają obliczenia między wiele stron, z których żadna nie widzi pełnych danych wejściowych. Jest często szybsze niż FHE dla określonych funkcji i jest naturalnym wyborem, gdy strony są z góry zdefiniowane. FHE działa z pojedynczym niezaufanym serwerem.

Dowody zerowej wiedzy (ZKP) pozwalają jednej stronie udowodnić, że twierdzenie jest prawdziwe, bez ujawniania świadka. ZKP udowadniają; FHE oblicza. Są komplementarne, a rzeczywiste systemy używają obu: FHE do prywatnych obliczeń, ZKP do weryfikacji, że obliczenia zostały wykonane poprawnie.

Protokoły hybrydowe łączące FHE i MPC to aktywny obszar badań. Żadna z tych technologii samodzielnie nie spełnia wszystkich wymagań; ich połączenie może zapewnić lepszą wydajność i silniejsze gwarancje niż każda z nich niezależnie.