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よりもはるかに容易に解ける特別な最近接ベクトル問題に変換できることを示しました。

実装

• TheGaBr0/GGH – GGH暗号システムとその最適化された変種であるGGH-HNFのPython実装。^[2]このライブラリには、鍵生成、暗号化、復号、基本的な格子縮約技術、そして既知の攻撃のデモが含まれています。教育および研究目的で使用されており、PyPIから入手できます。

参考文献

1. Phong Nguyen. Crypto '97 に掲載された Goldreich-Goldwasser-Halevi 暗号システムの暗号解読. CRYPTO, 1999
2. ミッチアンチョ, ダニエル. (2001). エルミート正規形を用いた格子ベース暗号システムの改良. LNCS. 2146. 10.1007/3-540-44670-2_11.

参考文献

• Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai (1997). 「格子縮約問題からの公開鍵暗号システム」. CRYPTO '97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology . London: Springer-Verlag. pp.  112– 131.
• Nguyen, Phong Q. (1999). 「Crypto '97 における Goldreich–Goldwasser–Halevi 暗号システムの暗号解読」. CRYPTO '99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology . London: 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 の暫定バージョン。
• ミッチアンチョ, ダニエレ (2001). 「エルミート正規形を用いた格子ベース暗号システムの改良」.暗号と格子. コンピュータサイエンス講義ノート. 第2146巻. シュプリンガー. pp.  126– 145. doi :10.1007/3-540-44670-2_11.