NTRU: historia, projekt i bezpieczeństwo

NTRU został wynaleziony przez Hoffsteina, Pipher i Silvermana w 1996 roku, dzięki czemu jest jednym z najstarszych systemów klucza publicznego odpornych na ataki kwantowe, które wciąż uznaje się za bezpieczne. W przeciwieństwie do RSA i ECC, których bezpieczeństwo opiera się na trudności problemów z teorii liczb, bezpieczeństwo NTRU wynika z trudności znalezienia krótkich wektorów w określonej kracie wyprowadzonej z pierścieni wielomianów. Przed upowszechnieniem się kryptografii postkwantowej NTRU skomercjalizowano i wdrożono w kilku produktach związanych z bezpieczeństwem.

NTRU działa w ilorazowym pierścieniu wielomianów Z[X]/(X^N - 1), gdzie N jest liczbą pierwszą. Wielomiany w tym pierścieniu mają stopień co najwyżej N-1, a mnożenie zawija się (splot). Wybór pierścienia oraz struktura wielomianów o małych współczynnikach mają kluczowe znaczenie zarówno dla wydajności NTRU, jak i jego właściwości bezpieczeństwa.

Generowanie kluczy polega na wybraniu dwóch małych wielomianów f i g, których współczynniki należą do zbioru {-1, 0, 1}. Wielomian f musi być odwracalny zarówno modulo p (mała liczba pierwsza, zazwyczaj 3), jak i modulo q (większa liczba pierwsza, zazwyczaj 2048). Klucz publiczny to h = f_q^{-1} * g mod q, gdzie f_q jest odwrotnością f modulo q. Klucz prywatny stanowi para (f, g).

Aby zaszyfrować wielomian wiadomości m o małych współczynnikach, nadawca wybiera losowy mały wielomian maskujący r i oblicza c = r * h + m mod q. Szyfrogram c jest wielomianem w tym samym pierścieniu. Losowy r zapobiega temu, aby dwa szyfrowania tej samej wiadomości wyglądały identycznie, zapewniając bezpieczeństwo semantyczne.

Deszyfrowanie oblicza a = f * c mod q, wybierając współczynniki z przedziału (-q/2, q/2]. Następnie a mod p odtwarza f_p * m mod p, a pomnożenie przez fp = f^{-1} mod p daje m. Struktura małych współczynników zapewnia, że współczynniki f * c są wystarczająco małe, aby operacje mod q i mod p prawidłowo ze sobą współdziałały i pozwoliły odzyskać wiadomość bez błędu deszyfrowania spowodowanego szumem.

Współczesny NTRU ma dwie standaryzowane rodziny parametrów: NTRU-HPS (Hoffstein-Pipher-Silverman) i NTRU-HRSS (Hulsing-Rijneveld-Schanck-Schwabe). NTRU-HPS wykorzystuje trójwartościowe wielomiany wiadomości, natomiast NTRU-HRSS używa randomizowanego kodowania, aby zmniejszyć odsetek nieudanych deszyfrowań. Oba warianty znalazły się wśród finalistów 3. rundy NIST PQC, a ich zestawy parametrów odpowiadają poziomom bezpieczeństwa 128-, 192- i 256-bitowego.

Nie jest znany żaden atak na odpowiednio sparametryzowany NTRU działający w czasie wielomianowym. Najlepsze ataki sprowadzają się do znalezienia krótkiego wektora w kracie NTRU, co jest instancją przybliżonego problemu SVP. Krata NTRU ma specyficzną strukturę, obejmującą bloki cyrkulantowe, która sprawia, że jest nieco łatwiejsza do zaatakowania niż losowa krata. Dlatego parametry dobiera się z marginesem bezpieczeństwa uwzględniającym tę strukturę.

NTRU był szeroko chroniony patentami firmy NTRU Cryptosystems Inc. (później Security Innovation). Pierwsze patenty zgłoszono w 1996 i 1998 roku. Ochrona patentowa przez dwie dekady utrudniała powszechne wdrażanie oraz tworzenie implementacji open source. Kluczowe patenty NTRU wygasły około 2017 roku, po czym zaczęły się szybko rozpowszechniać otwarte implementacje, a NTRU przystąpił do konkursu standaryzacyjnego NIST PQC.

NTRU był finalistą 3. rundy konkursu NIST PQC, obok Kyber, Classic McEliece i SABER. NIST ostatecznie wybrał Kyber (ML-KEM) jako główny standard KEM, powołując się na prostszą analizę bezpieczeństwa i bardziej przejrzystą konstrukcję. NTRU nie został standaryzowany, ale pozostaje realną alternatywą, a jego analiza przyczyniła się do lepszego zrozumienia bezpieczeństwa krat.

NTRUPrime, opracowany przez Bernsteina, Chuengsatiansupa, Langego i van Vredendaala, celowo usuwa strukturę pierścienia X^N - 1 i zastępuje ją X^N - X - 1, wielomianem o stopniu pierwszym. Eliminuje to potencjalne słabości wynikające z cyklicznej struktury pierścienia, które zdaniem niektórych kryptanalityków można by wykorzystać. NTRUPrime był również alternatywnym kandydatem w konkursie NIST PQC.

NTRU powstał przed schematami opartymi na LWE i nie ma formalnej redukcji trudności dla przypadku najgorszego, takiej jak redukcja LWE Regeva. Jednak NTRU zapewnia szybsze generowanie kluczy i mniejsze rozmiary szyfrogramów niż wiele schematów LWE przy równoważnych poziomach bezpieczeństwa. Kompromisem jest mniej formalna podstawa bezpieczeństwa, oparta na dziesięcioleciach doświadczeń kryptanalitycznych, a nie na dowodzie redukcji.

Z czego wyprowadza się klucz publiczny w NTRU?

NTRU jest pionierskim systemem kryptograficznym opartym na kratach, wykorzystującym arytmetykę w pierścieniu wielomianów. Generowanie kluczy wykorzystuje małe wielomiany f i g, a klucz publiczny ma postać h = f^{-1}*g mod q. Szyfrowanie wykorzystuje losowe maskowanie, a deszyfrowanie korzysta ze struktury małych współczynników f. NTRU nie ma formalnej redukcji dla przypadku najgorszego, ale przetrwał dekady kryptoanalizy. Jego patenty wygasły w 2017 roku, a NTRU był finalistą 3. rundy NIST PQC.