NTRU: storia, design e sicurezza

NTRU è stato inventato da Hoffstein, Pipher e Silverman nel 1996, diventando uno dei più antichi sistemi a chiave pubblica post-quantistici ancora considerati sicuri. A differenza di RSA e ECC, che si basano sulla difficoltà di problemi della teoria dei numeri, la sicurezza di NTRU si basa sulla difficoltà di trovare vettori corti in uno specifico reticolo derivato da anelli polinomiali. NTRU è stato commercializzato e implementato in diversi prodotti di sicurezza prima che la crittografia post-quantistica diventasse di uso comune.

NTRU opera nell’anello polinomiale troncato Z[X]/(X^N - 1), dove N è un numero primo. I polinomi in questo anello hanno grado al massimo N-1 e la moltiplicazione si avvolge ciclicamente (convoluzione). La scelta dell’anello e la struttura dei polinomi con coefficienti piccoli sono fondamentali sia per l’efficienza di NTRU sia per le sue proprietà di sicurezza.

La generazione delle chiavi seleziona due polinomi piccoli f e g con coefficienti in {-1, 0, 1}. Il polinomio f deve essere invertibile sia modulo p, un primo piccolo generalmente uguale a 3, sia modulo q, un primo più grande generalmente uguale a 2048. La chiave pubblica è h = f_q^{-1} * g mod q, dove f_q è l’inverso di f modulo q. La chiave privata è la coppia (f, g).

Per cifrare un polinomio messaggio m con coefficienti piccoli, il mittente sceglie un polinomio casuale piccolo r di mascheramento e calcola c = r * h + m mod q. Il testo cifrato c è un polinomio nello stesso anello. Il valore casuale r impedisce che due cifrature dello stesso messaggio risultino identiche, garantendo la sicurezza semantica.

La decifratura calcola a = f * c mod q, scegliendo coefficienti nell’intervallo (-q/2, q/2]. Quindi a mod p recupera f_p * m mod p e la moltiplicazione per fp = f^{-1} mod p restituisce m. La struttura a piccoli coefficienti garantisce che i coefficienti di f * c siano abbastanza piccoli affinché le operazioni mod q e mod p interagiscano correttamente e recuperino il messaggio senza errori di rumore.

NTRU moderno presenta due famiglie di parametri standardizzate: NTRU-HPS (Hoffstein-Pipher-Silverman) e NTRU-HRSS (Hulsing-Rijneveld-Schanck-Schwabe). NTRU-HPS utilizza polinomi messaggio ternari, mentre NTRU-HRSS utilizza una codifica randomizzata per ridurre il tasso di errori di decifratura. Entrambi sono stati finalisti del terzo ciclo della competizione NIST PQC, con insiemi di parametri destinati a livelli di sicurezza di 128, 192 e 256 bit.

Non è noto alcun attacco in tempo polinomiale contro NTRU parametrizzato correttamente. I migliori attacchi si riducono alla ricerca di un vettore corto in un reticolo NTRU, che costituisce un’istanza del problema SVP approssimato. Il reticolo NTRU presenta una struttura specifica, con blocchi circolanti, che lo rende leggermente più facile da attaccare rispetto a un reticolo casuale; per questo i parametri vengono scelti con un margine di sicurezza che tiene conto di tale struttura.

NTRU è stato ampiamente brevettato da NTRU Cryptosystems Inc., in seguito Security Innovation. I brevetti originali sono stati depositati nel 1996 e nel 1998. Questa protezione brevettuale ha ostacolato per due decenni l’adozione su larga scala e le implementazioni open source. I brevetti fondamentali di NTRU sono scaduti intorno al 2017; in seguito le implementazioni aperte si sono diffuse rapidamente e NTRU è entrato nella competizione di standardizzazione NIST PQC.

NTRU è stato finalista del terzo ciclo della competizione NIST PQC insieme a Kyber, Classic McEliece e SABER. NIST ha infine scelto Kyber (ML-KEM) come principale standard KEM, citando un’analisi della sicurezza più semplice e una progettazione più lineare. NTRU non è stato standardizzato, ma rimane un’alternativa valida e la sua analisi ha contribuito alla comprensione della sicurezza dei reticoli.

NTRUPrime, sviluppato da Bernstein, Chuengsatiansup, Lange e van Vredendaal, rimuove deliberatamente la struttura ad anello X^N - 1 e la sostituisce con X^N - X - 1, un polinomio di grado primo. Ciò elimina potenziali debolezze derivanti dalla struttura dell’anello ciclico che alcuni crittoanalisti ritengono possano essere sfruttate. NTRUPrime è stato anch’esso un candidato alternativo nella competizione NIST PQC.

NTRU precede gli schemi basati su LWE e non dispone di una riduzione formale dalla difficoltà nel caso peggiore come la riduzione di Regev per LWE. Tuttavia, NTRU è più veloce nella generazione delle chiavi e ha testi cifrati più piccoli rispetto a molti schemi LWE con livelli di sicurezza equivalenti. Il compromesso consiste in un fondamento di sicurezza meno formale, basato su decenni di esperienza nella crittoanalisi anziché su una dimostrazione di riduzione.

In NTRU, da cosa deriva la chiave pubblica?

NTRU è un crittosistema pionieristico basato sui reticoli e sull’aritmetica degli anelli polinomiali. La generazione delle chiavi utilizza polinomi piccoli f e g, con chiave pubblica h = f^{-1}*g mod q. La cifratura utilizza un mascheramento casuale, mentre la decifratura sfrutta la struttura a piccoli coefficienti di f. NTRU non dispone di una riduzione formale dal caso peggiore, ma ha resistito a decenni di crittoanalisi. I suoi brevetti sono scaduti nel 2017 ed è stato finalista del terzo ciclo NIST PQC.