ニーダーライター暗号

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

スキーム定義

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

鍵生成

1. アリスは、 t個の誤りを訂正できる2値( 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] [4]}

1. を計算します。ここで、はハッシュ関数、は署名された文書です。 ${\displaystyle s=h(d)}$ ${\displaystyle h}$ ${\displaystyle d}$
2. を計算します。ここで は連結を表します。 ${\displaystyle s_{i}=h(s|i),i=0,1,2,\dots }$ ${\displaystyle |}$
3. 復号化可能な（以降 と表記）の最小値が見つかるまで復号化を試みます。 ${\displaystyle s_{i}}$ ${\displaystyle i}$ ${\displaystyle i_{0}}$ ${\displaystyle s_{i}}$
4. トラップドア関数を使用して、 （は公開鍵）となるように計算します。 ${\displaystyle z}$ ${\displaystyle Hz^{T}=s_{i_{0}}}$ ${\displaystyle H}$
5. 重み 9 の単語の空間内の のインデックスを計算します。 ${\displaystyle I_{z}}$ ${\displaystyle z}$
6. 署名として使用します。 ${\displaystyle \left[I_{z}|z\right]}$

検証アルゴリズムははるかにシンプルです。

1. インデックスから回復します。 ${\displaystyle z}$ ${\displaystyle I_{z}}$
2. 公開鍵を使って計算します。 ${\displaystyle s_{1}=Hz^{T}}$ ${\displaystyle H}$
3. 計算します。 ${\displaystyle s_{2}=h(h(d)|i_{0})}$
4. とを比較します。同じであれば署名は有効です。 ${\displaystyle s_{1}}$ ${\displaystyle s_{2}}$

のインデックスは以下の式で導出できます。ここで、は の非ゼロビットの位置を表します。格納に必要なビット数は削減できません。平均すると ビット長になります。 を格納するために必要な平均ビット数と合わせると、署名は平均ビット長になります。 ${\displaystyle I_{z}}$ ${\displaystyle z}$ ${\displaystyle i_{1}<\dots <i_{9}}$ ${\displaystyle z}$ $${\displaystyle I_{z}=1+\sum _{n=1}^{9}{\binom {i_{n}}{n}}}$$ ${\displaystyle i_{0}}$ ${\displaystyle log_{2}(9!)\approx 18.4}$ ${\displaystyle 125.5}$ ${\displaystyle I_{z}}$ ${\displaystyle 125.5+18.4\approx 144}$

参考文献

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

1. H. Niederreiter (1986). 「ナップサック型暗号システムと代数的符号理論」.制御情報理論の問題. Problemy Upravlenija I Teorii Informacii . 15 : 159– 166.
2. VM Sidel'nikov & SO Shestakov (1992). 「一般化リード・ソロモン符号に基づく暗号システムの安全性について」.離散数学と応用. 2 (4): 439– 444. doi :10.1515/dma.1992.2.4.439. S2CID  120779674.
3. N. Courtois、M. Finiaz、N. Sendrier (2001). 「McElieceベースのデジタル署名方式の実現方法」. Advances in Cryptology — ASIACRYPT 2001 . Lecture Notes in Computer Science. Vol. LNCS 2248. pp.  163– 164. doi : 10.1007/3-540-45682-1_10 . ISBN 978-3-540-42987-6。
4. Makoui, Farshid Haidary; Gulliver, Thomas Aaron; Dakhilalian, Mohammad (2022年12月17日). 「McEliece暗号システムに基づく新しいコードベースデジタル署名」. IET Communications . 17 (10). Institution of Engineering and Technology (2023年4月6日発行): 1199– 1207. doi : 10.1049/cmu2.12607 .

外部リンク

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

「https://en.wikipedia.org/w/index.php?title=Niederreiter_cryptosystem&oldid=1300158296」から取得