Podstawa Learning With Errors (LWE)

Learning With Errors (LWE) autorstwa Regeva (2005): mając wiele zaszumionych równań liniowych nad Z_q, należy znaleźć tajny wektor s. Szum e jest niewielki, ale uniemożliwia eliminację Gaussa. Bez szumu układ jest łatwy do rozwiązania; nawet przy minimalnym szumie staje się obliczeniowo trudny.

Tajny wektor s ∈ Z_q^n. Przeciwnik otrzymuje próbki (a_i, b_i), gdzie a_i ∈ Z_q^n jest losowe, a b_i = + e_i mod q, przy czym e_i jest niewielkim szumem z rozkładu χ (np. rozkładu Gaussa z σ = √n). Zadanie: znaleźć s na podstawie wielomianowej liczby próbek.

Bez szumu: b_i = mod q. Eliminacja Gaussa odzyskuje s w czasie O(n^3). Z szumem: nawet jedno błędne równanie zaburza eliminację. Szum jest wystarczająco mały, aby odszyfrowanie działało przy użyciu klucza, ale wystarczająco duży, aby uniemożliwić kryptoanalizę.

Regev udowodnił, że LWE redukuje się do problemów kratowych w najgorszym przypadku (SIVP, GapSVP) za pomocą redukcji kwantowej. Oznacza to, że jeśli LWE zostanie złamane, rozwiązanych zostanie wiele trudnych problemów kratowych — jednak nie jest znany żaden algorytm kwantowy dla problemów kratowych. LWE jest bezpieczne postkwantowo.

RLWE zastępuje Z_q^n pierścieniem Z_q[x]/(f(x)) dla wielomianu cyklotomicznego f. Jedna próbka RLWE koduje n równań, co zapewnia znacznie większą wydajność. RLWE stanowi podstawę Kyber (KEM), Dilithium (podpis) oraz schematów HE BFV/BGV/CKKS.

Bezpieczeństwo zależy od: n (wymiar, zazwyczaj 512–2048), q (moduł, 1024–2^60), σ (odchylenie standardowe szumu). Większe n oraz mniejszy stosunek σ/q oznaczają większą trudność. Standardy postkwantowe NIST wykorzystują n=256 (wymiar modułu) oraz k modułów (k=2,3,4).

Klucz publiczny: (A, b=As+e). Szyfrowanie bitu m: wybierz losowe r i oblicz szyfrogram (u=A^T r, v = b^T r + m*q/2). Odszyfrowanie: v - s^T u = e^T r + m*q/2 ≈ m*q/2. Zaokrąglij do najbliższej wartości m. Szum e sprawia, że szyfrogram ukrywa m podczas szyfrowania.

Decyzyjne LWE: rozróżnienie (a, As+e) od (a, u), gdzie u jest jednostajnie losowe. Przy założeniu trudności LWE rozkłady te są obliczeniowo nierozróżnialne. Stanowi to podstawę bezpieczeństwa semantycznego — dla przeciwników bez tajnego klucza szyfrogramy wyglądają jak losowy szum.

Najlepsze znane ataki wykorzystują redukcję krat BKZ (Block Korkine-Zolotarev). Złożoność jest podwykładnicza, ale nie wielomianowa. BKZ-β wymaga 2^{0.292β} operacji. Dla LWE-512 bezpieczeństwo wynosi około 128 bitów w przypadku ataku BKZ. Nie jest znane żadne przyspieszenie kwantowe dla BKZ.

Module-LWE (używane w Kyber) jest RLWE nad modułami o randze k. Zapewnia elastyczność: k=2 dla 512-bitowego poziomu bezpieczeństwa, k=3 dla 768-bitowego, k=4 dla 1024-bitowego. Bezpieczeństwo i wydajność skalują się wraz z k. NIST wybrał Kyber (przemianowany na ML-KEM) jako standard PQC.

Bezpieczeństwo RSA/ECC opiera się na faktoryzacji liczb całkowitych i logarytmie dyskretnym (podatnych na ataki kwantowe z użyciem algorytmu Shora). Bezpieczeństwo LWE opiera się na problemach kratowych w najgorszym przypadku (nie jest znane żadne przyspieszenie kwantowe). Rozmiary kluczy: klucze LWE mają około 1 KB, a RSA-2048 — 256 bajtów. LWE zajmuje więcej miejsca, ale jest bezpieczne w erze komputerów kwantowych.

Co sprawia, że rozwiązanie LWE jest trudne nawet przy dużej liczbie próbek?

LWE: znalezienie tajnego s na podstawie zaszumionych równań liniowych — problem trudny dla komputerów kwantowych. RLWE wykorzystuje pierścienie wielomianów w celu zwiększenia wydajności. Stanowi podstawę Kyber, Dilithium i schematów HE. Dalej: schematy HE BGV i BFV do operacji na liczbach całkowitych.