この記事は EAGLYS Advent Calendar 2022 の９日目の記事です

前回は，符号ベース暗号の概要や符号理論についてでしたが，今回は符号ベース暗号の大枠を掴んで，Information Set Decoding アルゴリズムまで触れようと思います

この辺りの話は
草川恵太 : 耐量子計算機暗号の研究動向調査報告書第３章符号に基づく暗号技術, CRYPTREC, 2019.

草川恵太（NTT社会情報研究所） : 耐量子計算機暗号の解説～符号暗号を中心として～, SITA2021, 2021

成定真太郎（KDDI総合研究所） : 符号暗号の高速求解手法の実装に向けて, 耐量子計算機暗号と量子情報の数理, 2022
がめちゃくちゃ詳しいので，本記事ではざっくり書きます

突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください

連載記事の構成

今回のアドカレの関連記事（気になるところから読んでください）

符号ベース暗号の概要
２日目（符号ベース暗号に入門する（前半））：符号ベース暗号の概要, 符号理論の概要
９日目（イマココ）（符号ベース暗号に入門する（後半））：シンドローム復号問題, McEliece暗号, Information Set Decoding アルゴリズム

符号ベース暗号を用いた準同型暗号の構成
16日目（符号ベース暗号を用いた準同型暗号の構成（前半））：Reed-Muller符号の定義, 具体例, 実装
23日目（符号ベース暗号を用いた準同型暗号の構成（後半））：Reed-Muller符号の性質, 準同型暗号の定義, 既存方式の紹介

シンドローム復号問題

シンドローム復号問題（以下SDP）とは，次のような問題です

$n, k, w$ を正整数，$H \in \mathbb{F}_2^{(n - k) \times n}, s \in \mathbb{F}_2^{n - k}$ とするとき，$He = s$ かつ $\mathrm{wt}(e) = w$ なる $e \in \mathbb{F}_2^{n}$ を求めよ

この問題は Berlekamp らによって，NP完全であることが知られています
＊E. Berlekamp, R. McEliece, H. V. Tilborg: ``On the inherent intractability of certain coding problems (corresp.)'', Information Theory, IEEE Transactions on, vol.24(3), pp.384-386, May, 1978.

次で紹介するMcEliece暗号の安全性の根拠となっている問題です
＊といってもそのような問題はたくさんあり，それは草川恵太 : 耐量子計算機暗号の研究動向調査報告書第３章符号に基づく暗号技術, CRYPTREC, 2019. を参照してください

SDPがどう難しいかについての大枠ですが，
LWE問題をご存知の方は，あの問題はノイズが全て0の場合は簡単に解けます
そして，SDPで $\mathrm{wt}(e) = w$ の条件を外すと，ノイズが全て0のLWE問題と同じです（考えている体は同じとして）

そこからどのような条件を加えるかですが，未知数を増やしたのがLWE，解に条件を加えたのがSDPという感じです

あとは，Information Set Decoding アルゴリズムの箇所で具体例を見たら，どのぐらい難しいか直感でわかると思います

McEliece暗号

R. J. McEliece: ``A public-key cryptosystem based on algebraic coding theory'',Deep Space Network Progress Report, vol.44, pp.114-116, Jan, 1978.

先に謝罪しておくと，タイトル詐欺をしています
McEliece暗号というと，一般には公開鍵暗号方式を指す（ように思える）のですが，今回扱うのは共通鍵暗号方式だからです
＊公開鍵は今回の連載で使わないため
＊ですが，一応最後に公開鍵だとどんな感じなのかは軽く記載します

一般的な定義は，他の書籍・資料が素晴らしいので，そちらを参照してください
＊以前にMcElice暗号の記事は実装付きで書いたのですが，ちょっと色々あって現在非公開なので，公開できるようになったら追記します

本記事では，前回のHamming符号を使って，ふわっと理解することを目標にします

Alice, Bob は共に前回のHamming符号に対する生成行列とparity検査行列を知っているものとします
前回のHamming符号に対する生成行列 $G$ は次のようなものでした:

