GGH encryption scheme

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'=UB.

For some chosen M, the message space consists of the vector (\lambda_1,..., \lambda_n) in the range -M <\lambda_i < M.

Encryption

Given a message m = (\lambda_1,..., \lambda_n), error e, and a public key B' compute

v = \sum \lambda_i b_i'

In matrix notation this is

v=m\cdot 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 \cdot B' + e

Decryption

To decrypt the cyphertext one computes

 c \cdot B^{-1} = (m\cdot B^\prime +e)B^{-1} = m\cdot U\cdot B\cdot B^{-1} + e\cdot B^{-1} = m\cdot U + e\cdot B^{-1}

The Babai rounding technique will be used to remove the term e \cdot B^{-1} as long as it is small enough. Finally compute

 m = m \cdot U \cdot U^{-1}

to get the messagetext.

Example

Let L \subset \mathbb{R}^2 be a lattice with the basis B and its inverse B^{-1}

 B=  \begin{pmatrix}
 7 & 0 \\ 0 & 3 \\      
     \end{pmatrix} and B^{-1}=  \begin{pmatrix}
 \frac{1}{7} & 0 \\ 0 & \frac{1}{3} \\      
     \end{pmatrix}

With

U = \begin{pmatrix}
         2 & 3 \\ 3 &5\\
        \end{pmatrix} and
U^{-1} = \begin{pmatrix}
         5 & -3 \\ -3 &2\\
        \end{pmatrix}

this gives

B' = U B = \begin{pmatrix}
            14 & 9 \\ 21 & 15 \\
           \end{pmatrix}

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} = \left( \frac{-104}{7}, \frac{-79}{3}\right).

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.

Bibliography

This article is issued from Wikipedia - version of the Sunday, December 20, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.