imported>WikiCleanerBot: v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

2025-06-28T05:49:28Z

v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

New page

{{Short description|Lattice-based cryptosystem}}
The '''Goldreich–Goldwasser–Halevi (GGH)''' [[Lattice-based cryptography|lattice-based]] [[cryptosystem]] is a broken [[Public-key cryptography|asymmetric]] cryptosystem based on [[Lattice (group)|lattices]]. There is also a [[GGH signature scheme]] which hasn't been broken as of 2024.

The Goldreich–Goldwasser–Halevi (GGH) cryptosystem makes use of the fact that the [[Lattice problems|closest vector problem]] can be a hard problem. This system was published in 1997 by [[Oded Goldreich]], [[Shafi Goldwasser]], and [[Shai Halevi]], and uses a [[trapdoor function|trapdoor one-way function]] which relies 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 (broken) in 1999 by {{ill|Phong Q. Nguyen|fr|Phong Nguyen}}. Nguyen and [[Oded Regev (computer scientist)|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 <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>(m_1,..., m_n)</math> in the range <math>-M <m_i < M</math>.

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

: <math>v = \sum m_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 ciphertext 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 message.

==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 ==
In 1999, Nguyen <ref>Phong Nguyen. ''Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from Crypto '97''. CRYPTO, 1999</ref> showed that the GGH encryption scheme has a flaw in the design. 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.

== Implementations ==
* [https://github.com/TheGaBr0/GGH TheGaBr0/GGH] – A Python implementation of the GGH cryptosystem and its optimized variant GGH-HNF.<ref>Micciancio, Daniele. (2001). Improving Lattice Based Cryptosystems Using the Hermite Normal Form. LNCS. 2146. 10.1007/3-540-44670-2_11.</ref> The library includes key generation, encryption, decryption, basic lattice reduction techniques, and demonstrations of known attacks. It is intended for educational and research purposes and is available via [https://pypi.org/project/GGH-crypto/ PyPI].

==References==
{{Reflist}}

== Bibliography ==
*{{cite book |first1=Oded |last1=Goldreich |first2=Shafi |last2=Goldwasser |first3=Shai |last3=Halevi |chapter=Public-key cryptosystems from lattice reduction problems |title=CRYPTO '97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology |pages=112–131 |location=London |year=1997 |publisher=Springer-Verlag }}
*{{cite book |first=Phong Q. |last=Nguyen |chapter-url=https://www.di.ens.fr/~pnguyen/pub_Ng99.htm |chapter=Cryptanalysis of the Goldreich–Goldwasser–Halevi Cryptosystem from Crypto ’97 |title=CRYPTO '99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology |pages=288–304 |location=London |year=1999 |publisher=Springer-Verlag }}
* {{cite journal | last1 = Nguyen | first1 = Phong Q. | last2 = Regev | first2 = Oded | title = Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures| journal = Journal of Cryptology | date = 11 November 2008 | volume = 22 | issue = 2 | pages = 139–160 | issn = 0933-2790 | eissn = 1432-1378 | doi = 10.1007/s00145-008-9031-0 | pmid = | s2cid = 2164840 | url = https://iacr.org/archive/eurocrypt2006/40040273/40040273.pdf}}<small>Preliminary version in EUROCRYPT 2006.</small>
*{{cite book |last=Micciancio |first=Daniele |chapter=Improving Lattice Based Cryptosystems Using the Hermite Normal Form |title=Cryptography and Lattices |series=Lecture Notes in Computer Science |volume=2146 |pages=126–145 |year=2001 |publisher=Springer |doi=10.1007/3-540-44670-2_11 }}

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

GGH encryption scheme - Revision history

imported>WikiCleanerBot: v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)