GGH encryption scheme

GGH encryption scheme

The Goldreich-Goldwasser-Halevi (GGH) cryptosystem is a asymetriccryptosystem based on lattice.

The Goldreich-Goldwasser-Halevi (GGH) cryptosystem makes use of thefactthatthe CVP can be a hard problem. It was published in 1997 and uses atrapdoorone-way function that is relying on the difficulty of latticereduction.The ideaincluded in this trapdoor function is that, given any basis for alattice, it is easyto generate a vector which is close to a lattice point, for exampletaking a latticepoint and adding a small error vector. But it is not known how tosimplyreturnfrom this erroneous vector to the original lattice point.

Operation

GGH involves a private key and a public key.

The private key is a basis B of a lattice Lwith good properties as short mostly orthogonal vectors and aunimodularmatrix U.

The public key is of the lattice L of the formB'=UB.

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

Encryption

Given a message m = (lambda_1,..., lambda_n) and apublickey B' compute

v = sum lambda_i b_i'

In matrix notation this is v=mcdot 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} = (mcdot B+e)B^{-1} = mcdot Ucdot Bcdot B^{-1} + ecdot B^{-1} = mcdot U + ecdot B^{-1}

The Babai rounding technique will be used to remove the term e cdot B^{-1} as longas 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= egin{pmatrix} 7 & 0 \ 0 & 3 \ end{pmatrix} and B^{-1}= egin{pmatrix} frac{1}{7} & 0 \ 0 & frac{1}{3} \ end{pmatrix}

With

U = egin{pmatrix} 2 & 3 \ 3 &5\ end{pmatrix} andU^{-1} = egin{pmatrix} 5 & -3 \ -3 &2\ end{pmatrix}

this gives B' = U B = egin{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} ight).

This is rounded to (-15, -26) and the message is recovered withm= (-15, -26) U^{-1} = (3, -7).

ecurity 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 in a special closest vector problem much easier to solve than the general CVP.

Bibliography

* 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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • GGH signature scheme — The Goldreich Goldwasser Halevi (GGH) signature scheme is a digital signature scheme proposed in 1995 and published in 1997, based on solving the closest vector problem (CVP) in a lattice. The signer demonstrates knowledge of a good basis for the …   Wikipedia

  • GGH encryption algorithm — The Goldreich Goldwasser Halevi (GGH) signature scheme is an asymmetric key encryption algorithm proposed in 1995 and published in 1997, based on solving the close vector problem (CVP) in a lattice. The encrypter uses the public key, a bad… …   Wikipedia

  • Lattice based cryptography — is the generic term for asymmetric cryptographic primitives based on lattice. HistoryLattice have first been discovered by mathematicans Lagrange and Gauss. Lattice have been used laterly in computer algorithms and in cryptanalysis. In 1996 Atjai …   Wikipedia

  • NTRUSign — NTRUSign, also known as the NTRU Signature Algorithm, is a public key cryptography digital signature algorithm based on the GGH signature scheme. It was first presented at the rump session of Asiacrypt 2001 and published in peer reviewed form at… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”