PICSI

Algorithme à clé publique: NTRU (réseaux euclidiens)

NTRU est initialement un schéma de chiffrement à clé publique dû à J. Hoffstein, J. Pipher et J. H. Silverman [1]. Proposé en 1996, il fit l'effet d'une petite bombe, d'une part en raison de ses performances annoncées, d'autre part parce qu'il illustrait pour la première fois que la théorie des réseaux euclidiens (lattices) pouvait aussi être source de schémas efficaces, et pas seulement de méthodes de cryptanalyse dévastatrices avec l'algorithme LLL (Lenstra-Lenstra-Lovasz). Plus précisément, la sécurité de NTRU est connectée à la difficulté de trouver le plus petit vecteur dans un réseau euclidien de grande dimension.

NTRU utilise des polynômes réduits modulo X^N dont les coefficients eux-mêmes réduits modulo un premier q sont volontairement choisis petits afin d'accélérer les calculs. La version utilisant de petites valeurs de N et q fut vite cassée [2], mais si par exemple N = 251 et q = 239, alors le schéma résiste à la cryptanalyse. Des algorithmes de signature ont également été proposés, mais ils ont connu de mauvaises fortunes. Le dernier en date [3] a été sévèrement ébranlé lors de la conférence Eurocrypt 2006 [4].

Les algorithmes NTRU sont normalisés ou en cours de normalisation à l'IEEE [5].





[1] J. Hoffstein, J. Pipher and J. H. Silverman. NTRU : a ring based public key cryptosystem. In Proc. of ANTS III, LNCS 1423, pages 267-288, Springer-Verlag, 1998. First presented at the rump session of Crypto‘96.

[2] D. Coppersmith and A. Shamir. Lattices attacks on NTRU. In Proc. of Eucrocrypt‘97, LNCS 1233, pages 52-61, Springer-Verlag, 1998.
 
[3] J. Hoffstein, J. Pipher and J. H. Silverman. NTRUSIGN : Digital signatures using the NTRU lattice. In Proc. of CT-RSA‘03, LNCS 2612, pages 122-140, Springer-Verlag, 2003.

[4] P.Q. Nguyen and O. Regev. Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures. In Proceedings of Eurocrypt‘06, LNCS 4004, pages 271-288, Springer-Verlag, 2006.

[5] IEEE P1361.1. Public-key cryptographic techniques based on hard problems over lattices. http://grouper.ieee.org/groups/1363/lattPK/index.html