GGH 暗号方式

Goldreich–Goldwasser–Halevi (GGH) 格子暗号方式とは、格子に基づく非対称方式のひとつである。GGH 署名方式も存在する。

Goldreich–Goldwasser–Halevi (GGH) 暗号方式では、最近ベクトル問題の困難性を利用している。格子基底縮小の難しさに依存する落とし戸付き一方向関数を用いており、1997年に Oded Goldreich, Shafi Goldwasser, Shai Halevi により発表された。この一方向性関数は、格子の基底が与えられたときに格子点の近くのベクトルを生成するのは簡単だが（例えば格子点を選んで小さな誤差ベクトルを足せばよい）、この誤差を含んだベクトルから元の格子点を得るには特別な基底が必要である、というアイデアに基づいている。

GGH 暗号は Phong Q. Nguyen により1999年に暗号解読された。

暗号方式

鍵生成

GGH 暗号では、次の秘密鍵と公開鍵を用いる。

秘密鍵は，格子 $L$ の"良い性質を持つ"基底 $B$ と、ユニモジュラ行列 $U$ である。"良い性質"とは、基底が短く、ほとんど直交しているなどの性質である。

公開鍵は、格子 L の別の基底 $B'=UB$ である。

暗号化

平文空間は一定の M に対して −M < λ_i < M を満たす整数ベクトル (λ₁, ..., λ_n) である。

平文が m = (λ₁, ..., λ_n) 、公開鍵が $B'=(b'_{1},\ldots ,b'_{n})$ であるとき、まず次のように計算する。

$v=\sum \lambda _{i}b_{i}'$

これは行列記法を使えば以下のように書ける。

$v=m\cdot B'$

$m$ が整数値からなり、各 $b'_{i}$ が格子点であるから、 $v$ も格子点となる。次に、小さな誤差ベクトル $e$ を選び、暗号文は次のように計算される。

$c=v+e=m\cdot B'+e$

復号

暗号文を復号するには、次のように計算する。

$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}$

$e\cdot B^{-1}$ が十分に小さいならば、Babai 丸め法を用いることでこの項を除去することができる。最終的に次のように平文を計算できる。

$m=m\cdot U\cdot U^{-1}$

例

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

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

くわえて、

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

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

とすると、以下を得る。

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

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

$c=mB'+e=(-104,-79)$

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

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

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

$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.