NTRUサイン

NTRUSignは、 NTRU 署名アルゴリズムとも呼ばれ、 GGH 署名方式に基づくNTRU 公開鍵暗号 デジタル署名アルゴリズムです。NTRUSign のオリジナル バージョンは、多項式認証および署名スキーム( PASS ) であり、CrypTEC'99 で公開されました。^[1] PASS の改良バージョンは NTRUSign と命名され、Asiacrypt 2001 のランプ セッションで発表され、 RSA Conference 2003で査読済みの形式で公開されました。 ^[2] 2003 年の公開では、80 ビット セキュリティのパラメータ推奨事項が含まれていました。その後の 2005 年の公開では、80 ビット セキュリティのパラメータ推奨事項が改訂され、 112、128、160、192、および 256 ビットのセキュリティ レベルを実現するパラメータが提示され、任意のセキュリティ レベルでパラメータ セットを導出するアルゴリズムが説明されました。NTRU Cryptosystems, Inc. は、このアルゴリズムの特許を申請しています。

NTRUSign は、メッセージを 2 N次元空間のランダムな点にマッピングします。ここでNはNTRUSign パラメータの 1 つであり、NTRUEncrypt格子に密接に関連する格子内の最も近いベクトル問題を解きます。NTRUSign は、低セキュリティ レベルではこれらのアルゴリズムよりも高速であり、高セキュリティ レベルでは大幅に高速であると主張されています。ただし、分析により、元のスキームは安全ではなく、秘密鍵の情報が漏洩する可能性があることが示されました。^{[3] [4]}

再設計されたpqNTRUSignは、 NISTポスト量子暗号標準化コンペティションに提出されました。^[5]これは「ハッシュアンドサイン」（フィアット・シャミール変換とは対照的）手法に基づいており、より小さな署名サイズを実現すると主張しています。

NTRUSign は、 IEEE P1363ワーキング グループによって標準化が検討されています。^{[引用が必要]}

2000年にWu、Bao、Ye、Dengは、NTRUSignのオリジナルバージョンであるPASSの署名は、秘密鍵を知らなくても簡単に偽造できることを実証しました。^{[6] NTRUSignは}ゼロ知識署名方式ではなく、署名の転写により秘密鍵に関する情報が漏洩することが、GentryとSzydloによって最初に観察されました。^[3] NguyenとRegevは2006年に、元の乱されていないNTRUSignパラメータセットでは、攻撃者はわずか400の署名で秘密鍵を復元できることを実証しました。^[4]

現在の提案では、署名者が署名自体を計算する前に、メッセージを表す点を小さな秘密量だけずらすことにより、秘密鍵を復元するために必要な転写の長さを増やすために摂動が使用されています。NTRU は、摂動された署名の転写によって有効な攻撃が可能になるまでには、少なくとも 2 ^{30 の}署名が必要であり、おそらくはそれ以上の数の署名が必要であると主張しました。2012 年には、摂動によるこの方式への攻撃が発表されましたが、標準的なセキュリティ パラメータでは数千の署名が必要でした。^[7]

pqNTRUSign は、指定されたパラメータ セットに対して 128 ビットの古典的および量子的なセキュリティを主張します。

• 複数のセキュリティ レベルのパラメータ セットを含む最新の NTRUSign 論文
• NTRUSign の Java 実装