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

日本語での符号ベース暗号の記事が少ないので，現在符号ベース暗号を研究している（たぶんこれからも研究する）身から色々と書こうと思います

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

更新履歴
12/15：連載記事の構成, 符号ベース暗号の概要「参考文献」, Hamming符号の生成行列を追記

連載記事の構成

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

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

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

符号ベース暗号の概要

符号ベース暗号とは

大雑把には，符号理論の中で難しい問題を安全性の根拠としている暗号のことです
＊難しい問題，として，後半の記事でシンドローム復号問題を紹介します

後半の記事で触れますが，符号ベース暗号は，1978年のMcEliece暗号をベースとしていて，なんとRSA暗号とほぼ同時期に提案されています

なんですが，いまだに量子計算機で簡単に（多項式時間で）解けるアルゴリズムが知られていないこともあり，耐量子計算機暗号（以下PQC）の候補の１つと考えられています
＊PQC云々は昨年のアドカレもご参考を耐量子計算機暗号ってどの方式が人気なの？符号ベース暗号は？調べてみました！

他のPQCとの比較

PQCには他にも種類があり，有名どころとしては，格子暗号・多変数多項式暗号・同種写像暗号・ハッシュベース暗号，などがあります

格子暗号と符号ベース暗号の呼び方

lattice-based cryptography を和訳して格子暗号・code-based cryptography を和訳して符号ベース暗号なのは，おかしいんじゃないかって言われたことがあります（~~先に結論を書くとマジでどうでも良いんですが・・・~~）

修正するなら，格子ベース暗号とはあまり言われない印象なので，符号暗号なのかなって思いますが，符号暗号って何言っているかよく分からない気がするんですよね・・・

これだけ種類があってプレイヤー（研究している人）が均等かっていうと全くそんなことはなく，日本だと格子暗号・多変数多項式暗号・同種写像暗号のプレイヤーが多い気がします
＊要するに符号ベース暗号はプレイヤーが（検閲済）

ですが，格子暗号をメインにやっていてサブで符号ベース暗号とか，多変数多項式暗号をメインにやっていてサブ符号ベース暗号，みたいな方もよく見かけます
メインで符号ベース暗号をやっている人がめちゃ少ないんですよね・・・

最新の動向

NIST PQC 第4ラウンドに符号ベース暗号の3方式が残っています
＊NIST PQC 第4ラウンドの詳しい話はまた別の記事で

BIKE
Classic McEliece
HQC

アルゴリズムなどより詳しい話題は後半の記事で扱います（たぶん）

教科書とか

正直，符号ベース暗号で（網羅的に）参考にできる書籍は少なく，現状だと

Post-Quantum Cryptography
耐量子計算機暗号

ぐらいでしょうか・・・（もし他にご存知の方がいらっしゃいましたら，ご教授願いします）

また，符号ベース暗号の暗号方式を深くやろうとすると，そこで用いられる符号の深い知識は必要になることが多いです
例えば，LDPC符号という符号理論でよく用いられる符号がありますが，この符号をMcEliece暗号にナイーブに使った際に有名な攻撃が知られています
＊LDPC-McEliece は色々と論文がありますが，R. Misoczki, et al.: MDPC-McEliece: New McEliece variants from moderate density parity-check codes, In: 2013 IEEE international symposium on information theory. IEEE, pp.2069-2073, 2013.のイントロにその辺の内容や歴史が書かれています

ですので，一般的な符号理論の知識も必要なのかなと思います
その辺りは自分で使う符号の一般論を勉強する必要がありますが，線型代数や有限体・グラフ理論などに慣れていないと難しい場面もあるかもしれません

しかし，そもそも符号理論自体がよく分からん，符号ベース暗号って何ですかって方も決して多くないため，今回と次回の記事で本当に最低限の内容をまとめます

参考資料

書籍が少ない，とは書きましたが，参考になる資料が少ないわけではないため，色々と載せていこうと思います（ラストの参考文献以外で）

1.INRIAの講義的な, 2015.
2.草川恵太 : 耐量子計算機暗号の研究動向調査報告書第３章符号に基づく暗号技術, CRYPTREC, 2019.
3.草川恵太（NTT社会情報研究所） : 耐量子計算機暗号の解説～符号暗号を中心として～, SITA2021, 2021
4.成定真太郎（KDDI総合研究所） : 符号暗号の高速求解手法の実装に向けて, 耐量子計算機暗号と量子情報の数理, 2022

1 : 網羅的に色々書かれています（リンク先はビデオですが，頑張って探せばスライドのみの公開も見つかるはずです）
2 : 符号ベース暗号の安全性の根拠となっている問題の亜種や色々な暗号化方式を理解できます
3 : 第４ラウンドに残っている符号ベース暗号化方式がどのようなものか分かります
4 : ISDアルゴリズムをより深く理解できます

