GGH署名スキーム

Goldreich -Goldwasser-Halevi (GGH) 署名方式は、 1995 年に提案され、1997 年に公開されたデジタル署名方式で、格子内の最近接ベクトル問題(CVP)を解くことに基づいています。署名者は、メッセージを表す点の CVP を解決するために格子の適切な基底を使用することで、格子の適切な基底に関する知識を証明します。検証者は、同じ格子の不適切な基底を使用して、検討中の署名が実際に格子点であり、メッセージ点に十分近いことを検証します。

このアイデアは元の論文では詳細に説明されておらず、関連する暗号化アルゴリズムに重点が置かれていました。

GGH 署名は、 NTRUSign署名アルゴリズムの基礎となります。

Phong Q. Nguyen  [fr]とOded Regev は、 2006 年にオリジナルの GGH 署名方式 を暗号解読 (破る) しました。

• Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai (1997)。「格子縮約問題からの公開鍵暗号システム」。CRYPTO '97: 暗号学の進歩に関する第 17 回国際暗号学年次会議議事録。ロンドン: Springer-Verlag。pp. 112–131。
• 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 の暫定バージョン。

• 原論文のウェブページ