ニーダーライター暗号システム

暗号学において、ニーダーライター暗号システムは、1986年にハラルド・ニーダーライターによって開発されたマケリス暗号システムのバリエーションです。^[1]これは、同じアイデアを線形コードのパリティ検査行列Hに適用します。セキュリティの観点から、ニーダーライターはマケリスと同等です。シンドロームを暗号文として使用し、メッセージはエラーパターンです。ニーダーライターの暗号化は、マケリスの暗号化よりも約10倍高速です。ニーダーライターは、デジタル署名スキームの構築に使用できます。

ニーダーライターの元の提案の特殊なケースは破られました^[2]が、バイナリゴッパコードと併用するとシステムは安全です。

1. アリスはt個の誤りを訂正できるバイナリ( n , k )線形ゴッパコードGを選択します。このコードは効率的な復号アルゴリズムを備えています。
2. アリスはコードGに対して( n − k )× nのパリティ検査行列Hを生成します。
3. アリスはランダムな( n − k )×( n − k )の2進非特異行列Sを選択します。
4. アリスはランダムなn × n 順列行列Pを選択します。
5. アリスは( n − k )× n行列Hpub = SHP^を計算します。
6. アリスの公開鍵は( Hpub , t )、秘密鍵は( ^S , H , P )です。

ボブが公開鍵が( H ^pub , t )であるアリスにメッセージmを送信したいとします。

1. ボブはメッセージm を、長さn、重みが最大tのバイナリ文字列 e ^m'としてエンコードします。
2. ボブは暗号文をc = H ^pub e ^Tとして計算します。

ボブからc = H ^pub m ^Tを受信すると、アリスはメッセージm を取得するために次の操作を実行します。

1. アリスはS ⁻¹ c = HPm ^Tを計算します。
2. アリスはGのシンドローム復号アルゴリズムを適用してPmTを^復元します。
3. アリスは、 m ^T = P ⁻¹ Pm ^Tを介してメッセージmを計算します。

Courtois、Finiasz、Sendrierは、Niederreiter暗号システムを使用して署名スキームを導出する方法を示しました。^[3]

1. 署名するドキュメントdをハッシュします（公開ハッシュ アルゴリズムを使用）。
2. このハッシュ値を暗号文のインスタンスであるかのように復号化します。
3. 復号化されたメッセージを署名としてドキュメントに追加します。

次に、検証では、公開暗号化関数を署名に適用し、これが文書のハッシュ値と等しいかどうかを確認します。Niederreiter を使用する場合、または実際にはエラー訂正コードに基づく任意の暗号システムを使用する場合、署名スキームの 2 番目の手順はほぼ常に失敗します。これは、ランダム シンドロームが通常、tよりも大きい重みのエラー パターンに対応するためです。次に、システムは、復号化できるものが見つかるまで d を調整する決定論的な方法を指定します。

コードパラメータの選択は、ランダムシンドロームがデコード可能な確率に関係しています。 Courtois、Finiaz、および Sendrier は、パラメータ値n = 2 ¹⁶およびt = 9 を提案しています。この場合、ランダムシンドロームをデコードする確率は です。したがって、デコード可能なシンドロームは、期待される試行回数 9! の後に見つかります。元の文書dにカウンタiを追加して、わずかに変更された文書d _iを作成します。d _{i を}ハッシュすると、 iに依存するシンドロームが得られます。iが 0 からi ₀まで実行され、i _{0 が}d _iがデコード可能な最初のiの値であるとします。この場合、復号化されたメッセージは、長さnで重みが 9 の単語zであり、Hz ^{T は}d _{i 0}のハッシュ値に等しくなります。署名は、検証のために値i _{0と組み合わせた}zになります。この署名は元の文書dに添付されます。 ${\displaystyle {\frac {1}{9!}}}$

• ヘンク・CA・ファン・ティルボルグ。暗号学の基礎、11.4。

• McEliece 暗号システムの攻撃と防御 Daniel J. Bernstein、Tanja Lange、Christiane Peters