1→2→4→3の順で読むと綺麗に理解できると思います

海外だとINRIAというフランスの研究機関が符号ベース暗号にかなり強いので，この辺りで探してみるのもいいかもしれません（~~そのおかげでたまにフランス語の論文にエンカウントしますが~~）

符号理論の概要

通信上でAliceがBobへメッセージを送るときのことを考えます
＊AliceとかBobって何で出てくるのって思った方はアリスとボブを参照してください，日本語の正式な書類で出てくる甲とか乙です

Aliceがメッセージを送って，通信路を通るときにノイズが発生して，Bobの受け取ったメッセージがAliceが送信したメッセージと異なるものであるときがあります
＊今回考えるノイズは付加的なものだけで，削除とか挿入とかは考えないものとします

簡単な例としては，Aliceが「010」というメッセージを送ったのに，Bobの受け取ったメッセージが「011」だったとかそういうことですね

とても簡単な解決法として，「010」というメッセージをAliceがBobへ送る際に，「010010010」と「010」を3回繰り返して送信する方法が考えられます
Bobが受け取ったメッセージが「010011010」であり，Bobは「送りたいメッセージが３回繰り返されている」ということを知っていた場合，送りたいメッセージは「010」なんだなとBobは分かります

しかし，上記の方法では色々と問題点もあります

上記の例で「011011011」とノイズが発生してしまったら，Bobは送りたいメッセージが「011」であったと認識してしまう
ノイズが多く発生する場合に備えて，送りたいメッセージを3回ではなく100回繰り返したメッセージで送信する，とかすると，メッセージのサイズが大きくなり通信路をかなり圧迫する

ではどうすればいいか・・・そんなあなたに符号理論です

代表的な符号

ここでは最も有名な符号として，Hamming符号を紹介します．まずは用語の導入とか前提の整理から．

前提知識

今回使う有限体

以下では，要素数（サイズ，位数）が $q$ である有限体を $\mathbb{F}_q$ と書くことにします．
まずは $\mathbb{F}_2$ を扱います．
また，$n$ を正整数として，$\mathbb{F}_2^n$ で $\mathbb{F}_2$ 上の $n$ 次元ベクトル空間（$\mathbb{F}_2$ の $n$ 個の直積）を表すものとします．

そして，$1 \leq i \leq n$ で $x_i$ で $x$ の $i$ 番目の要素を表すものとします．例えば，$x = (1, 0, 1) \in \mathbb{F}_2^3$ に対して，$x_1 = 1, x_2 = 0, x_3 = 1$ です．

このとき $\mathbb{F}_2^n$ と $\mathbb{F}_{2^n}$ を同一視することができます．$\mathbb{F}_{2^n}$ は，要素数が $2^n$ の有限体です．
これは，$x \in \mathbb{F}_2^n$ に対して，$\displaystyle \sum_{i = 1}^n x_i 2^{n - i}$ という変換で $\mathbb{F}_{2^n}$ の要素になるからです（逆も構成できて一対一対応する）．例えば，$x = (1, 0, 1) \in \mathbb{F}_2^3$ に対して，$1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 5$ となり，$\mathbb{F}_{2^3}$ の要素となっています．

Hamming重み

$x \in \mathbb{F}_2^n$ に対して，$\mathrm{wt}(x) = |${$i \ | \ x_i \neq 0$}$|$ とします．ここで，有限集合 $S$ に対して，$|S|$ で $S$ の要素の個数を表します．例えば，$x = (1, 0, 1) \in \mathbb{F}_2^3$ に対して，$x_1 = 1, x_2 = 0, x_3 = 1$ なので，$\mathrm{wt}(x) =|$ {$1, 3$} $| = 2$ です．
$\mathrm{wt}(x)$ を $x$ の Hamming 重みとか単に重みと言います
＊この記事（今回の連載記事）では，Hamming 重みしか扱いません

線型符号

$\mathbb{F}_2^n$ の部分空間を符号といい，符号の元を符号語といいます
部分空間なので，和で閉じています（$\mathbb{F}_2$なので，スカラー倍を考えなくていい）

例えば，$\mathbb{F}_2^4$ の符号の例として，{$(0, 0, 0, 0), (0, 1, 0, 1), (1, 0, 1, 0), (1, 1, 1, 1)$} があります

生成行列とparity検査行列

$\mathbb{F}_2^n$ の符号 $\mathcal{C}$ の次元が $k$ だとします（$\mathcal{C}$ の要素数が $2^k$）

このとき，$\mathcal{C}$ の（$\mathbb{F}_2$ 上の）基底に対して，それぞれのベクトルを縦に $k$ 本並べてできる $k \times n$ 行列を $\mathcal{C}$ の生成行列といいます
＊つまり，任意の $x \in \mathbb{F}_2^k$ に対して，$x G$ は符号語です

