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: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology . London: 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 の暫定バージョン。

外部リンク

• 原論文のウェブページ