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. This system was published in 1997 by
Oded Goldreich
Oded Goldreich ( he, עודד גולדרייך; b. 1957) is a professor of Computer Science at the Faculty of Mathematics and Computer Science of Weizmann Institute of Science, Israel. His research interests lie within the theory of computation ...
,
Shafi Goldwasser
en, Shafrira Goldwasser
, name = Shafi Goldwasser
, image = Shafi Goldwasser.JPG
, caption = Shafi Goldwasser in 2010
, birth_place = New York City, New York, U.S.
, birth_date =
, death_date ...
, and
Shai Halevi
Shai Halevi ( he, שי הלוי; born 1966) is a computer scientist who works on cryptography research at Algorand Foundation, a blockchain startup founded by Silvio Micali.
Born in Israel in 1966, Halevi received a B.A. and M.Sc. in computer sc ...
, and uses a
trapdoor one-way function which relies on the difficulty of
lattice reduction
In mathematics, the goal of lattice basis reduction is to find a basis with short, nearly orthogonal vectors when given an integer lattice basis as input. This is realized using different algorithms, whose running time is usually at least expone ...
. 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 (broken) in 1999 by . Nguyen and
Oded Regev had cryptanalyzed the related
GGH signature scheme in 2006.
Operation
GGH involves a ''private key'' and a ''public key''.
The private key is a basis
of a lattice
with good properties (such as short
nearly orthogonal vectors) and a
unimodular matrix
In mathematics, a unimodular matrix ''M'' is a square integer matrix having determinant +1 or −1. Equivalently, it is an integer matrix that is invertible over the integers: there is an integer matrix ''N'' that is its inverse (these are equiv ...
.
The public key is another basis of the lattice
of the form
.
For some chosen M, the message space consists of the vector
in the range