129.217.151.245: /* Construction */

2014-07-01T11:24:20Z

Construction

en>Qetuth: changed stub type to crypto

2012-01-01T07:58:14Z

changed stub type to crypto

New page

The '''Goldreich–Goldwasser–Halevi (GGH)''' [[Lattice-based cryptography|lattice-based]] [[cryptosystem]] is an [[Public-key cryptography|asymmetric]] cryptosystem based on [[Lattice (group)|lattices]]. There is also a [[GGH signature scheme]].

The Goldreich–Goldwasser–Halevi (GGH) cryptosystem makes use of the fact that the [[Lattice problems|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 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 <math>B</math> of a lattice <math>L</math> with good properties (such as short [[Lattice_reduction#Nearly_Orthogonal|nearly orthogonal]] vectors) and a [[unimodular matrix]] <math>U</math>.

The public key is another basis of the lattice <math>L</math> of the form <math>B'=UB</math>.

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

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

: <math>v = \sum \lambda_i b_i'</math>

In matrix notation this is

: <math>v=m\cdot B'</math>.

Remember <math>m</math> consists of integer values, and <math>b'</math> is a lattice point, so v is also a lattice point. The ciphertext is then

: <math>c=v+e=m \cdot B' + e</math>

=== Decryption ===
To decrypt the cyphertext one computes

: <math> 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}</math>

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

: <math> m = m \cdot U \cdot U^{-1} </math>

to get the messagetext.

==Example==
Let <math>L \subset \mathbb{R}^2</math> be a lattice with the basis <math>B</math> and its inverse <math>B^{-1}</math>

: <math> B= \begin{pmatrix}
7 & 0 \\ 0 & 3 \\
\end{pmatrix}</math> and <math>B^{-1}= \begin{pmatrix}
\frac{1}{7} & 0 \\ 0 & \frac{1}{3} \\
\end{pmatrix}</math>

With

: <math>U = \begin{pmatrix}
2 & 3 \\ 3 &5\\
\end{pmatrix}</math> and
: <math>U^{-1} = \begin{pmatrix}
5 & -3 \\ -3 &2\\
\end{pmatrix}</math>

this gives

: <math>B' = U B = \begin{pmatrix}
14 & 9 \\ 21 & 15 \\
\end{pmatrix}</math>

Let the message be <math>m = (3, -7)</math> and the error vector <math>e = (1, -1)</math>. Then the ciphertext is

: <math>c = m B'+e=(-104, -79).\,</math>

To decrypt one must compute

: <math>c B^{-1} = \left( \frac{-104}{7}, \frac{-79}{3}\right).</math>

This is rounded to <math>(-15, -26)</math> and the message is recovered with

: <math>m= (-15, -26) U^{-1} = (3, -7).\,</math>

==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==
* 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. [http://www.di.ens.fr/~pnguyen/pub_Ng99.htm 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.

[[Category:Public-key encryption schemes]]
[[Category:Lattice-based cryptography]]

Preparata code - Revision history

129.217.151.245: /* Construction */

en>Qetuth: changed stub type to crypto