GGH暗号化方式

ゴルトライヒ・ゴルトヴァッサー・ハレヴィ（GGH） 格子ベース 暗号システムは、格子に基づく破られた非対称暗号システムです。 2024年現在、破られていない GGH署名方式もあります。

Goldreich–Goldwasser–Halevi (GGH) 暗号システムは、最近接ベクトル問題が困難な問題になり得る という事実を利用しています。このシステムは、1997 年にOded Goldreich、Shafi Goldwasser、Shai Haleviによって発表され、格子簡約の困難さに依存するトラップドア一方向関数を使用しています。このトラップドア関数に含まれるアイデアは、格子の基底が与えられれば、格子点に近いベクトルを簡単に生成できるというものです。たとえば、格子点を取り、小さな誤差ベクトルを追加します。ただし、この誤ったベクトルから元の格子点に戻るには、特別な基底が必要です。

GGH暗号化方式は1999年にPhong Q. Nguyen  [fr]によって解読（破）されました。NguyenとOded Regevは2006年に、 関連するGGH署名方式を解読しました。

GGH には秘密鍵と公開鍵が必要です。

秘密鍵は、優れた特性（短いほぼ直交ベクトルなど）とユニモジュラ行列を持つ格子の基底です。 ${\displaystyle B}$${\displaystyle L}$ ${\displaystyle U}$

公開鍵は、フォームの格子のもう 1 つの基礎です。 ${\displaystyle L}$${\displaystyle B'=UB}$

ある選択された M に対して、メッセージ空間は範囲 のベクトルで構成されます。 ${\displaystyle (m_{1},...,m_{n})}$${\displaystyle -M<m_{i}$

メッセージ、エラー、公開鍵が与えられ た場合、${\displaystyle m=(m_{1},...,m_{n})}$${\displaystyle e}$${\displaystyle B'}$

${\displaystyle v=\sum m_{i}b_{i}'}$

行列表記ではこれは

${\displaystyle v=m\cdot B'}$。

は整数値で構成され、格子点なのでvも格子点です。暗号文は次のようになります。 ${\displaystyle m}$${\displaystyle b'}$

${\displaystyle c=v+e=m\cdot B'+e}$

暗号文を解読するには、

${\displaystyle 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}}$

ババイの丸め技法は、十分に小さい限り 項を除去するために使用されます。最後に計算します。${\displaystyle e\cdot B^{-1}}$

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

メッセージを受け取ります。

を基底とその逆元を持つ格子とする${\displaystyle L\subset \mathbb {R} ^{2}}$${\displaystyle B}$${\displaystyle B^{-1}}$

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

メッセージを、エラーベクトルをとすると、暗号文は次のようになります。 ${\displaystyle m=(3,-7)}$${\displaystyle e=(1,-1)}$

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

解読するには計算する必要がある

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

これを丸めてメッセージは次のように復元されます。 ${\displaystyle (-15,-26)}$

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

1999年、グエン^[1] はGGH暗号化方式の設計に欠陥があることを示しました。彼は、すべての暗号文が平文に関する情報を明らかにし、復号化の問題は一般的なCVPよりもはるかに簡単に解決できる 特別な最近接ベクトル問題に変換できることを示しました。

• Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai (1997)。「格子縮約問題からの公開鍵暗号システム」。CRYPTO '97: 暗号学の進歩に関する第 17 回国際暗号学年次会議議事録。ロンドン: Springer-Verlag。pp. 112–131。
• Nguyen, Phong Q. (1999)。「Crypto '97 の Goldreich–Goldwasser–Halevi 暗号システムの暗号解析」。CRYPTO '99: 暗号学の進歩に関する第 19 回国際暗号学会議の議事録。ロンドン: Springer-Verlag。pp. 288–304。
• Nguyen , Phong Q.; Regev, Oded (2008 年 11 月 11 日)。「平行六面体の学習: GGH および NTRU 署名の暗号解析」(PDF)。Journal of Cryptology。22 ( 2 ): 139–160。doi  : 10.1007/ s00145-008-9031-0。eISSN 1432-1378。ISSN 0933-2790。S2CID  2164840  。EUROCRYPT 2006 の暫定バージョン。