GGH 暗号方式

L ⊂ ℝ² を、以下のような基底 B とその逆 B⁻¹ をもつ格子とする。

${\displaystyle B={\begin{pmatrix}7&0\\0&3\\\end{pmatrix}}}$, ${\displaystyle B^{-1}={\begin{pmatrix}{\frac {1}{7}}&0\\0&{\frac {1}{3}}\\\end{pmatrix}}}$

くわえて、

${\displaystyle U={\begin{pmatrix}2&3\\3&5\\\end{pmatrix}}}$ および

${\displaystyle U^{-1}={\begin{pmatrix}5&-3\\-3&2\\\end{pmatrix}}}$

とすると、以下を得る。

${\displaystyle B'=UB={\begin{pmatrix}14&9\\21&15\\\end{pmatrix}}}$

平文を m = (3, −7) とし、誤差を e = (1, −1) とすると、以下のように暗号文を得る。

${\displaystyle c=mB'+e=(-104,-79)}$

これを復号するには、次の計算を行う。

${\displaystyle cB^{-1}=\left({\frac {-104}{7}},{\frac {-79}{3}}\right)}$

これを丸めると (−15, −26) が得られ、次のように平文を得ることができる。

${\displaystyle m=(-15,-26)U^{-1}=(3,-7)}$

1999年、Nguyen は国際会議 Crypto にて GGH 暗号方式には方式設計上の欠陥があることを示した。暗号文から平文の一部が漏れること、および、GGH暗号の復号問題が、一般の最近ベクトル問題よりも格段に容易な特別の最近ベクトル問題に帰着できることが示された。

• Oded Goldreich, Shafi Goldwasser, and Shai Halevi. Public-key cryptosystems from lattice reduction problems. In CRYPTO ’97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, pages 112–131, London, UK, 1997. Springer-Verlag.
• Phong Q. Nguyen. Cryptanalysis of the Goldreich–Goldwasser–Halevi Cryptosystem from Crypto ’97. In CRYPTO ’99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, pages 288–304, London, UK, 1999. Springer-Verlag.