Titre du document / Document title

Cryptanalysis of the Goldreich-Goldwasser-Halevi cryptosystem from Crypto '97

Auteur(s) / Author(s)

NGUYEN P. ⁽¹⁾ ;

Affiliation(s) du ou des auteurs / Author(s) Affiliation(s)

⁽¹⁾ École Normale Supérieure, Laboratoire d'Informatique, 45 rue d'Ulm, 75230 Paris, FRANCE

Résumé / Abstract

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.

Revue / Journal Title

Lecture notes in computer science    ISSN  0302-9743 

Source / Source

Congrès
CRYPTO '99 : advances in cryptology :   ( Santa Barbara CA, 15-19 August 1999 )
Annual international cryptology conference N^o19, Santa Barbara CA , ETATS-UNIS (15/08/1999)
1999  , vol. 1666, pp. 288-304[Note(s) : XII, 638 p., ] (28 ref.) ISBN 3-540-66347-9 ;  Illustration : Illustration ;

Langue / Language

Anglais

Editeur / Publisher

Springer, Berlin, ALLEMAGNE  (1973) (Revue)
Springer, Berlin, ALLEMAGNE  (1999) (Monographie)

Mots-clés anglais / English Keywords

Cryptography

;

NP hard problem

;

Public key

;

Internet

;

Mots-clés français / French Keywords

Cryptographie

;

Problème NP difficile

;

Clé publique

;

Internet

;

Mots-clés espagnols / Spanish Keywords

Criptografía

;

Problema NP duro

;

Llave pública

;

Internet

;

Localisation / Location

INIST-CNRS, Cote INIST : 16343, 35400008456254.0180