書籍『耐量子計算機暗号』の紹介

この記事は[EAGLYS Advent Calendar 2021](https://qiita.com/advent-calendar/2021/eaglys_adcal)の９日目の記事です．

書評するコーナーをやってみます．

Q. それってあなたの感想ですよね？
A. はい

今回は第１回で僕が「聖書」と呼んでいる本です．

# 自己紹介

耐量子計算機暗号（特に符号ベース暗号）を研究している修士１年です．

普段Qiitaでは量子関連（まだ量子アルゴリズムのスクラッチ実装と量子ブロックチェーンの勉強したての記事のみですが・・・）を扱い，

[量子アルゴリズム①　Shorの素因数分解アルゴリズム](https://qiita.com/0917laplace/items/982f171d023ef2fe6320)

[Qunatum-secured blockchain ①](https://qiita.com/0917laplace/items/5c2f499251a67ca2777a)

Zennでは，古典関連（耐量子暗号やプログラマブルブートストラップの解説記事）を扱っています（唐突な宣伝）．

[McEliece暗号](https://zenn.dev/0917laplace/articles/b6ff9731e533cf)

[プログラマブルブートストラップの原著論文を理解する回　1/4](https://zenn.dev/0917laplace/articles/1f0eb3957b838d)

また，現在Qiitaの方で，上記のZennの連載記事「プログラマブルブートストラップの原著論文を理解する回」のリメイク版も載せています．

[「プログラマブルブートストラップの原著論文を理解する回」を理解する回　1/4](https://qiita.com/0917laplace/items/679fa72d44bf02b4e17c)

# 何をするのか

秘密計算の会社の記事，ということで，Qiitaですが古典の内容を投稿します．

格子暗号に秘密計算・機械学習って最近の話題を色々紹介しているけど，なんか良い本ないの？という要望に応える企画です．
ちなみに暗号全般や暗号で使われる数学関連の書籍は，[「プログラマブルブートストラップの原著論文を理解する回」を理解する回](https://qiita.com/0917laplace/items/679fa72d44bf02b4e17c#%E5%8F%82%E8%80%83%E6%96%87%E7%8C%AE)という記事で紹介しているので，そちらをご参照ください．

全３回に渡って，主に３冊を取り上げて紹介します．今回は第１回目です．

１冊目：[縫田 光司，『耐量子計算機暗号』，森北出版，2020](https://www.morikita.co.jp/books/mid/087211)
２冊目：[佐久間 淳，『データ解析におけるプライバシー保護』，講談社，2016](https://www.kspub.co.jp/book/detail/1529199.html)
３冊目：[Chiheb Chebbi　著，新井 悠，一瀬 小夜，黒米 祐馬　訳，『セキュリティエンジニアのための機械学習ーAI技術によるサイバーセキュリティ対策入門』，O'Reilly Japan，2021](https://www.oreilly.co.jp/books/9784873119076/)

選んだ理由としては，

１冊目：格子暗号含む秘密計算の理論的な話
２冊目：秘密計算のもう少しざっくりした話やプライバシー・機械学習の話
３冊目：セキュリティと機械学習の話

っていう秘密計算→機械学習の流れが綺麗かなぁって思ったからです．（ホンマか？）

内容的に全てを紹介するのはできないので，読んでて思ったところを特に紹介していきます．
途中途中で他にも色々と本を紹介するつもりです．

# 今回紹介する本

以下の記事を連載中です．

Zenn
[プログラマブルブートストラップの原著論文を理解する回　1/4](https://zenn.dev/0917laplace/articles/1f0eb3957b838d)

Qiita（上記のリメイク版）
[「プログラマブルブートストラップの原著論文を理解する回」を理解する回　1/4](https://qiita.com/0917laplace/items/679fa72d44bf02b4e17c)

内容については触れませんが，このような記述があります．

> マジの聖書（耐量子計算機暗号に多かれ少なかれ関わっている方はもちろん，数学的に量子計算や高機能暗号を捉えたい方に勧められます．量子計算機の共通鍵暗号への影響もちらっとだけ触れられていて，本当に痒いところに手が届く本です）
（ですが，計算量や代数は載っているもののかなりさらっと書かれているので，初学向けではないです）

オタク特有の早口感が拭えない・・・．

ちょっと胡散臭いなぁと思ってしまう方もいらっしゃるかもしれないので，ここではその内容に少し触れていきたいと思います．

というわけで，初回は↓の本を紹介します．

[耐量子計算機暗号](https://www.morikita.co.jp/books/mid/087211)

# どのような本なのか

> 耐量子計算機暗号を包括的かつ技術的に解説した、初の専門書

です．

ちなみに上記では省かれていますが，「和書として初の専門書」です．
洋書では，例えば， [Daniel J. Bernstein，Johannes Buchmann，Erik Dahmen，『Post-Quantum Cryptography』，Springer，2009](https://link.springer.com/book/10.1007/978-3-540-88702-7) などがあります．

内容は，ガバガバな設定などもなくて個人的にめちゃくちゃ読みやすいです．特に $\mathbb{Z}_p$ なんかはやっぱりそう思いますよね・・・って感じでした．

そんなこんなで割ときっちりと議論が進んでいきます．数学科出身って感じです．そして所々のちょっとしたTipsが痒いところに手が届くって感じの本です．

**理論寄りの本なので，実装などの話は少ないです**

ちなみに大川出版賞という賞を受賞されている本です． [かなり最近の話題](http://www.okawa-foundation.or.jp/activities/publications_prize/list.html)

＊2018年度の森前先生の『量子計算理論』もよく読んでます

# 構成

> 第1章　暗号分野への導入
第2章　耐量子計算機暗号
第3章　格子暗号
第4章　同種写像暗号
第5章　量子計算と暗号の安全性

もう少し詳しいことは， [縫田先生のHP](http://www2u.biglobe.ne.jp/~nuida/m/book_PQC_202008.htm) で紹介されています．

上記のHPに目次が記載されているのですが，そこから本の内容が深く推測できない程度に紹介します．

# 第１章
暗号理論の基礎的な部分の紹介です．代数や計算量の解説もあります．

個人的には，暗号の安全性の証明を和書で読めるのは結構珍しいのでは，と思いました．NP困難な問題に帰着させて・・・という「定石」を理解するには最適だと思います．

また，Paillier（パイエ）暗号という準同型暗号に繋がる話題も紹介されています．

# 第２章
3つに分かれていて，

- 耐量子計算機暗号の導入
- 符号ベース暗号
- 多変数多項式暗号

という流れです．

**耐量子計算機暗号の導入**
耐量子計算機暗号について，背景や直近の動向について触れられています．

この辺の話題は [高木 剛，『暗号と量子コンピュータ ―耐量子計算機暗号入門―』，オーム社，2019](https://www.ohmsha.co.jp/book/9784274224102) が詳しいです．

**符号ベース暗号**
符号理論の説明が１から始まり，McEliece暗号やNiederreiterについて触れられています．

専門だからの感想かもしれませんが，めちゃくちゃあっさりしています．
えっ？もう終わったの？？？って感じでした()．

↑そんなこと言うならお前が書けよって思うかもしれませんが，**書いています**

符号理論の詳しい話ですが， [萩原　学，『進化する符号理論』，日本評論社，2016](https://www.nippyo.co.jp/shop/book/7206.html) が読みやすく，もう少しきっちりやりたい方には [萩原　学，『符号理論 デジタルコミュニケーションにおける数学』，日本評論社，2012](https://www.nippyo.co.jp/shop/book/5977.html) がおすすめです．
特に縫田先生の本で省略されているLDPC符号の話はしっかり理解できると思います．

**多変数多項式暗号**
Gr&ouml;bner基底の説明が非常によくまとまっていて，かつ，具体例もあり分かりやすいです．

途中で出てくるUOV方式ですが，恐らくこれを発展させたものが [最近話題になったやつ](https://www.jst.go.jp/pr/announce/20211124-2/index.html) なんじゃないかなと思っています（内容はよく見てないのですが）

ちなみにグレブナー基底は検索エンジンでかければ色々と面白い記事が出てくる（ポン酢が合う）ので，まずはそれで馴染むのも良いかもしれません．

# 第３章
格子暗号ですね．耐量子計算機暗号の中で最も人口が多い分野（だと勝手に思っている，少なくとも感覚的に日本ではそう）．

基底簡約やアルゴリズムの話のみならず，準同型暗号への応用にも触れられています．

ちなみに，格子暗号の数理的な側面は [青野 良範，安田 雅哉，『格子暗号解読のための数学的基礎 ―格子基底簡約アルゴリズム入門―』，近代科学社，2019](https://www.kindaikagaku.co.jp/math/kd0598.htm) が詳しいです．っていうか詳しすぎて，読むのがちょっと大変・・・．

＊クッソどうでもいいですが，先日に著者の安田先生にサインいただきました（もらうつもりはなかったのですが，気づいたらもらっていました）（え？）

欲を言えば，NTRUの解説がほしかった・・・．

# 第４章
えっ！同種写像暗号の紹介あるの？

っていうのが第１印象でした．同種写像は平たくいうと楕円曲線間の写像のことです．

僕もこの本を読むまで存在は知っていましたが，同種写像って難しそうだな，難し目の楕円曲線の本（[AECとか](https://www.amazon.co.jp/Arithmetic-Elliptic-Curves-Graduate-Mathematics/dp/0387094938)）を読んでからトライしようかなってぼんやりと思っていました．

深くは読み切れていませんが，これを読んだら，SIKEやSIDHにトライしてもいいかなって思っています．

＊まあ今研究でSIKEの論文を読んでいるので，そのうちっていうかすぐトライしなきゃなんですが・・・

ちなみに[九州大学 IMIの新着情報](https://www.imi.kyushu-u.ac.jp/news/view/1607)での縫田先生の↓のコメントがめちゃくちゃ好きです笑．

> 本書で紹介している暗号技術の一つである同種写像暗号はかなり新しい種類の暗号技術であり、類書がないため執筆に際しては原著論文をあたる必要がありました。その際、暗号方式の動作の正しさに関わる命題の証明が一部省略されていた箇所があり、論文の著者に内心で文句を言いながら自分で証明を考えていたことが印象に残っています。

やっぱりみんな文句を言うんだなって笑．

# 第５章
量子計算と量子アルゴリズムの話です．
**耐量子計算機暗号の本ですが，この章のためだけにこの本を買うのもあり**なぐらいおすすめな章です．

まず，量子計算の導入が簡潔で分かりやすいです．確かに波動関数云々は重要なのですが，そこを抜きにして理論を進めるのは敷居が低くてよかったなって思っています．

また，量子アルゴリズムについても，単に紹介するだけでなく，正当性の話まで踏み込んでいます．
SimonやGroverであればまだ取っつきやすいですが，Shorのアルゴリズムをきっちり理解しようと思うと意外と大変です．それを和書で読めるというのは，非常に意味があることだと思います．

＊隙あらば宣伝ですが，Shor・Simon・Groverのアルゴリズムは以前に記事を書いたのがあるのでぜひ

[量子アルゴリズム①　Shorの素因数分解アルゴリズム](https://qiita.com/0917laplace/items/982f171d023ef2fe6320)

[量子アルゴリズム②　Simonのアルゴリズム](https://qiita.com/0917laplace/items/01e66393a699deae5c38)

[量子アルゴリズム③　Groverのアルゴリズム](https://qiita.com/0917laplace/items/e7113eb1465ff75be0a7)

# 良かった点と悪かった点
良かった点

- かなりself-contained（代数や計算量・確率の前提もまとまっている）
- 具体例もきっちり載っている
- 暗号の安全性の証明が載っている（すごい）
- 耐量子暗号のみならず，高機能暗号などへの応用にも触れられている
- 共通鍵暗号への影響などのちょっとしたTipsも豊富
- 同種写像暗号の解説にびっくり
- 量子計算の解説の充実度がすごい（Shorのアルゴリズムの理論をきっちり解説する本は貴重です）

悪かった点（自分でやれっていうか，本に求めすぎっていうか・・・）

- 擬似コードでいいので，実装例をほしかったです
- 符号ベース暗号の扱い・・・
- NTRUの理論に触れてほしかったなぁ

# 最後に
今回は
[縫田 光司，『耐量子計算機暗号』，森北出版，2020年](https://www.morikita.co.jp/books/mid/087211)
を紹介しました．

耐量子計算機暗号の理論の入門としてはぴったりの本です．また，高機能暗号との関わりや量子計算の解説も素晴らしいと思います（え？上から？）．
本当に持っておいて損はない本だと思います．

しかし，符号ベース暗号に接続するにはちと厳しい本かな・・・と．その辺の話題（色々な符号の応用や具体的な攻撃手法とアルゴリズム・そのPythonやC++の実装例も含む）は今僕が書いているので，１年ぐらい期待してください()．