Ring-LWE i kraty modułowe

Standardowy LWE wymaga mnożenia dużych macierzy przez wektory, co prowadzi do dużych rozmiarów kluczy. Ring-LWE, wprowadzony przez Lyubashevsky'ego, Peikerta i Regeva w 2010 roku, zastępuje wektory i macierze wielomianami w pierścieniu R_q = Z_q[X]/(f(X)). Takie uporządkowane środowisko umożliwia tworzenie znacznie mniejszych kluczy i wykonywanie szybszych operacji arytmetycznych, dzięki czemu Ring-LWE stanowi praktyczną podstawę współczesnej kryptografii opartej na kratach.

Wielomian f(X) stosowany w Ring-LWE ma zazwyczaj postać f(X) = X^n + 1, gdzie n jest potęgą liczby 2. Jest to wielomian cyklotomiczny o indeksie 2n. Wybiera się go, ponieważ jest nierozkładalny nad Z, zapewnia dobre właściwości algebraiczne pierścienia R_q oraz umożliwia zastosowanie transformaty teoretyczno-liczbowej (NTT) do wydajnego mnożenia. Pierścienie cyklotomiczne zostały gruntownie zbadane i uważa się je za bezpieczne.

W Ring-LWE sekret s jest wielomianem w R_q, a próbki mają postać (a, b = a*s + e), gdzie a jest jednostajnie losowanym elementem pierścienia, a e jest małym wielomianem błędu. Przeciwnik obserwuje wiele takich próbek i musi odzyskać s albo odróżnić je od rozkładu jednostajnego. Trudność opiera się na założeniu Ring-LWE, dla którego istnieje redukcja z problemów najgorszego przypadku na kratach idealnych.

Ring-LWE jest trudniejszy dla przeciwnika, ale wiąże się również z nieco inną redukcją bezpieczeństwa niż zwykły LWE. Redukcja prowadzi od problemów najgorszego przypadku na kratach idealnych (ideal-SVP), a nie od dowolnych krat. Dodatkowa struktura krat idealnych mogłaby w zasadzie sprawić, że będą łatwiejsze do zaatakowania niż kraty ogólne, dlatego jest to aktywny obszar badań. Nie jest znany żaden praktyczny atak wykorzystujący tę strukturę.

Module-LWE (M-LWE) uogólnia zarówno LWE, jak i Ring-LWE, operując na macierzy k x k elementów pierścienia zamiast na pojedynczym elemencie pierścienia lub dużej macierzy liczb całkowitych. Gdy k = 1, sprowadza się do Ring-LWE, a wraz ze wzrostem k zbliża się do standardowego LWE. Regulowany parametr k pozwala równoważyć zaufanie do bezpieczeństwa i wydajność.

CRYSTALS-Kyber (obecnie ML-KEM, FIPS 203) opiera się na Module-LWE z macierzą rangi k nad R_q. Parametr k bezpośrednio określa poziom bezpieczeństwa: k=2 odpowiada 128-bitowemu poziomowi bezpieczeństwa (ML-KEM-512), k=3 — 192-bitowemu (ML-KEM-768), a k=4 — 256-bitowemu (ML-KEM-1024). Struktura modułowa pozwala korzystać z jednej bazy kodu i skalować bezpieczeństwo przez zmianę k.

Mnożenie wielomianów w R_q = Z_q[X]/(X^n + 1) jest wąskim gardłem wydajności. Transformata teoretyczno-liczbowa (NTT) jest dyskretną transformatą Fouriera nad Z_q, która przekształca wielomiany do postaci ewaluacyjnej, w której mnożenie staje się operacją punktową. Gdy q jest dobrane tak, aby można było zastosować NTT, mnożenie wielomianów zajmuje O(n log n) zamiast O(n^2), co stanowi kluczową optymalizację w ML-KEM i ML-DSA.

Transformata NTT wymaga, aby q było liczbą pierwszą spełniającą q = 1 mod 2n, co zapewnia, że Z_q zawiera pierwotny 2n-ty pierwiastek z jedności. Dla ML-KEM z n = 256 liczba q = 3329 spełnia ten warunek. Transformata NTT nad Z_3329 działa niezwykle szybko na nowoczesnym sprzęcie wykorzystującym instrukcje SIMD, umożliwiając wykonywanie tysięcy operacji ML-KEM na sekundę na standardowych procesorach.

Ring-LWE i Module-LWE znacznie zmniejszają rozmiary kluczy w porównaniu ze standardowym LWE. Klucz publiczny standardowego LWE zapewniający 128-bitowe bezpieczeństwo może mieć rozmiar 1 MB; Ring-LWE zmniejsza go do około 800 bajtów, a Module-LWE (ML-KEM-768) zapewnia klucz publiczny o rozmiarze 1184 bajtów i 192-bitowe bezpieczeństwo postkwantowe. Ta kompaktowość sprawia, że schematy kratowe są praktyczne w protokole TLS i systemach wbudowanych.

Niektórzy kryptografowie obawiają się, że dodatkowa struktura algebraiczna pierścieni cyklotomicznych może umożliwiać ataki, które nie mają zastosowania do zwykłego LWE. W 2024 roku Elias Rokicki i jego współpracownicy opublikowali analizę 2n-tego wielomianu cyklotomicznego. Nie znaleźli praktycznych sposobów jego wykorzystania, ale podkreślili znaczenie dalszej weryfikacji. Proces NIST PQC uwzględnił to ryzyko i częściowo z tego powodu wybrano Module-LWE, aby zmniejszyć zależność od jednej konkretnej struktury pierścieniowej.

Oprócz Kybera Ring-LWE stanowi podstawę CRYSTALS-Dilithium (ML-DSA), standaryzowanego przez NIST schematu podpisu. Biblioteka SEAL firmy Microsoft umożliwia szyfrowanie homomorficzne za pomocą Ring-LWE. Biblioteka kryptograficzna Tink firmy Google obsługuje ML-KEM. Ring-LWE przeszedł od konstrukcji teoretycznej do wdrożeń produkcyjnych w niezwykle krótkim czasie, napędzany procesem standaryzacji NIST.

Ring-LWE przenosi LWE do pierścienia wielomianów R_q = Z_q[X]/(X^n+1), znacznie zmniejszając rozmiary kluczy i umożliwiając szybkie operacje arytmetyczne oparte na transformacie NTT. Module-LWE uogólnia tę konstrukcję za pomocą struktury rangi k i stanowi podstawę ML-KEM (FIPS 203) oraz ML-DSA (FIPS 204). Przyjazna dla NTT liczba pierwsza q = 3329 umożliwia wydajną implementację. Bezpieczeństwo opiera się na trudności problemów dotyczących krat idealnych i modułowych.