この記事はEAGLYS Advent Calendar 2021の24日目の記事です。Merry Christmas!!!って言いたかった（投稿日1/31）．
今回の記事は下記の記事とは独立に読めます．
原著論文：プログラマブルブートストラップの原著論文
第１回：第１回
第２回：第２回
第３回：第３回
第４回：第４回
上記はプログラマブルブートストラップの原著論文の第２〜４章を厳密に考察した連載記事です．
全体を通して使う記号や前提知識などは第１回目の記事にまとめています．
この連載を更に深掘りしたZennの記事
第１回：第１回
第２回：第２回
第2.5回:第2.5回
第３回：第３回
第４回：第４回
Zenn版理論まとめ（今回の内容に加えて本論文を理解する際に集中的に読むべき箇所や注意点・感想などを記載しています）
理論まとめ:理論まとめ
突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください
今回の目次
- なぜ今回の記事が必要なのか
- 各記事の位置付け
- 本論文の流れ
- ２章のポイント
- ３章のポイント
- ４章のポイント
なぜ急に今回の記事が出てきたのか，それも含めて早速内容の方に入っていきます．
なぜ今回の記事が必要なのか
今までZennでもQiitaでも「本論文の理論を深く理解する」という目的で，連載を始めました．
しかし，全ての人がそこまで必要ではありません．例えば「TFHE方式の暗号化のアルゴリズムだけやりたいんだけど，これの 第１回 から読まないといけないの？」と聞かれたら，そんなことはありません．
また，各論を深く理解しても結局全体の流れがどうだったのかを意識できなければ，その理論を応用したり，似たような議論に出会ったときに統一的な視点で理解するのは難しいです．
「木を見て森を見ず」になってしまわないかなと思ったので，各章で「どういうことをやりたいのか」・「なんでそれができるのか」をポイントを絞って１つの記事にしてみました．
キーワードの簡単な説明を織り交ぜながら，各章のモチベーションやポイントを簡単に解説します．
各記事の位置付け
全体で４つに分けられます．
Qiitaまとめ：Qiitaまとめ
今回の記事です．論文の各章のポイントをまとめた記事になります．これを読むことで，何をやるためにどうすればいいのか，が簡潔にキーワードを含めて理解できるようになっています（たぶん）．
Zennまとめ：Zennまとめ
こちらは，内容としては上記のQiitaまとめに加えて，「本論文を理解する際に集中的に読むべき箇所」や「読みづらい原因」・「感想」・「今後の展望」など＋α的なことも加えています．
Qiita連載記事
第１回：第１回
第２回：第２回
第３回：第３回
第４回：第４回
本論文の第２〜４章の理論を厳密に考察した連載記事です．こちらは最小限の努力で理解することを目標にしています．
Zenn連載記事
第１回：第１回
第２回：第２回
第2.5回:第2.5回
第３回：第３回
第４回：第４回
上記のQiita連載に加えて，背景にある数学の議論や暗号化の具体例・今回の議論を元にどう深掘りして考察するか，など「本論文をゼミで発表するならどんな原稿になるか」を意識した記事です．
本論文の流れ
- どういう背景や課題・モチベーションがあって，
- どのようなアイディアのもとで，
- どのような結果が得られたのか
を整理します．
背景・課題
完全準同型暗号を達成する暗号として格子暗号ベースが考えられています．
格子暗号は簡単には暗号文にノイズを付与することで，安全性を保証しており，
暗号文を何度も演算するとノイズが増大する問題は，ブートストラップと呼ばれる技術で解消できます．
このブートストラップを実用性のあるものにすべく，TorusベースのTFHE方式（提唱者の頭文字をとってCGGI方式とも）が考えられました．
しかし，このTFHE方式の暗号化では，暗号文に任意の演算，特に非線型演算($\exp$とか)を与えるのが難しいとされていました．
アイディア
従来のブートストラップにleveled operation（演算回数に制限をつける）で解決です
結果
暗号文で任意の演算が可能になりました．やったね！
それらを元に各章を整理すると，次のようになります:
1章：イントロ
2章：前提知識
3章：TFHE方式
4章：ブートストラップとプログラマブルブートストラップ
5章：Neural Network への応用
つまり，３章と４章の前半までが「準備段階」で，４章の後半が一番言いたいことになります．
ただ，発想自体は別に難しいものではなく，むしろ「準備段階」が一番難しいです．
２章のポイント
Torus 上のLWE問題（TLWE問題）とRLWE問題（TRLWE問題）がメインです．Torusは「0以上1未満の実数全体の集合」と思っておけば今回は問題ありません．
LWE問題とは，秘密鍵をランダムベクトルでマスキングした後に平文とノイズを加えると，平文を復号するのは困難という問題です．これはノイズを加えると，平文を一意的に特定するのが難しいためであり，あえてノイズを加えることが重要です．
ノイズは正規分布に従う実数です．
3章のポイント
ここから項目ごとに解説します．
まず，３章前説では Torus の離散化についてです．
続く3.1では，cleartext（生データのこと） から plaintext（平文というより，暗号化アルゴリズムの input の方がイメージとして正確）への encode とその逆操作である decode を扱います．
3.2は，TRLWE問題に基づく plaintext から ciphertext への暗号化とその逆操作である復号化です．
最後の3.3では，上記の ciphertext 同士の演算についてとなります．
３章前説
$\mathbb{T}$ を $\mathbb{Z} / q \mathbb{Z}$ で離散化します（$q$ は2べき）
これ以降 Torus は出てきません
3.1
cleartext から plaintext への encode/decode を扱います．意外とこの論文の基礎となっている部分で，特に plaintext の構成を理解することが重要です．
これは，plaintext 全体を $\Omega$ bit として，先頭から見て
先頭 $\bar{w}$ bit → padding bit
続く $w$ bit → cleartext 用の bit
1 bit 空ける
後ろ $\Omega - (\bar{w} + w) - 1$ bit → ノイズ格納用 bit
となっています．予め，どこになんの情報が入るのかを意識することが重要です．
ノイズを下位ビットに配置することで，欲しい情報は上位bitに格納されます．本論文では，Upper関数というものを使って，取り出すように定義しています．
3.2
plaintext から ciphertext への暗号化/復号化を扱います．2章で出てきたTRLWE問題を安全性の根拠としています．
暗号化はTRLWE問題をそのまま活かしていることを意識するといいと思います．
この辺からノイズの影響を気にしないといけない部分が増えてきて，議論が煩雑になってきます．しかし，ノイズさえ無視できる範囲と仮定すればやっていること自体は普通の暗号化/復号化と同じだと気づけるはずです．
3.3
暗号文同士の演算を考えます．まず，加法とスカラー倍が成り立ちますが，これはTorusでも成り立っていたので，むしろ成り立っていないと困るものです．
そして一番厄介なのが External product です．しかも，3.2での暗号化方式とは別のGGSW方式という暗号化での暗号文との掛け算を考えます．
Torusでは掛け算は考えないのではないか，と思うかもしれませんが，3章前説で $\mathbb{Z} / q \mathbb{Z}$ で離散化したことを思い出すと，TorusであってTorusでない状況なので，掛け算も考えられる（実際に行うのは掛け算ではなくスカラー倍ですが），ということです．
一見すると意味不明なことをやっているように思えますが，GGSW方式の暗号化は実はかなり単純で，TRLWE方式で０を暗号化したものをノイズとみなし，平文に対しては簡単に逆行列を求められる行列によってマスキングすることで構成しています．
そして，GGSW方式の暗号文を gadget decomposition と呼ばれる方法を使って，スカラーベクトルに近似することで，暗号文の掛け算を実装しています．
ちなみに gadget decomposition も難しそうに聞こえますが，やっていることは結局 $B$ 進展開を $\ell$ 桁で打ち止めているだけです．
4章のポイント
4章では，bootstrap についてです．bootstrap とは，暗号文からノイズを取り除く手法を表します．
4.1では，従来の bootstrap を扱います．Blind Rotation, Sample Extraction, Key Exchange という３つのアルゴリズムの合成によって実現します．
Blind Rotation には，Rescaling と呼ばれる要素の範囲を制限するアルゴリズムも含んでいます．Rescaling によって，係数を多項式の肩に乗せることができるようになり，これによって，元のベクトルのノイズを取り除くことが容易になります．
しかし，Blind Rotation によって，出力が多項式になる・暗号化による秘密鍵が変更される，という問題が起こり，それぞれを Sample Extraction, Key Exchange という２つのアルゴリズムによって解消しています．
4.2では，本論文のメインとなる programmable bootstrap についてです．
一旦 test polynomial の要素を plaintext まで戻すことで，（$\mathrm{mod} \ w$の制限はあるものの）要素に任意の関数を作用させることができるようになったのがこの論文の新規性，ということになります．
内容としては，以上になります．長くなりましたが，お疲れ様でした（自分向け）．
連載を完走した感想としては，正直Qiitaではインラインでの数式が書きづらすぎました．論文解説はZennで続けて，Qiitaではコードメインでこれまで通り量子に戻ろうと思います．
Zennでは，来月からイデアル格子暗号入門，４月からGSW方式の原論文である Homomorphic Encryption from Learning with Errors:Conceptually-Simpler, Asymptotically-Faster, Attribute-Based を解説しようと思っていますので，興味のある方はご覧ください．