Dowody bezpieczeństwa i redukcje w schematach kratowych

Dowód bezpieczeństwa schematu kryptograficznego to formalny argument matematyczny pokazujący, że złamanie schematu prowadziłoby do rozwiązania pewnego bazowego trudnego problemu. Dowód nie gwarantuje absolutnego bezpieczeństwa; pokazuje, że dowolnego wydajnego przeciwnika atakującego schemat można przekształcić w wydajny algorytm rozwiązujący trudny problem. Jeśli trudny problem jest niewykonalny obliczeniowo, schemat jest bezpieczny.

Przełomowy dowód Regeva z 2005 roku pokazuje, że algorytm działający w czasie wielomianowym, który rozwiązuje decyzyjny problem LWE, może zostać wykorzystany do rozwiązania problemu GapSVP (Gap Shortest Vector Problem) w najgorszym przypadku na kratach n-wymiarowych. Redukcja ma charakter kwantowy: wykorzystuje kwantową procedurę próbkowania do przekształcenia algorytmu rozwiązującego LWE w algorytm rozwiązujący problem kratowy. Oznacza to, że LWE jest co najmniej tak trudny jak problemy kratowe w najgorszym przypadku w modelu obliczeń kwantowych.

Redukcja Regeva nie jest ścisła: czynniki wielomianowe występujące w redukcji oznaczają, że poziom bezpieczeństwa gwarantowany przez dowód jest nieco słabszy niż sugerują najlepsze znane ataki. Przy praktycznym doborze parametrów kryptografowie korzystają z bezpieczeństwa konkretnego wyznaczanego przez najlepsze znane ataki (za pomocą lattice estimator), a nie z teoretycznego ograniczenia wynikającego z redukcji, ponieważ redukcja jest zachowawcza.

Schemat szyfrowania oparty na LWE dowodzi się jako IND-CPA (nieodróżnialność w warunkach ataku z wybranym tekstem jawnym) za pomocą argumentu hybrydowego. Dowód pokazuje, że rozróżniacz IND-CPA implikuje rozróżniacz LWE. W pierwszej hybrydzie rzeczywisty szyfrogram zostaje zastąpiony jednostajnie losowym ciągiem; nieodróżnialność wynika z założenia LWE. Zapewnia to przejrzysty dowód bezpieczeństwa podstawowego szyfrowania kratowego.

Bezpieczeństwo IND-CPA nie wystarcza w przypadku mechanizmów enkapsulacji klucza używanych w TLS: wymagają one bezpieczeństwa IND-CCA2 (w warunkach ataku z wybranym szyfrogramem). Transformacja Fujisakiego-Okamoto (FO) przekształca dowolny schemat IND-CPA w mechanizm KEM IND-CCA2 w modelu losowej wyroczni (ROM). ML-KEM stosuje wariant transformacji FO do bazowego szyfrowania Module-LWE, zapewniając bezpieczeństwo CCA2 wymagane przy wdrożeniach produkcyjnych.

Model losowej wyroczni (ROM) traktuje funkcje skrótu jak prawdziwie losowe funkcje. Wiele dowodów bezpieczeństwa, w tym dowody dotyczące transformacji FO, wymaga modelu ROM. W praktyce funkcje skrótu, takie jak SHA-3, nie są prawdziwie losowymi wyroczniami, dlatego dowody w modelu ROM nie gwarantują bezpieczeństwa w modelu standardowym. Mimo to dowody w modelu ROM są powszechnie uznawane w społeczności kryptograficznej za mocne przesłanki bezpieczeństwa.

Dowód w modelu standardowym nie przyjmuje żadnej idealizacji dotyczącej funkcji skrótu i jest ściśle silniejszy od dowodu w modelu ROM. Większość praktycznych schematów kratowych korzysta z dowodów w modelu ROM, ponieważ dowody CCA2 w modelu standardowym dla KEM-ów opartych na kratach są znacznie bardziej złożone i prowadzą do gorszych parametrów konkretnych. NIST zaakceptował dowody oparte na ROM dla ML-KEM, uznając je za wystarczające dla docelowych poziomów bezpieczeństwa.

Dowód bezpieczeństwa ML-KEM przebiega w dwóch etapach. Najpierw wykazuje się, że bazowe szyfrowanie Module-LWE jest bezpieczne IND-CPA przy założeniu M-LWE. Następnie transformacja Fujisakiego-Okamoto (a konkretnie transformacje T i U stosowane w Kyberze) podnosi ten poziom do IND-CCA2 w kwantowym modelu losowej wyroczni (QROM), który uwzględnia przeciwników odpytujących losową wyrocznię w superpozycji.

Estymator krat autorstwa Albrechta, Playera i Scotta jest standardowym narzędziem do obliczania bezpieczeństwa konkretnego schematów opartych na LWE. Modeluje koszt najlepszych znanych ataków kratowych (BKZ z wykorzystaniem metod przeszukiwania lub enumeracji) i zwraca szacowane bezpieczeństwo w bitach dla danych parametrów (n, q, sigma). Narzędzie jest regularnie aktualizowane wraz z publikowaniem nowych algorytmów i modeli kosztu sprzętu.

Algorytm Block Korkine-Zolotarev (BKZ) jest najlepszym praktycznym algorytmem redukcji krat. BKZ z rozmiarem bloku beta znajduje krótkie wektory, a jego złożoność przy użyciu najlepszych algorytmów przeszukiwania wynosi w przybliżeniu 2^{0.292*beta} operacji bramkowych. Dla ML-KEM-768 szacowane bezpieczeństwo klasyczne wynosi około 180 bitów, a kwantowe około 164 bitów, czyli znacznie powyżej docelowych 192 bitów.

Asymptotyczne dowody bezpieczeństwa pokazują, że schemat jest bezpieczny dla dostatecznie dużych parametrów, ale nie określają, co w praktyce oznacza „dostatecznie duże”. Analiza bezpieczeństwa konkretnego wypełnia tę lukę, szacując rzeczywisty koszt najlepszego ataku dla wybranych parametrów. Standaryzacja postkwantowa w dużej mierze opiera się na analizie bezpieczeństwa konkretnego, a parametry dobiera się tak, aby schematy były odporne na ataki z użyciem przewidywanego sprzętu kwantowego w perspektywie 30 lat.

Jakiej transformacji używa się do podniesienia bezpieczeństwa kratowego szyfrowania IND-CPA do IND-CCA2 w ML-KEM?

Dowody bezpieczeństwa schematów kratowych redukują bezpieczeństwo schematu do trudności problemu LWE lub SVP. Redukcja Regeva gwarantuje, że LWE jest co najmniej tak trudny jak problemy kratowe w najgorszym przypadku. Transformacja Fujisakiego-Okamoto podnosi bezpieczeństwo z IND-CPA do IND-CCA2 w modelu ROM. Bezpieczeństwo konkretne ocenia się za pomocą estymatora krat, wykorzystując modele złożoności BKZ. Luki w ścisłości redukcji oznaczają, że praktyczne parametry opierają się raczej na szacunkach kosztu ataków niż wyłącznie na ograniczeniach wynikających z redukcji.