Cryptosystems and LLL

Since the late 70’s, several public key cryptographic algorithms have been proposed. Diffie and Hellman first came with this concept in 1976. Since that time, several other public key cryptosystems were invented, such as the well known RSA, ElGamal or Rabin cryptosystems. Roughly, the scope of these algorithms is to allow the secure exchange of a secret key that will later on be used to encrypt a larger amount of data. All these algorithms share one particularity, namely that their security rely on some mathematical problem which is supposed to be hard (computationally speaking) to solve. For example, it is well known that the ability to factorize easily the product of two large primes without any indication about the primes, would lead to break the RSA cryptosystem. Since those early days, most of the assymetric encryption algorithms that have been proposed relied on the same hard mathematical problems. Yet, it is well accepted that we should not put al l the cryptographic eggs in one basket. This is the reason why Goldreich, Goldwasser, and Halevi proposed in 1997 (exactly 10 years after RSA) a new public-key cryptosystem which security was based on lattice reduction problems. This cryptographic schemes is known as the GGH cryptosystem. Unfortunately, only two years later, Nguyen proposed an attack against GGH which proved that in practice, GGH would not provide the security it originally claimed to have. The attack involved a so called lattice reduction algorithm, known as LLL. The aim of this work is to provide the necessary background to understand the GGH cryptosystem and the attack that goes with it. The basis reduction algorithm LLL has many other applications in cryptography. As an example, we will review a very recent attack against the GNU Privacy Guard software, which is a widely used free implementation of Zimmermann’s famous software. The necessary background about lattices, LLL, . . . will be recalled in sections 2 and 3. Section 4 will review the GGH cryptosystem and Nguyen’s attack against it. Finally, Section 5 will show how lattice reduction techniques can break the ElGamal digital signature scheme implementation in GPGv1.2.3.