今までZennでもQiitaでも「本論文の理論を深く理解する」という目的で，連載を始めました．
しかし，全ての人がそこまで必要ではありません．例えば「TFHE方式の暗号化のアルゴリズムだけやりたいんだけど，Zenn の第１回から読まないといけないの？」と聞かれたら，そんなことはありません．~~Torus はマジで必要ないし．~~

また，各論を深く理解しても結局全体の流れがどうだったのかを意識できなければ，その理論を応用したり，似たような議論に出会ったときに統一的な視点で理解するのは難しいです．

「木を見て森を見ず」になってしまわないかなと思ったので，各章で「どういうことをやりたいのか」・「なんでそれができるのか」をポイントを絞って１つの記事にしてみました．
キーワードの簡単な説明を織り交ぜながら，各章のモチベーションやポイントを簡単に解説します．

各記事の位置付け

全体で４つに分けられます．
Qiitaまとめ：
こちらは論文の各章のポイントをまとめた記事になります．これを読むことで，何をやるためにどうすればいいのか，が簡潔にキーワードを含めて理解できるようになっています（たぶん）．

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$ の制限はあるものの）要素に任意の関数を作用させることができるようになったのがこの論文の新規性，ということになります．

本論文を読むにあたっての注意点

本論文を理解する際に集中的に読むべき箇所
読みづらい原因

この2つを解説します．

まず，集中的に読むべき箇所ですが，

2.2
Appendix A
3章前説
3.1
3.2
4.1
Appendix B

これら７つです．といっても，確率分布やLWE問題をご存知の方は，それぞれ 2.2 や Appendix A は飛ばして読めます．あと，3章前説も Torus を $\mathbb{Z} / q \mathbb{Z}$ で離散化することさえ意識できれば飛ばしてもいいかもしれません．
４つでトータル５ページぐらいですが，それでも分かりづらい方のために，連載記事を書いた（唐突な宣伝）ので，そちらを参照しながら読むとスッと理解できると思います．

逆にさらっと流すだけで十分な箇所は，

の３つです．理由としては，

2.1：Torus は3章前説で離散化して以来使わないため，多項式環をご存知でない方はそこは読んでください（Appendix A 以降ずっと使うため）
3.3：Leveled operation は足し算とスカラー倍とCMuxでやりたいことが分かれば十分（具体的な演算回数に言及しているわけでもなく，ノイズの議論もやりたいならやればいいだけなので）
4.2：programmable bootstrap はそもそも大したことやってない（え）

ためです．そして，理解しようと思うと，2.1 と 3.3 にかなり時間が取られるのも事実だからです．

次に読みづらい原因についてです．これは別にディスっているわけではなく，この辺りを注意して読まないと混乱する可能性がある，という話です．これらを整理するために連載記事を始めたので．

数学的な内容や流れなどについてですが，

ベクトルは縦ベクトルが通例（Tensor積でぐちゃぐちゃ）
同値類はさすがに理解してほしい（lift 関数の定義がめちゃくちゃ）
LWE問題の説明でなぜ分布の識別で取り上げたのか

などなど，もうちょいしっかりしてほしいなという印象が目立ちました．特に最後は，その後の暗号化との接続を考えて求解困難性にしなかった理由が分からなかったです．正直「あえて読みづらくしている」ように思えました．

後は雑だなと思った細かいところとして，

変数設定
ネーミングセンス
定式化
込み入った議論

あたりですかね．1つ1つ細かくは触れません（というか連載の各所で触れている）これまでの連載でかなり整理したつもりですが，まだ分かりやすく改良できる余地があると思っています．

感想

連載を完走した感想です．

TFHEの原論文をいくつか前提にしている箇所があって，それなら引用してくれればいいのに，それがないせいで論理の飛躍が多かったです．これの連載が終わったら，上記の TFHEの原論文も解説記事を書こうかと思ったのですが，正直読みたくないな・・・っていう感じです．理論的なものがこんな感じなら，コードも本当に正しいのか・・・？と不安になったのもあります．

前節からマイナスイメージが続いてしまったので，プラスイメージのものを書いて締めようと思います．
実はIntroductionが綺麗にまとまっていて分かりやすいです．~~本記事では一切触れていませんが．~~ 準同型暗号ベースの秘密計算の流れがまとまっていて，個人的にはかなり好きです．触れていない関連で5章の Neural Network への応用も分かりやすいとかなんとか．
また，図がちょこちょこあったのも分かりやすかったかなと．個人的には，cleartext から plaintext への変換を文字だけで伝えるのはめんどくさいので，図があった方が伝えやすいなーと思いました．後は，programmable bootstrap の look-up table とかも図式が記載されていて，図式に慣れている方には分かりやすいかなと．

今後の展望

論文をしっかり理解するシリーズは「GSW方式の原著論文」→「イデアル格子暗号入門」まで決まっているので，次回はイデアル格子暗号入門を来月から解説します．
- また，４月には，Homomorphic Encryption from Learning with Errors:
  Conceptually-Simpler, Asymptotically-Faster, Attribute-Based を解説しようと思います（３月は忙しそう）．GSW方式の原論文です．
こんな感じでこれからも耐量子計算機暗号や秘密計算関連の論文の解説記事をZennで書こうと思います．もしよろしければ今後ともよろしくお願いします．

今回の目次

なぜ今回の記事が必要なのか