Lattice Based Cryptography (the GGH scheme)
Laila El Aimani ( Cosec (B-it) ):
Tuesday 09 May 2006, 15.00 sharp (s.t.), b-it 1.25 (cosec meeting room)
Contents
The GGH cryptosystem [GGH97] is the analogous, in lattices, of the McEliece system, based on error correcting codes. It is probably the most intuitive method for using lattices to devise a public key cryptosystem. The idea underlying the construction is that, given any basis for a lattice, it is easy to generate a vector which is close to a lattice point (by adding a small perturbation to the lattice point), whereas, it seems to be hard to recover, from this close vector, the original lattice point (given an arbitrary lattice basis).
The authors of the system have conjectured that their cryptosystem was secure for at least dimensions higher than 300. However, A paper by Nguyen [Ng99] exibited a weakness of the scheme whose consequences were devastating: There was a leakage of information about the plain text, which will simplify the process of decoding.
In this talk, we will present the GGH cryptosystem as well as the mentioned attack and finally conclude with recommendations to improve the scheme.
keywords: lattice algorithmic problems, lattice based cryptography, public key cryptography.