\begin{pmatrix}
1 & 1 & 0 & 1 & 0 & 0 & 1 \\
0 & 1 & 0 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 
\end{pmatrix}

Alice は，平文として，$(0, 0, 1, 1)$ をとって，符号語 $(0, 0, 1, 1)G = (1, 1, 1, 0, 0, 0, 0)$ を考えます
＊これが前回の符号の符号語になっていることは，前回の記事からわかります

ここで，符号語にあえてノイズを加えて，$(1, 1, 1, 0, 0, 0, 1)$ として，これを暗号文とします

（今回は通信路上にノイズが発生しない仮定のもとで）AliceはBobへ $(1, 1, 1, 0, 0, 0, 1)$ を送信し，Bobは前回の記事の手順から $(1, 1, 1, 0, 0, 0, 0)$ に復号（符号化に対する復号）できます

あとは，$xG = (1, 1, 1, 0, 0, 0, 0)$ なる $x \in \mathbb{F}_2^4$ を考えて，$x = (0, 0, 1, 1)$ を復号（暗号化に対する復号）できます

ポイントとしては，符号理論でノイズとして考えていた部分を，符号語にあえて加えることで暗号文にしているところです

なんか流れがLWE問題を使ったやつっぽいな・・・と思われた方は，その直感はおそらく正しくて，このフレームワークを使って，次の記事から，符号ベース暗号を使った準同型暗号を構成します

ちなみに公開鍵暗号方式では，生成行列に対して，$\mathbb{F}_2$ 上の可逆行列や置換行列を掛けたものを公開鍵として，生成行列や可逆行列，置換行列，（今なら）parity検査行列を秘密鍵とすれば構成できます（が，詳しいことは今回は触れません）

Information Set Decoding アルゴリズム

McEliece暗号に対する攻撃アルゴリズムで有名なものとして，Information Set Decoding アルゴリズム（ISDアルゴリズム）を紹介します
＊情報集合復号アルゴリズム，ということもできますが，ISDアルゴリズムで統一します

こちらの攻撃は，暗号文や平文に注目するのではなく，直接シンドローム復号問題を解こうとするアプローチによるものです

Prange が1962年に初めて提唱したものになります
E. Prange: "The use of information sets in decoding cyclic codes", Information Theory, IRE Transactions on, vol.8(5), pp.5–9, september, 1962.

ISDアルゴリズムにはさまざまな派生があり，大雑把に次のようなものがあります

年	アルゴリズム名	論文名
1962	Prange	E. Prange: "The use of information sets in decoding cyclic codes", Information Theory, IRE Transactions on, vol.8(5), pp.5–9, september, 1962.
1991	Dumer	I. Dumer: "On minimum distance decoding of linear codes", In Proc. 5th Joint Soviet-Swedish Int, Workshop Information Theory, pp.50–52, 1991.
2011	MMT	A. May, A. Meurer, E. Thomae: "Decoding random linear codes in $\tilde{\mathcal{O}}(2^{0.054n})$", In International Conference on the Theory and Application of Cryptology and Information Security, pp.107–124, 2011.
2012	BJMM	A. Becker, A. Joux, A. May, A. Meurer: "Decoding random binary linear codes in $2^{n/20}$: How 1 + 1 = 0 improves information set decoding", In Annual international conference on the theory and applications of cryptographic techniques, pp.520–536, 2012.

他にも Nearest-Neighbor を使った2015年のMO, 2018年のBMアルゴリズムや estimator に関する研究，ISDアルゴリズムを並列化することで高速化する研究など様々あります
＊最後の並列化の話が冒頭で紹介した成定真太郎（KDDI総合研究所） : 符号暗号の高速求解手法の実装に向けて, 耐量子計算機暗号と量子情報の数理, 2022
＊この辺の流れはいつしかきっちりとまとめてみたいものですね~~研究背景とかで書かないといけないので~~

大雑把にPrangeのアルゴリズムの方針を説明します

$He = s$ かつ $\mathrm{wt}(e) = w$ を満たす $e \in \mathbb{F}_2^n$ というのは，
$H$ の $n$ 列のうち，どの $w$ 列を選んで，その $\mathbb{F}_2^n$ 上での値が $s$ と一致するか？という問題と同値です．

