実は今Zennで符号ベース暗号と量子アルゴリズムに関する本（というより今までの自分の知識の整理をする予定のもの）を書いています
（構成だけ作って満足している人()）
符号ベース暗号と量子アルゴリズム
そこでは，符号ベース暗号に関する基本的事項（必要な数学も全て）から最先端の話題（筆者の研究も少し書きます）まで取り扱うつもりなのですが，完成までに割と（３年ぐらい？）時間がかかりそうですし，いくつかのリクエスト記事に答える形で「美味しい」部分を先に扱おうと思います
といっても，このスポット解説も書き終えるのに１年ぐらいかかりそうではあるため，月１本ペースで気長に待ってくださればと思います
| 回目 | 内容 |
|---|---|
| 第1回 | 符号ベース暗号で用いられる計算問題 |
| 第2回 | McEliece暗号方式, Niederreiter暗号方式, CFS署名方式 |
| 第3回 | BIKE, Classic McEliece, HQC（Hamming符号ベース暗号方式） |
| 第4回 | ROLLO, RQC（Rank符号ベース暗号方式） |
| 第5回 | LESS-FM, Durandal（符号ベース署名方式） |
| 第6回 | Information Set Decodingアルゴリズム, Dumer のアルゴリズム |
| 第7回 | MMT, BJMMアルゴリズム, DOOM |
| 第8回 | Nearest-Neighbor, Syndrome Decoding Estimator |
| 第9回 | 量子Information Set Decodingアルゴリズム |
| 第10回 | GRSアルゴリズム |
構成を簡単に説明します
符号ベース暗号の論文は
- どのような符号を用いるのか
- その符号に対してどのような計算問題を用いるのか
- 暗号方式 or 署名方式
- 設計 or 攻撃
という視点で分類すると，読みやすくなると思っています．
そこで
第１回 → 1.と2.
第２回 → 3.の概要(暗号方式と署名方式・設計)
第３・４回 → 3.と4.（暗号方式・設計）
第５回 → 3.と4.（署名方式・設計）
第６-10回 → 3.と4.（暗号方式・攻撃）
という構成を取って，なるべく最新の話題までさらえるように仕上げていきます
1. どのような符号を用いるのか
符号理論で考察の対象となる符号はたくさんあるのですが，その中でもよく符号ベース暗号で使われるのはHamming距離を用いた符号とRank距離を用いた符号です
またその中でも代数系か組合せ（という呼び方が適切かは知らない，モダンと呼ばれるもの）系かに分かれます
大雑把にですが，
| Hamming | Rank | |
|---|---|---|
| 代数 | Reed-Solomon 符号 Goppa 符号 |
LDPC 符号 QC-MDPC 符号 |
| 組合せ | Gabidulin 符号 | LRPC 符号 |
みたいな分類ができます
はじめにこれらの符号を使ってどのような暗号方式や署名方式が構成されるのかを理解してから，徐々に（自分の中で）扱える符号を増やすと良いと思います
2. その符号に対してどのような計算問題を用いるのか
以前の符号ベース暗号の連載記事では，シンドローム復号問題というNP完全な問題を紹介しましたが，他にも計算困難な問題はあります（その問題が実際の暗号方式や署名方式に用いられているかは一旦別として）
参考文献
耐量子計算機暗号の研究動向調査報告書
格子暗号で用いられるLWE問題を弱めたLPN（Linear Parity with Noise）問題という問題があります
大雑把にいうと $\mathbb{F}_2$ 上のLWE問題がLPN問題に対応します
また，Rank距離を用いた符号では，いずれ紹介しますがDurandalという署名方式の原論文において，いくつかの計算困難問題が紹介されています．
N. Aragon, O. Blazy, P. Gaborit, A. Hauteville, Gilles Zémor: ``Durandal: a rank metric based signature scheme'', In: Advances in Cryptology–EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19–23, 2019, Proceedings, Part III 38. Springer International Publishing, pp.728-758, 2019.
＊↑の引用先はePrint
例えば，シンドローム復号問題のRank距離版であるRank SDP（Rank Support Decoding Problemとも）やRSLP（Rank Support Learning Problem），PSSIP（Product Spaces Subspaces Indistinguishability Problem）などが議論されています
＊PSSIPについては，つい先日それ関連のePrintが出ましたね（Nicolas Aragon, Philipe Gaboritは符号ベース暗号だとめちゃくちゃ有名ですね・・・）
N. Aragon, V. Dyseryn, P. Gaborit: ``Analysis of the security of the PSSI problem and cryptanalysis of the Durandal signature scheme'', Cryptography ePrint Archive, 2023/926, 2023.
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！