Fandom

DSZQUP XJLJ

GGH encryption scheme

564pages on
this wiki
Add New Page
Talk0 Share

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

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 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 it is not known how to simply return from this erroneous vector to the original lattice point.

OperationEdit

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 Edit

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 Edit

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.

ExampleEdit

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 schemeEdit

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.

BibliographyEdit

  • Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Public-key cryptosystems from lattice reduction problems. In CRYPTO ’97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, pages 112–131, London, UK, 1997. Springer-Verlag.
  • Phong Q. Nguyen. Cryptanalysis of the Goldreich–Goldwasser–Halevi Cryptosystem from Crypto ’97. In CRYPTO ’99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, pages 288–304, London, UK, 1999. Springer-Verlag.

Also on Fandom

Random Wiki