要するに $e = (e_1, \cdots, e_n)$ で $1 \leq i \leq n$ とするとき，

$e_i = 1$ なら $H$ の $i$ 番目の列を選んで，$e_i = 0$ なら選ばない
1のようにして $w$ 列選ぶ
2で選んだ列のXORの値が $s$ に一致するなら，1のようにして $e$ を構成する

という流れになります

例えば，$n = 4, k = 1, w = 3$ で

H = \begin{pmatrix}
1 & 1 & 0 & 0 \\
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 1
\end{pmatrix}, \ 
s = (1, 1, 1)

とすると，$e = (1, 0, 1, 1)$ です
$e = (1, 0, 1, 1)$ になることが，$H$ の1,3,4列目のXORの値が $s$ と一致することに対応しています

$n$ 列のうち $w$ 列を選ぶのは，$\binom{n}{w}$ 通りだけあります
実は，$e$ の選び方として，$\min${$\binom{n - k}{w}, 2^{n - k}$} だけあるので，（$\binom{n - k}{w} < 2^{n - k}$ のとき）ランダムに $w$ 列を選んでも期待値として $\binom{n}{w} / \binom{n - k}{w}$ 回の試行回数で $e$ を得られます

$\binom{n}{w} / \binom{n - k}{w}$ は（$w$に適切な仮定を入れると）$2^{0.121n}$ ぐらいになります
ですから上の具体例だと $n = 4$ なので，$H$ の4列のうちランダムに3列選ぶことを繰り返すと，$2^{0.484} \approx 2^{0.5} = \sqrt{2}$ ぐらいの期待値の回数で $e$ を選べます

これを扱いやすく定式化すると，$n \times n$ 置換行列全体からランダムに置換行列 $P$ を選んで，
行列 $HP$ に対して，Gaussの消去法を行う行列を $U$ とするとき，$Us$ と $0^k$ を連結したものが $e$ となります

最初に紹介した Dumer, MMT, BJMM はもう少しこれらの行列に細工を入れて，探索回数を減らしたアルゴリズムです

ISDアルゴリズムには，量子版もあり，PrangeのアルゴリズムとGroverのアルゴリズムを組合わせたBernsteinのアルゴリズムとか，
MMT/BJMMアルゴリズムとGrover, 量子walk探索アルゴリズムを組合わせた量子MMT/BJMMアルゴリズムなどがあります

量子ISDアルゴリズムの参考文献

D. J. Bernstein: ``Grover vs. McEliece'', In International Workshop on Post-Quantum Cryptography, pp.73–80, Springer, 2010.

G. Kachigar, J. P. Tillich: ``Quantum information set decoding algorithms'', In International Workshop on Post-Quantum Cryptography, Lecture Notes in Computer Science, vol.10346, pp.69–89, Springer, 2017.

＊ちなみに筆者は，コンピュータセキュリティシンポジウム (CSS)2022にて，この辺りのテーマを題材にした発表をしました

まとめ

今回はSDP, 符号ベース暗号の枠組み, ISDアルゴリズムの紹介をしました

ISDアルゴリズムはちょっと前までがっつりやっていたので，全然書き足りないですね・・・
特に量子ISDアルゴリズムはしっかり書いてみてもいいかなぁと思っています~~自分の研究分野の紹介もしたいですし~~

最近までrank符号をやっていたので久々にって感じでしたが，符号ベース暗号の中でもISDアルゴリズムは今でもかなり盛んに行われています

今までHamming符号しかやっていませんでしたが，次回からはReed-Muller符号というものを扱って，今回の符号ベース暗号の枠組みと絡めて，準同型暗号の構成に繋げていきます

今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！

参考文献

萩原学 : 符号理論　デジタルコミュニケーションにおける数学, 日本評論社, 2012.
D. J. Bernstein, J. Buchmann, E. Dahmen: Post-Quantum Cryptography, Springer-Verlag, 2009.
縫田光司 : 耐量子計算機暗号, 森北出版, 2020.