Détail de la notice
Titre du Document
Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from Crypto '97
Auteur(s)
NGUYEN P. ; Wiener Michael (Editeur scientifique)
Résumé
Recent results of Ajtai on the hardness of lattice problems have inspired several cryptographic protocols. At Crypto '97, Goldreich, Goldwasser and Halevi proposed a public-key cryptosystem based on the closest vector problem in a lattice, which is known to be NP-hard. We show that there is a major flaw in the design of the scheme which has two implications: any ciphertext leaks information on the plaintext, and the problem of decrypting ciphertexts can be reduced to a special closest vector problem which is much easier than the general problem. As an application, we solved four out of the five numerical challenges proposed on the Internet by the authors of the cryptosystem. At least two of those four challenges were conjectured to be intractable. We discuss ways to prevent the flaw, but conclude that, even modified, the scheme cannot provide sufficient security without being impractical.
Editeur
Springer
Type du document
Conférence : Annual international cryptology conference, 19, Santa Barbara CA, USA, 1999-08-15
Identifiant
ISSN : 0302-9743 ISBN : 3-540-66347-9
Source
Lecture notes in computer science A. 1999, vol. 1666, pp. 288-304 [bibl. : 28 ref.]
Langue
Anglais
Pour les membres de la communauté du CNRS, ce document est autorisé à la reproduction à titre gratuit.
Pour les membres des communautés hors CNRS, la reproduction de ce document à titre onéreux sera fournie sous réserve d’autorisation du Centre Français d’exploitation du droit de Copie.

Pour bénéficier de nos services (strictement destinés aux membres de la communauté CNRS (Centre National de la Recherche Scientifique), de l'ESR français (Enseignement Supérieur et Recherche), et du secteur public français & étranger) :