また，任意の符号語 $c \in \mathcal{C}$ に対して，$H c = 0$（$n - k$ 次元ベクトルとしての等号）なる $\mathbb{F}_2$ 上の $(n - k) \times n$ 行列をparity検査行列と言います
＊上記の条件から一般に $G H^t = 0$ （$k \times (n - k)$ 行列としての等号）が成り立ちます

短完全列をご存知の方は，次の定義の方がしっくりくるかもです（短完全列の定義はしません）

短完全列を用いた定義

$0 \rightarrow \mathbb{F}_2^{k} \rightarrow \mathbb{F}_2^{n} \rightarrow \mathbb{F}_2^{n - k} \rightarrow 0$ なる短完全列が存在するとき，$\mathbb{F}_2^{k} \rightarrow \mathbb{F}_2^{n}$ なる線型写像の表現行列を生成行列，$\mathbb{F}_2^{n} \rightarrow \mathbb{F}_2^{n - k}$ なる線型写像の表現行列をparity検査行列といい，生成行列の像（parity検査行列の核）を符号といいます

これまでのまとめ

メッセージを送る際には，

符号の構造をAliceとBobで事前に共有する
Aliceは送りたいメッセージを生成行列で符号語に変換する
Aliceは符号語をBobへ送信する
Bobは受け取ったメッセージを誤り訂正し，元のメッセージへ復号する

というステップを踏めば良いということになります

どのような符号があるのか
Bobはどのようにして誤り訂正を行うのか

について，次の章で有名な符号であるHamming符号を紹介します

Hamming符号

Hamming 符号は，次のparity検査行列で表される符号です（取り方は色々あります，今回は説明の都合上って感じで）

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

上の行列は $\mathbb{F}_2$ 上の $3 \times 7$ 行列であって，$1 \leq i \leq 7$ の $i$ 列目を $\mathbb{F}_2^3$ の要素とみると，

\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7
\end{pmatrix}

という $\mathbb{F}_{2^3}$ 上の $1 \times 7$ 行列に対応する行列です．
このようなparity検査行列をもつ符号を（$(7, 3)$-）Hamming 符号といいます．

例えば，$(1, 1, 1, 0, 0, 0, 0)$ は符号語です．それは，parity検査行列を $H$ としたとき，$H(1, 1, 1, 0, 0, 0, 0) = (0, 0, 0)$ となるためです（実際に確かめてみてください）．

では，$(1, 1, 1, 0, 0, 0, 0)$ に対して，$(1, 1, 1, 0, 0, 0, 1)$ という誤りが発生したとします．このとき，$H(1, 1, 1, 0, 0, 0, 1) = (1, 1, 1)$ となります．$(1, 1, 1)$ は $\mathbb{F}_2^3$ の要素なので，$\mathbb{F}_{2^3}$の要素に変換すると，7になります．
また，$(1, 0, 1, 0, 0, 0, 0)$ という誤りが発生したとします．このとき，$H(1, 0, 1, 0, 0, 0, 0) = (0, 1, 0)$ となります．$(0, 1, 0)$ は $\mathbb{F}_{2^3}$ では2になります．

何が起こっているのかというと，

Aliceがメッセージを符号語に変換する
AliceがBobへ符号語を送信する
通信路中，符号語に対して，$1 \leq i \leq 7$ の $i$ 番目に誤りが発生する
Bobは受け取った $\mathbb{F}_2^7$ の符号語に $H$ を掛けて $\mathbb{F}_2^3$ の要素へ変換する
Bobは step3 の出力（$\mathbb{F}_2^3$ の要素）を $\mathbb{F}_{2^3}$ の要素へ変換する
step4で $i$ が出力されるため，Bobはstep3で受け取った符号語の $i$ 番目のbitを反転する

という操作で誤り訂正が行えることを言っています
＊厳密には，1 bit 誤り検出ができて，1 bit 誤り訂正ができます（2 bit 誤り検出もできますが，今回は割愛）

始めの例だと「010」というメッセージを「010010010」でメッセージ長９で符号化していたのが，Hamming符号を使うとメッセージ長が７で済むというのが嬉しい点です

ちなみに今回のHamming符号の生成行列を以下に示しておきます（一意ではない）:

\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}

と言っても，Hamming符号よりも効率の良い（符号効率が良い）符号は他にたくさんある，っていうかありすぎるぐらいあります

まとめ

今回は符号ベース暗号のための，本当に最低限の符号理論の内容を紹介しました
符号理論はそれ自体でめちゃくちゃ大きい分野ですので，参考書も数多くあります

興味のある方は何かしらの符号を勉強してみてはいかがでしょうか？

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

参考文献

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