NTRU : histoire, conception et sécurité

NTRU a été inventé par Hoffstein, Pipher et Silverman en 1996, ce qui en fait l’un des plus anciens systèmes à clé publique post-quantiques encore considérés comme sûrs. Contrairement à RSA et ECC, qui reposent sur la difficulté de problèmes de théorie des nombres, la sécurité de NTRU repose sur la difficulté de trouver des vecteurs courts dans un réseau particulier construit à partir d’anneaux de polynômes. NTRU a été commercialisé et déployé dans plusieurs produits de sécurité avant que la cryptographie post-quantique ne devienne courante.

NTRU fonctionne dans l’anneau de polynômes tronqué Z[X]/(X^N - 1), où N est un nombre premier. Les polynômes de cet anneau sont de degré au plus N-1 et la multiplication s’effectue avec repliement, c’est-à-dire par convolution. Le choix de l’anneau et la structure des polynômes à petits coefficients sont essentiels à la fois à l’efficacité de NTRU et à ses propriétés de sécurité.

La génération des clés sélectionne deux petits polynômes f et g dont les coefficients appartiennent à {-1, 0, 1}. Le polynôme f doit être inversible à la fois modulo p, un petit nombre premier généralement égal à 3, et modulo q, un nombre premier plus grand généralement égal à 2048. La clé publique est h = f_q^{-1} * g mod q, où f_q est l’inverse de f modulo q. La clé privée est le couple (f, g).

Pour chiffrer un polynôme de message m à petits coefficients, l’expéditeur choisit un petit polynôme de masquage aléatoire r et calcule c = r * h + m mod q. Le chiffré c est un polynôme du même anneau. Le caractère aléatoire de r empêche deux chiffrés du même message de paraître identiques, ce qui assure la sécurité sémantique.

Le déchiffrement calcule a = f * c mod q en choisissant les coefficients dans l’intervalle (-q/2, q/2]. Ensuite, a mod p permet de retrouver f_p * m mod p, et la multiplication par fp = f^{-1} mod p donne m. La structure de la petite erreur garantit que les coefficients de f * c sont suffisamment petits pour que les opérations modulo q et modulo p s’articulent correctement et permettent de retrouver le message sans échec dû au bruit.

Les versions modernes de NTRU possèdent deux familles de paramètres normalisées : NTRU-HPS (Hoffstein-Pipher-Silverman) et NTRU-HRSS (Hulsing-Rijneveld-Schanck-Schwabe). NTRU-HPS utilise des polynômes de message ternaires, tandis que NTRU-HRSS utilise un codage aléatoire afin d’obtenir de meilleurs taux de réussite du déchiffrement. Les deux ont été retenus comme finalistes de la troisième ronde de NIST PQC, avec des jeux de paramètres visant une sécurité de 128, 192 et 256 bits.

Aucune attaque en temps polynomial contre NTRU correctement paramétré n’est connue. Les meilleures attaques se ramènent à la recherche d’un vecteur court dans un réseau NTRU, ce qui constitue une instance du problème SVP approché. Le réseau NTRU possède une structure particulière, faite de blocs circulants, qui le rend légèrement plus facile à attaquer qu’un réseau aléatoire. Les paramètres sont donc choisis avec une marge de sécurité qui tient compte de cette structure.

NTRU a fait l’objet d’un grand nombre de brevets déposés par NTRU Cryptosystems Inc., devenue par la suite Security Innovation. Les brevets d’origine ont été déposés en 1996 et 1998. Cette protection par brevet a freiné l’adoption à grande échelle et les implémentations à code source ouvert pendant deux décennies. Les brevets fondamentaux de NTRU ont expiré vers 2017, après quoi les implémentations ouvertes se sont multipliées et NTRU a rejoint la compétition de normalisation NIST PQC.

NTRU était finaliste de la troisième ronde de la compétition NIST PQC, aux côtés de Kyber, Classic McEliece et SABER. NIST a finalement choisi Kyber (ML-KEM) comme norme KEM principale, en invoquant une analyse de sécurité plus simple et une conception plus claire. NTRU n’a pas été normalisé, mais reste une alternative viable, et son analyse a contribué à approfondir la compréhension de la sécurité des réseaux.

NTRUPrime, développé par Bernstein, Chuengsatiansup, Lange et van Vredendaal, supprime délibérément la structure d’anneau X^N - 1 et la remplace par X^N - X - 1, un polynôme de degré premier. Cela élimine les faiblesses potentielles liées à la structure d’anneau cyclique que certains cryptanalystes pensent pouvoir exploiter. NTRUPrime était également un candidat alternatif de NIST PQC.

NTRU est antérieur aux schémas fondés sur LWE et ne bénéficie pas d’une réduction formelle de difficulté dans le pire cas comme la réduction de Regev pour LWE. Cependant, NTRU est plus rapide pour la génération des clés et produit des chiffrés plus petits que de nombreux schémas LWE offrant des niveaux de sécurité équivalents. Le compromis est un fondement de sécurité moins formel, qui repose sur des décennies d’expérience cryptanalytique plutôt que sur une preuve par réduction.

Dans NTRU, de quoi la clé publique est-elle dérivée ?

NTRU est un cryptosystème pionnier fondé sur les réseaux et reposant sur l’arithmétique des anneaux de polynômes. La génération des clés utilise les petits polynômes f et g, avec pour clé publique h = f^{-1}*g mod q. Le chiffrement utilise un masquage aléatoire ; le déchiffrement exploite la structure à petits coefficients de f. NTRU ne possède aucune réduction formelle du pire cas, mais a résisté à plusieurs décennies d’analyse cryptographique. Ses brevets ont expiré en 2017 et il a été finaliste de la troisième ronde de NIST PQC.