GGH encryption scheme
Encyclopedia
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.
The private key is a basis
of a lattice 
with good properties, such as short nearly orthogonal vectors and a unimodular matrix
.
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 
.
, error 
, and a
public key
compute
In matrix notation this is
Remember
consists of integer values, and 
is a lattice point, so v is also a lattice point. The ciphertext is then
The Babai rounding technique will be used to remove the term
as long as it is small enough. Finally compute
to get the messagetext.
be a lattice with the basis 
and its inverse 
Cryptosystem
There are two different meanings of the word cryptosystem. One is used by the cryptographic community, while the other is the meaning understood by the public.- General meaning :...
is an asymmetric
Public-key cryptography
Public-key cryptography refers to a cryptographic system requiring two separate keys, one to lock or encrypt the plaintext, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private...
cryptosystem based on lattices
Lattice (group)
In mathematics, especially in geometry and group theory, a lattice in Rn is a discrete subgroup of Rn which spans the real vector space Rn. Every lattice in Rn can be generated from a basis for the vector space by forming all linear combinations with integer coefficients...
. There is also a GGH signature scheme
GGH signature scheme
The Goldreich-Goldwasser-Halevi signature scheme is a digital signature scheme proposed in 1995 and published in 1997, based on solving the closest vector problem in a lattice...
.
The Goldreich–Goldwasser–Halevi (GGH) cryptosystem makes use of the fact that the closest vector problem
Lattice problems
In computer science, lattice problems are a class of optimization problems on lattices. The conjectured intractability of such problems is central to construction of secure lattice-based cryptosystems...
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.
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 matrixUnimodular matrix
In mathematics, a unimodular matrix M is a square integer matrix with determinant +1 or −1. Equivalently, it is an integer matrix that is invertible over the integers: there is an integer matrix N which is its inverse...
.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 .Encryption
Given a message, error , and apublic key
compute
In matrix notation this is
-
.
Remember
consists of integer values, and is a lattice point, so v is also a lattice point. The ciphertext is then
Decryption
To decrypt the cyphertext one computes
The Babai rounding technique will be used to remove the term
as long as it is small enough. Finally compute
to get the messagetext.
Example
Let be a lattice with the basis and its inverse -
and 
With
-
and
-
this gives
-
Let the message be
and the error vector 
. Then the ciphertext is
To decrypt one must compute
This is rounded to
and the message is recovered with
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. -
-
-
-
