Learning With Errors: trudny problem

Problem Learning With Errors (LWE), czyli uczenia z błędami, został przedstawiony przez Odeda Regeva w 2005 roku jako podstawa kryptografii postkwantowej. Mając losową macierz A nad Z_q oraz wektor b = As + e, należy znaleźć tajny wektor s. Wektor e jest niewielkim błędem wylosowanym z dyskretnego rozkładu Gaussa, co sprawia, że problem jest obliczeniowo nierozwiązywalny.

W problemie LWE macierz losowa A o wymiarach m x n jest losowana równomiernie z Z_q, gdzie q jest modułem pierwszym. Sekret s jest wektorem n-wymiarowym, a e jest wektorem małego błędu, którego współczynniki są losowane z wąskiego rozkładu Gaussa. Nawet znajomość struktury A nie pomaga przeciwnikowi odróżnić b od wektora losowego o rozkładzie jednostajnym.

Istnieją dwa standardowe sformułowania problemu LWE. Problem wyszukiwania LWE polega na odzyskaniu sekretu s na podstawie wielu próbek (A, b). Problem decyzyjny LWE polega na odróżnieniu próbek (A, As + e) od jednostajnie losowych par (A, u). Oba sformułowania są równoważne w czasie wielomianowym, co oznacza, że algorytm rozwiązujący jedno z nich można przekształcić tak, aby rozwiązywał również drugie.

Wyraz błędu w LWE jest losowany z dyskretnego rozkładu Gaussa na liczbach całkowitych, parametryzowanego odchyleniem standardowym sigma. Niewielkie wartości sigma sprawiają, że e jest mały w porównaniu z q, dzięki czemu b wygląda niemal jak As mod q. Gdyby sigma wynosiło zero, nie byłoby błędu i układ można byłoby rozwiązać za pomocą eliminacji Gaussa, dlatego błąd jest niezbędny dla trudności problemu.

Regev udowodnił niezwykłą redukcję: rozwiązywanie próbek LWE z przypadku średniego jest co najmniej tak trudne jak rozwiązywanie instancji problemu najkrótszego wektora (SVP) w kratach dla przypadku najgorszego. Oznacza to, że skuteczne złamanie LWE pozwoliłoby skutecznie rozwiązać dowolny problem kratowy. Nie jest znany żaden klasyczny ani kwantowy algorytm rozwiązujący problem SVP dla przypadku najgorszego w czasie wielomianowym.

W przeciwieństwie do RSA i kryptografii krzywych eliptycznych żaden znany algorytm kwantowy nie zapewnia wykładniczego przyspieszenia w ataku na LWE. Algorytm Grovera oferuje co najwyżej kwadratowe przyspieszenie, a najlepsze kwantowe algorytmy kratowe, czyli warianty BKZ, nie łamią LWE przy właściwie dobranych parametrach. Dzięki temu LWE stanowi solidną podstawę bezpieczeństwa postkwantowego.

O bezpieczeństwie LWE decydują trzy parametry: wymiar n (długość sekretu), moduł q oraz odchylenie standardowe błędu sigma. Większe n i mniejszy stosunek q/sigma zwiększają bezpieczeństwo. Dla 128-bitowego bezpieczeństwa postkwantowego typowe wartości to n = 1024, q równe około 12289 oraz sigma równe około 3.2. Narzędzie lattice estimator autorstwa Albrechta i współpracowników służy do oceny bezpieczeństwa dla konkretnych parametrów.

Problem SIS (Short Integer Solution) jest powiązanym założeniem trudności stosowanym w podpisach. Dla losowej macierzy A nad Z_q należy znaleźć krótki, niezerowy wektor x taki, że Ax = 0 mod q. SIS stanowi podstawę funkcji skrótu i schematów podpisu w kryptografii kratowej, uzupełniając LWE, na którym opierają się szyfrowanie i mechanizmy enkapsulacji klucza.

Prosty schemat szyfrowania LWE działa następująco: klucz publiczny to (A, b = As + e), a klucz prywatny to s. Aby zaszyfrować bit m, nadawca oblicza (u, v) = (A^T r, b^T r + m * floor(q/2)) dla losowego wektora binarnego r. Deszyfrowanie polega na obliczeniu v - s^T u i zaokrągleniu wyniku w celu odzyskania m. Schemat ten zapewnia bezpieczeństwo IND-CPA przy założeniu trudności LWE.

LWE umożliwiło stworzenie szerokiego zakresu konstrukcji kryptograficznych wykraczających poza podstawowe szyfrowanie. Należą do nich w pełni homomorficzne szyfrowanie (FHE), szyfrowanie oparte na tożsamości (IBE), szyfrowanie oparte na atrybutach (ABE) oraz protokoły wymiany kluczy. CRYSTALS-Kyber (obecnie ML-KEM, standaryzowany jako FIPS 203) jest obecnie najpowszechniej wdrażanym schematem opartym na LWE.

Kryptografia oparta na LWE trafia już do systemów produkcyjnych. Google i Cloudflare przeprowadziły w latach 2018–2020 eksperymenty z TLS z użyciem Kyber. W 2024 roku Chrome i Firefox dodały obsługę ML-KEM-768 w hybrydowych uzgodnieniach TLS. Signal Protocol dodał warstwę postkwantową (PQXDH) wykorzystującą ML-KEM-1024 do zapewnienia forward secrecy, chroniąc długoterminową poufność wiadomości przed przyszłymi komputerami kwantowymi.

Które stwierdzenie najlepiej opisuje gwarancję trudności problemu LWE?

LWE jest jednym z najlepiej zbadanych postkwantowych założeń trudności, wspartym silną redukcją od problemów kratowych dla przypadku najgorszego. Jego trzy parametry (n, q, sigma) określają kompromis między bezpieczeństwem a wydajnością. LWE jest odporne na ataki kwantowe i stanowi podstawę schematów standaryzowanych przez NIST. Zrozumienie LWE otwiera drogę do całej współczesnej kryptografii opartej na kratach, w tym ML-KEM i ML-DSA.