GGH encryption scheme - Alchetron, The Free Social Encyclopedia

The Goldreich–Goldwasser–Halevi (GGH) lattice-based cryptosystem is an asymmetric cryptosystem based on lattices. There is also a GGH signature scheme.

The Goldreich–Goldwasser–Halevi (GGH) cryptosystem makes use of the fact that the closest vector problem can be a hard problem. It was published in 1997 by Oded Goldreich, Shafi Goldwasser, and Shai Halevi, and uses a trapdoor one-way function that is relying on the difficulty of lattice reduction. The idea included in this trapdoor function is that, given any basis for a lattice, it is easy to generate a vector which is close to a lattice point, for example taking a lattice point and adding a small error vector. But to return from this erroneous vector to the original lattice point a special basis is needed.

The GGH encryption scheme was cryptanalyzed in 1999 by Phong Q. Nguyen.

Operation

GGH involves a private key and a public key.

The private key is a basis B of a lattice L with good properties (such as short nearly orthogonal vectors) and a unimodular matrix U .

The public key is another basis of the lattice L of the form B ′ = U B .

For some chosen M, the message space consists of the vector ( m 1 , . . . , m n ) in the range − M < m i < M .

Encryption

Given a message m = ( m 1 , . . . , m n ) , error e , and a public key B ′ compute

v = ∑ m i b i ′

In matrix notation this is

v = m ⋅ B ′ .

Remember m consists of integer values, and b ′ is a lattice point, so v is also a lattice point. The ciphertext is then

c = v + e = m ⋅ B ′ + e

Decryption

To decrypt the cyphertext one computes

c ⋅ B − 1 = ( m ⋅ B ′ + e ) B − 1 = m ⋅ U ⋅ B ⋅ B − 1 + e ⋅ B − 1 = m ⋅ U + e ⋅ B − 1

The Babai rounding technique will be used to remove the term e ⋅ B − 1 as long as it is small enough. Finally compute

m = m ⋅ U ⋅ U − 1

to get the messagetext.

Example

Let L ⊂ R 2 be a lattice with the basis B and its inverse B − 1

B = ( 7 0 0 3 ) and B − 1 = ( 1 7 0 0 1 3 )

With

U = ( 2 3 3 5 ) and U − 1 = ( 5 − 3 − 3 2 )

this gives

B ′ = U B = ( 14 9 21 15 )

Let the message be m = ( 3 , − 7 ) and the error vector e = ( 1 , − 1 ) . Then the ciphertext is

c = m B ′ + e = ( − 104 , − 79 ) .

To decrypt one must compute

c B − 1 = ( − 104 7 , − 79 3 ) .

This is rounded to ( − 15 , − 26 ) and the message is recovered with

m = ( − 15 , − 26 ) U − 1 = ( 3 , − 7 ) .

Security of the scheme

1999 Nguyen showed at the Crypto conference that the GGH encryption scheme has a flaw in the design of the schemes. He showed that every ciphertext reveals information about the plaintext and that the problem of decryption could be turned into a special closest vector problem much easier to solve than the general CVP.

References

GGH encryption scheme Wikipedia

(Text) CC BY-SA