GGHs

GGHs refers to the Goldreich–Goldwasser–Halevi cryptosystem, a public-key cryptosystem introduced in 1997 by Oded Goldreich, Shafi Goldwasser, and Yael Halevi. It is one of the early lattice-based schemes and its security is based on the difficulty of the closest vector problem (CVP) in lattices.

The system uses two bases of the same lattice: a private short basis B and a public basis A. The public key is A, while the private key consists of B together with a unimodular matrix U such that A = B U. This relationship means the two bases generate the same lattice, but B is shorter and better conditioned for decoding.

Key generation involves selecting a good private basis B and a unimodular matrix U, then computing A = B U and publishing A as the public key. The private key is (B, U).

Encryption proceeds by mapping the plaintext message to an integer vector m and selecting a small error vector e. The ciphertext is computed as c = A m + e and transmitted to the recipient. The small error masks the exact lattice point A m, making direct inversion difficult without the private basis.

Decryption uses the private basis B to solve a closest vector problem: it finds y that minimizes || c − B y ||, which yields y ≈ U m. The plaintext is recovered by m = U^{-1} y.

Security rests on the presumed hardness of approximate CVP. In practice, the original GGH scheme has vulnerabilities to certain lattice attacks and chosen-ciphertext attacks, and it is not widely used in modern deployments. Nevertheless, GGH is historically important for illustrating lattice-based public-key encryption and has influenced subsequent designs in lattice cryptography.