社会人になり３ヶ月が経ったということで，ここで理論的でもなければ技術的なことでもない今までのちょっとした（制作期間２ヶ月）振り返り記事を書いてみようと思います
格子暗号を用いた準同型暗号の論文を理解するには，どこまでの事前知識が必要なのか，他におすすめの論文などをまとめてみます
本記事はあくまで個人の見解であり，所属する組織の方針や見解を代表する・述べるものではありません
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください
既存のロードマップ
突然ですが皆さんこちらの記事はご存知でしょうか？
実は筆者も↑のロードマップに沿って，格子暗号や秘密計算の基礎を習得しました
しかし，↑は実装を含めた準同型暗号を使えるようになることを目標としているため，僕みたいにあまり実装に興味がない方準同型暗号の理論に注目したい方にとっては，
- このあとでおすすめの論文はないのか
- 他の論文を見ると色々と数学の知識が使われているがどこまで必要なのか
などの点が少し物足りないのかなと思っています
そこで今回は，今まで準同型暗号に関する論文（特に理論）をいくつか読んできた筆者が，
まずはよく使われる数学の分野を頻度順にまとめます
そして，それらの分野の中でも習得の優先順位が高いと思われるキーワードを列挙します
その優先順位の段階に応じておすすめの書籍も紹介します
最後に準同型暗号の理論に関して，いくつかのおすすめの論文を載せます
＊勘違いされそうなことへの補足
- 準同型暗号で必要とされる数学を全て網羅しているわけではありません
- また本当に必要な数学を網羅できているとも限りません（今後新しい分野が出てくることもある）
- 数学に興味がない方も想定して，特に初めの段階では，「適宜ググれば良い」やおすすめ本が必ずしも数学書ではないなど，ある程度の厳密性は落としています（全員が全員数学科出身ではないためです，必要になったり数学に興味が出てきたら色々な数学書で本格的に勉強してみてください）
- この記事では「数学の勉強」はあくまで論文を読むためのサプリのようなものなのであり，必要になったら適宜本に戻ってある程度わかったら論文に戻る，というスタンスの方を想定しています
- とは言っても，既に数学にかなり習熟されている（代数幾何専攻だったとか数論専攻だったとか表現論専攻だったとか）方もいらっしゃると思います，そのような方向けに暗号の理論的な部分に関する書籍も紹介していますので，参考になる部分があれば
逆に本記事では，格子暗号を用いた準同型暗号の歴史や最新動向，技術的な部分に関してはほぼ触れませんので，それに関しては既存のロードマップをご参照ください
機械学習で必要な数学の分野との違い
応用数学という広い分野の中に機械学習と暗号理論という２つの分野があるわけですが，ものすごく大雑把に，機械学習では解析・暗号理論では代数という数学の分野が主に使われます
機械学習では，微積分（主に多変数関数）・関数解析・数値解析（・統計）など多くの場面で解析が関わります
一方，暗号理論では，初等整数論・群・環・有限体など代数を用いることが多いです
また，どちらでも使われる分野もあり，統計や線形代数は割と共通していると思います
両者で必要とされる数学のスキルセットが異なるのですが，この中でも優先順位があります
次の章を見ると大体わかりますが，機械学習の実装に日頃励んでいる方が今回の準同型暗号の実装をやってみたいと思ったら，初等整数論・代数の基本的な知識を勉強するだけで，ある程度はできるようになるはずです
優先順位
＊「知らなくても良い」はその段階において知らなくても良い・勉強する優先順位は比較的低い，という意味であり，知っている・勉強するに越したことはありません
- 暗号をやる上で最小限
- 初等整数論の初歩（特に合同式）
- 確率・統計（特に正規分布）
- 計算量理論（多項式時間・クラスP, NP）
- 準同型暗号の簡単な実装(暗号化方式や暗号文の足し算の実装など）に必要
- 群論・環論の初歩（巡回群・剰余群・剰余環・イデアル）
- 初等整数論（オイラー関数・Fermatの小定理など有限体周り）
＊平方剰余の相互法則などは知らなくても良いです - 線型代数の初歩（ベクトルの足し算・行列の掛け算などのベクトル・行列演算）
＊Tensor積は知らなくても良いです - 複素数の初歩（複素数の掛け算・De Moivreの定理・1のn乗根）
- 準同型暗号の複雑なアルゴリズム（bootstrapとか）の実装に必要・理論を６割ほど理解したい
- 環論（多項式環・既約多項式）
- 加群（準同型）
- 理論を８割以上理解したい（優先順位は上から）
- Galois理論・円分体（特に円分多項式）
- 線型代数（ベクトル空間・基底）
＊学部１年生レベル（Jordan標準型や有限体上の線型代数は知らなくても良いです） - 離散Fourier変換（DFT）・FFT・NTT
- 全称命題・存在命題
- 位相空間
実装しか興味ない，という方も2までは知らないとおそらく何をやっているか分からないかと思います（群論・環論はもうちょい削れるかもですが，あまりお勧めできません）
また，個人的な感覚ですが，3まで踏まえれば理論的な研究に入っていけるかと思います（逆にここまでの知識がないと何を言っているか分からない論文に遭遇する可能性があります）
＊もちろんその知識セットで必要十分ではないため，足りない分野は適宜勉強してください（4の中でもあえて優先順位をつけるなら，上から順にやっていくと良いです）
４まで全部分かっているよ，という方は数論（代数的整数論とか）とか代数幾何とか表現論とかその辺りを勉強することになると思います
圧倒的な数学パワーでねじ伏せたい方は勉強しましょう（っていうかこの辺を一緒に勉強してくださる方を募集中ですモチベ的に）
それでは以下でそれぞれの分野について，何の書籍でどこを重点的に勉強すればいいか言及します
1. 暗号をやる上で最小限
初等整数論の初歩（特に合同式）
暗号理論は有限体の世界で議論することが多い（特に実務で使われるようなものは尚更）ため，合同式に関する知識は必須です
mod とかいう記号にギョッとするかもしれませんが，しょせんは余りに注目しているのにすぎないという意識があれば，そこまで恐れる必要もないと思います
（ここ最近の）高校数学の教科書を紐解いてみてもいいですし，暗号から学ぶ代数学 の２章を読むのでもいいかもしれません
確率・統計（特に正規分布）
この辺は暗号理論の書籍より機械学習の書籍の方が充実しているかもしれません
より理論の深い部分（安全性証明とか）を勉強・研究するなら，Chebyshev の不等式といった部分も必要になりますが，それ以外の方は正規分布がなんたるかを分かっていれば十分だと思います
計算量理論（多項式時間・クラスP, NP）
実務で使うような暗号は安全，と割り切ってしまえば，ここは飛ばしてもOKです
そこそこしっかりやるなら 耐量子計算機暗号 の1.2を読めば十分です
↓以下はもっとしっかりやりたい方向け
和書なら 計算理論の基礎 [原著第3版] 3.複雑さの理論 とか 計算できるもの、計算できないもの―実践的アプローチによる計算理論入門 とかがおすすめです
洋書はめちゃくちゃあるのですが，後で Goldreich という方の暗号理論の洋書を紹介するためここでは統一して Computational Complexity: A Conceptual Perspective
を載せておきます
＊Turing マシンやオートマトンなども１回はやっておいた方がいい気はしますが，この時点ではそこまで重要視しなくてもいいです
＊計算量理論メインの本を読むといいです，計算理論の方に突っ込むと戻れなくなります()
2. 準同型暗号の簡単な実装(暗号化方式や暗号文の足し算の実装など）に必要
群論・環論の初歩（巡回群・剰余群・剰余環・イデアル）
耐量子計算機暗号 の 1.4.1, 1.4.4 を読んで理解できるならいいのですが，それだけで理解できる方はおそらく既習の方なので 暗号から学ぶ代数学 をさくっと通読するといいと思います
ちょっと遠回りに思うかもしれませんが，さすがにRSA暗号やElgamal暗号は知っておいた方がいいと思います
初等整数論（オイラー関数・Fermatの小定理など有限体周り）
暗号から学ぶ代数学 を読んだら，現時点では十分かなと
それでも足りないと思う方は，正直ググれば大体はどうにかなる気もしますが，何かしらの初等整数論の本を読むと良いのかなと
筆者は 初等整数論―数論幾何への誘い― とか好きですが，ちょっと数学色が強いかなぁと・・・
線型代数の初歩（ベクトルの足し算・行列の掛け算などのベクトル・行列演算）
これもまた暗号理論の書籍より機械学習の書籍の方が充実しているかもしれません
大学で講義を受けてまだ教科書が残っている方はそちらでも良いかもです
線型代数の本は星の数ほどあるので自身に合いそうなものを探すといいのですが強いていうなら 線型代数学 がここ最近は良い本かなって思っています
複素数の初歩（複素数の掛け算・De Moivreの定理）
これは高校での教科書を紐解いた方が早いです
もしくはここはすっ飛ばして，必要になったら適宜ググるとかでも良いかもしれません
高校数学の範囲なので分かりやすい（と思われる）解説はたくさんあるはずです
3. 準同型暗号の複雑なアルゴリズム（bootstrapとか）の実装に必要・理論を６割ほど理解したい
この辺までおさえることができたら，大抵の実装で困ることはありませんし，ググってもよく分からんってなる気がするので，数学書を読んだ方が早いのでは感が否めません
なんですが，全てを読む必要はありませんし，必要になったら適宜読んで，大体掴んだらまた論文に戻るって感じで良いと思います
環論（多項式環・既約多項式）
おすすめ：代数学I 群と環, 代数学2 環と体とガロア理論
体上の多項式の集合に環の構造が入り，多項式が整数っぽい性質を持つことを理解できれば十分です
素数に対応するものが既約多項式になるとも思えます
既約多項式が生成するイデアルで割った剰余環は〜とかは次のステップでOKです
加群（準同型）
＊厳密なことを書くと，線型代数（特にベクトル空間）を全く知らないのに加群に突入してもイマイチよく分からないと思うので，ちょろっと触れておくといいかもしれません
おすすめ：代数学II 環上の加群, 代数学2 環と体とガロア理論
準同型暗号の準同型です
実用上では，足し算と掛け算を併せ持つことさえ理解できていれば良いので，ここまでの抽象論はもしかしたら不要かもしれません
＊なんですが，加群を勉強すると，加群準同型はすぐ出てくるので，ざっと勉強するのもありかもです
4. 理論を８割以上理解したい
ここに載っている分野を習得できたら，暗号理論に使われる数学にはさほど困らない（本当はそんなことないのですが，全員が全員数論専攻並のパワーが必要ではないので・・・）と思いますし，困ることがあっても，乗り切れるはずです
Galois理論・円分体（特に円分多項式）
＊厳密なことを書くと，線型代数（特に↓の基底とか）を全く知らないのにGalois理論に突入してもイマイチよく分からないと思うので，ちょろっと触れておくといいかもしれません
おすすめ：代数学III 体とガロア理論, 代数学2 環と体とガロア理論
格子暗号の理論に深く突っ込むなら，円分多項式は必須です
Galois理論をがっつり勉強するとまではいかなくても円分多項式にある程度慣れておくと良いと思います（なんですが円分多項式を理解しようとすると結局Galois理論の言葉が必要になることが多いです）
線型代数（ベクトル空間・基底）
おすすめ：線型代数学, 線型代数学 （新装版）
大学で講義を受けてまだ教科書が残っている方はそちらでも良いかもです
別に前者である必要はなく，線型代数の教科書ならほぼ書かれている内容なので，ご自身に合ったものが良い気がします
後者の教科書はめちゃ難しいので，辞書的なイメージですね
離散Fourier変換（DFT）・FFT・NTT
意外と１から解説するのを１つにまとまっているものはありません
ということで僭越ながら筆者が以前書いた記事を載せておきます
全称命題・存在命題
おすすめ：イプシロン・デルタ論法 完全攻略
暗号方式の安全性の議論に関わりたいなら，この分野は必須です
おすすめの第１章だけでも十分ですが，この分野を理解するのにε-δは最適です
級数や解析の基本知識も得られると思ってがんばりましょう
位相空間
おすすめ：イプシロン・デルタ論法 完全攻略, 集合と位相（増補新装版）
前者でε-δに慣れましょう
その上で位相の本はたくさんあるのですが，例えば最近新装版が出たやつとかも良いと思います
暗号理論の書籍について
ここでは数学ではなく，暗号理論の一般的な知識が足りないな・・・と思ったときに助けになるかもしれない書籍をいくつか載せます
準同型暗号・格子暗号
和書では，耐量子計算機暗号, 現代暗号の誕生と発展 がおすすめです
あとはもう書籍というより論文を読んだ方が早い感があります
安全性
暗号の理論的なテーマといえば暗号方式の安全性に関する議論は外せないと思います
いきなり論文を読んでもIND-CCAとか semantically secure とか意味わからん用語が出てくるので，格子暗号とか準同型暗号の前に，書籍での一般論の勉強が必要になると思います
筆者もそこまで詳しくはないのですが，大体この辺は押さえればって感じのものを紹介します
まずは Goldreich の Foundations of cryptography です
何回か同じことを繰り返してくれる（だから重厚）ので，案外読みやすいです（読めるとはいってない）
なんですがやはり上下巻あるのはしんどい・・・という方向けに 公開鍵暗号の数理 という和書があります
絶版という点を除けばすごく良い本だと思います
おすすめ論文
最後に格子暗号を用いた準同型暗号に関するおすすめの論文をいくつか載せます
大雑把に暗号理論の論文では，その暗号を設計する側の視点とそれを攻撃する側の視点に分かれます
勉強量的なおすすめは攻撃をやってから設計ですので，まずは攻撃の方から
攻撃
攻撃手法といっても色々あるのですが，最短で最先端に辿り着きやすいと思われるものを紹介します
多くの格子暗号（特に準同型暗号で使われるような格子暗号）の安全性の根拠となっているLWE問題に対して最善なアルゴリズムの１つにLLL基底簡約アルゴリズムというものがあります
＊LLLの読み方は「triple L」派と「L・L・L」派に分かれますが，まあそんなことどうでもよいです（筆者は前者派）
そのLLL基底簡約アルゴリズムを使っても格子暗号は簡単には解けない（解けると困る）のですが，逆にどのくらい付加情報があれば与えられたLWE問題を解けるのか？という視点に関する研究を紹介します
格子暗号解読のための数学的基礎
格子暗号解読のための数学的基礎-格子基底簡約アルゴリズム入門-
いきなり論文ではないのですが，この書籍では，LLL基底簡約アルゴリズムやその発展版であるBKZ基底簡約アルゴリズムについて解説されている現状唯一の日本語の書籍です
筆者もまだ完全には読みきれていないのですが，具体例含めて分かりやすく書かれています
数学書に慣れていないと読みづらいと思うかもしれませんが，そのうち慣れます
ちなみにこの本には実装が載っていませんが，耐量子計算機暗号と量子情報の数理 の安田先生（↑の本の著者のお一人）のスライドに LLL の SageMath（python）でのコードが記載されています
めちゃめちゃどうでもいいんですが，色々あって著者の安田先生からサインをいただきましたその節はありがとうございました
LWE with Side Information: Attacks and Concrete Security Estimation
↑の引用先はePrint版
この論文がこの攻撃のオリジナル（だと思っていますたぶん）
Too Many Hints – When LLL Breaks LWE
なんとこちらのePrintは先月にreceivedされたものですので，最先端のものになります
＊ちなみに筆者の Alexander May は符号ベース暗号でも有名です
設計
筆者はCKKSとTFHEに関する論文をメインに読んでいるので，その辺りを紹介します
といっても書きすぎてもしょうがないので，CKKSで２本・TFHEで２本紹介します
はじめに紹介したロードマップでは初めに「イデアル格子暗号入門」が紹介されているため，次に読むのはCKKS関連の論文が良いです
＊「イデアル格子暗号入門」に関する記事は探せば多くあります，筆者も以前に書いているので参考までに
イデアル格子暗号入門を深く理解する 1/3
Homomorphic Encryption for Arithmetic of Approximate Numbers
J. H. Cheon, A. Kim, M. Kim, Y. Song: ``Homomorphic Encryption for Arithmetic of Approximate Numbers'', In: International conference on the theory and application of cryptology and information security, Springer, Cham, pp.409-437, 2017.
さすがにCKKSのオリジナルは外せないですね
ちなみに上記のオリジナル論文に対して，その内容を噛み砕いた解説ブログがあります
CKKS EXPLAINED: PART 1, VANILLA ENCODING AND DECODING
なんですが，さらにそれを解説した「CKKS解説ブログを解説する」という連載をしている（かなり間が空いていますが，そのうち一気に完結させます）ので、よろしければこちらも
「CKKS解説ブログ」を解説する 1/5
On the Security of Homomorphic Encryption on Approximate Numbers
↑の引用先はePrint版
CKKSの安全性に関する論文です
漸近的・実用的の２つの方面から安全性の議論が展開されています
ちなみにこのePrintは下記の PALISADE というCKKSのライブラリでも言及されています
PALISADE HOMOMORPHIC ENCRYPTION SOFTWARE LIBRARY
TFHE: Fast Fully Homomorphic Encryption Over the Torus（論文誌版）
元祖TFHEですが，論文誌版では，色々なePrintの情報が統合されていて見やすいです
そもそもLWE自体がrevistedなので，ある程度は知ってる前提なのでしょう
Liberating TFHE: Programmable Bootstrapping with General Quotient Polynomials
↑の引用先はePrint版
TFHEで用いられる円分多項式について議論されています
色々な知識を使って，時には泥臭い議論をしないといけない感じが個人的には好きです
こちらは以前に解説記事を書いたので，もし何か参考になれば
【ePrint解説】Liberating TFHE 1/4
まとめとか感想とか
今までの知識の整理の兼ねて，方法論っぽい記事を書いて見ました（こういうのを書くのって結構大変なんですね・・・）
あくまで個人の意見ということをお忘れなく
もっと他にこういう本があるよ，などありましたら，ぜひ教えていただけたらと思います
本記事がどなたかのお役に立てるのなら幸いです
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！