Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
GGH encryption scheme
open-in-new
<p>The Goldreich–Goldwasser–Halevi (GGH) <a href="/facts/Lattice-based_cryptography/66HyNf1P">lattice-based</a> <a href="/facts/Cryptosystem/GyDVJ4D0">cryptosystem</a> is a broken <a href="/facts/Public-key_cryptography/gowoFTxS">asymmetric</a> cryptosystem based on <a href="/facts/Lattice_(group)/2ls9Iv9N">lattices</a>. There is also a <a href="/facts/GGH_signature_scheme/lflntMco">GGH signature scheme</a> which hasn't been broken as of 2024. </p><p>The Goldreich–Goldwasser–Halevi (GGH) cryptosystem makes use of the fact that the <a href="/facts/Lattice_problems/YHXNNrrG">closest vector problem</a> can be a hard problem. This system was published in 1997 by <a href="/facts/Oded_Goldreich/Ufn1bqW7">Oded Goldreich</a>, <a href="/facts/Shafi_Goldwasser/aTJJq4mB">Shafi Goldwasser</a>, and <a href="/facts/Shai_Halevi/QL3D6H0e">Shai Halevi</a>, and uses a <a href="/facts/Trapdoor_function/xMTTRrhY">trapdoor one-way function</a> which relies on the difficulty of <a href="/facts/Lattice_reduction/Mrz9g9oc">lattice reduction</a>. 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. </p><p>The GGH encryption scheme was cryptanalyzed (broken) in 1999 by Phong Q. Nguyen [fr]. Nguyen and <a href="/facts/Oded_Regev_(computer_scientist)/qb5CDFDC">Oded Regev</a> had cryptanalyzed the related <a href="/facts/GGH_signature_scheme/lflntMco">GGH signature scheme</a> in 2006. </p>