salle A. Pnueli CE3
31 May 2012 - 15h00
Une preuve de sécurité pour le cryptosystème NTRU
by Damien Stehle from LIP laboratory, ENS Lyon, Equipe Aric
Résumé : 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
Slides of the Presentation.
