🐡

McEliece暗号

3 min read

現在,専門にやっているMcEliece暗号についてです.この暗号方式が初めて提案されたのは,

R. J. McEliece, “A public-key cryptosystem based on algebraic coding
theory,” Deep Space Network Progress, vol. 44, pp. 114–116, 1978.

です.符号理論に関するいくつかのNP困難な問題に安全性を根拠としています.このことは,

E. Berlekamp, R. McEliece, and H. van Tilborg, “On the inherent intractability of certain coding problems (corresp.),” Information Theory,
IEEE Transactions on, vol. 24, no. 3, pp. 384 – 386, may 1978.

などに書かれています.
初めの原論文では,Goppa符号という代数的な符号に限定しているのですが,今回は一般の符号に関して理論や実装を進めていくことにします(そっちの方が実装楽ですし).

以下,基本的な符号理論の知識(線型符号・Hamming重み・生成行列・最小距離・誤り訂正能力)は仮定します(いつか記事にまとめてここにリンク貼るかもです).

アルゴリズムの概要

McEliece暗号は次の3つ組のアルゴリズムから構成されます

Gen() = pk, sk
Enc(pk, m) = c
Dec(sk, c) = \tilde{m}

詳しく見ると,
Gen() = pk, sk
Input : ()
Output : 公開鍵 pk, 秘密鍵 sk

1:何らかの誤り訂正符号 C を選び,その生成行列を Gk \times n行列)とする
2:C の誤り訂正能力を t,復号アルゴリズムを Dcd とする
3:k 次の正則行列 Sn 次の置換行列 P をランダムに選ぶ
4:G_{pub} = S \times G \times P を計算する

return pk \leftarrow (G_{pub}, t), \ sk \leftarrow (S, G, P, Dcd)

Enc(pk, m) = c
Input : (pk, m) where m は平文で k 次元ベクトル
Output : 暗号文 c (n次元ベクトル)

Hamming重みが t なる n 次元ベクトル(エラーベクトル) e をランダムに生成する

return c \leftarrow mG_{pub} + e

Dec(sk, c) = m
Input : (sk, c)
Output : \tilde{m} where \tilde{m}k 次元ベクトル(m = \tilde{m} ならOK)

1:c^{\prime} = c P^{-1} を計算する
2:c^{\prime} = m S G + e P^{-1}e P^{-1} のHamming重みは t なので,C で誤り訂正ができ,w = Dcd(c^{\prime}) = m S G とできる
3:m^{\prime} G = w になる m^{\prime} を求める

return \tilde{m} \leftarrow m^{\prime} S^{-1}

Decの2がポイントですね.これによって,Encapsでのエラーベクトルを訂正できる,ということになります.

実装

以下,実装についてですが,直書きがとても長くなりそうな予感がしたので,URLで代替します.

https://github.com/awlaplace/research_implementation/tree/master/McEliece

こちらの McEliece_py.py が上記3つのアルゴリズムの実装になります.
本当はC言語でも実装したかったのですが,行列の扱いが少し厄介なのと,Pythonの方が行列のモジュールが豊富で実装しやすかったので,こちらでやってみました.

正当性

要するに m = \tilde{m} となればOKです.
ただ,基本的な式変形は Dec で示しているので,気になる点は,
\bullet e P^{-1} のHamming重みは t
\bullet c^{\prime}C で誤り訂正ができる
\bullet m^{\prime} G = w になる m^{\prime} が存在する
この3つになります.

\bullet e P^{-1} のHamming重みは t
P とは置換行列のことでしたが,置換行列の逆行列は置換行列になります.置換行列の任意の列はある行の要素が1でそれ以外が0なので,e のHamming重みは e P^{-1} のHamming重みと等しくなります.ここで,e のHamming重みは t だったので,e P^{-1} のHamming重みも t です.

\bullet c^{\prime}C で誤り訂正ができる
C の誤り訂正能力は t でした.また,c^{\prime} = m S G + e P^{-1} であり,m S GC の符号語なので,1つ前の \bullet と合わせると, c^{\prime} のHamming重みは t なので,これもOKです.

\bullet m^{\prime} G = w になる m^{\prime} が存在する
G は生成行列だったので,フルランクです.よって,各行は1次独立なので,このような m^{\prime} は存在すれば一意だと分かります.そして,w = m S G でしたから,m^{\prime} = m S として取ればOKです.

まとめ

McEliece暗号そのものを研究しているわけではないのですが,元祖って感じがしました(こなみ).
今後はこんな感じで色々な耐量子暗号を紹介していこうと考えています.理論的なこともできるだけやっていきたいのですが,安全性の証明とかは長すぎて突っ込めないので,今回みたいに正当性ぐらいかなと思いますが・・・.

参考文献

\bullet 縫田光司. 耐量子計算機暗号. 森北出版 株式会社, 2020.

Discussion

ログインするとコメントできます