NTRUEncrypt, proposé en 1996 par Hoffstein, Pipher et Silverman, est le schéma de chiffrement asymétrique le plus efficace, parmi ceux dont la sécurité repose sur la difficulté de problèmes portant sur les réseaux euclidiens. Malheureusement, depuis sa création, sa sécurité a régulièrement été mise en doute. Nous montrerons comment modifier NTRUEncrypt pour qu'il admette une preuve de sécurité contre les attaques à clair choisi, sous l'hypothèse qu'il est difficile de trouver des vecteurs courts dans des réseaux correspondant à des idéaux arbitraires des anneaux d'entiers de corps cyclotomiques. La preuve repose sur les travaux récents de [Lyubashevsky et al., Eurocrypt'10] sur la difficulté du problème Ring-LWE. Notre principale contribution est de démontrer que si les polynômes de petites hauteurs correspondant à la clé secrète sont tirés suivant une loi Gaussienne discrète, alors la distribution de la clé publique, qui est leur quotient modulo un entier, est statistiquement proche de la loi uniforme sur son domaine.

Travail en commun avec Ron Steinfeld