一番言いたいことは３章と４章です．
２章については，TFHEの暗号化方式と bootstrap に関するアルゴリズム（Key Switching, Blind Rotation, Sample Extraction）がまとめられています
＊必要最低限って感じですし，TFHEの復号については触れられていないので，この辺は別途参照ですね

こう見ると，TFHEのサーベイ論文と読むことができます，今後リファレンスとして重宝しそうな予感がします
今回は３章と４章をさらっとまとめます

３章のまとめ

初めに，これまで提案されてきたTFHEのアルゴリズムについてまとめます
まずは，論文中に登場している順で:

Functional Bootstrap
Improved Programmable Bootstrap
Multi-Value Functional Bootstrap
Tensor product
Full-Domain Functional Bootstrap
Evaluating large Lookup tables
Circuit Bootstrap
Full TRGSW bootstrap
T(R)LWE conversion
BlindRotate Unfolding
Public Key compression

ほとんどが bootstrap 全般に関わるって感じです．任意の関数 $f$ やLUTへの扱いで色々あるイメージ．

それではそれぞれのアルゴリズムを簡単にまとめます．引用の上に書いてある数字は，論文と合わせています．

$\underline{\mathrm{Functional \ Bootstrap}}$
初めて提案されたのは2019年:

[5]
Christina Boura, Nicolas Gama, Mariya Georgieva, and Dimitar Jetchev. 2019. Simulating Homomorphic Evaluation of Deep Learning Predictions.
In Cyber Security Cryptography and Machine Learning, Shlomi Dolev, Danny Hendler, Sachin Lodha, and Moti Yung (Eds.). Springer International
Publishing, Cham, 212–230.

Lookup Table(LUT)で離散化された任意の関数に対しての gate bootstrap (1)の一般化と見ることができる
しかし，この方法自体は，既に提案されている(2)

多変数関数に対して，評価を行える手法も提案されている:

[25]
Antonio Guimarães, Edson Borin, and Diego F. Aranha. 2021. Revisiting the functional bootstrap in TFHE. IACR Transactions on Cryptographic
Hardware and Embedded Systems 2021, 2 (Feb. 2021), 229–253.

途中の引用
(1)
[14]
Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. 2020. TFHE: fast fully homomorphic encryption over the torus. Journal of
Cryptology 33, 1 (2020), 34–91.

(2)
[18]
Léo Ducas and Daniele Micciancio. 2015. FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second. In Advances in Cryptology –
EUROCRYPT 2015, Elisabeth Oswald and Marc Fischlin (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 617–640.

[33]
Daniele Micciancio and Yuriy Polyakov. 2020. Bootstrapping in FHEW-like Cryptosystems. Cryptology ePrint Archive, Report 2020/086.
https://eprint.iacr.org/2020/086

$\underline{\mathrm{Improved \ Programmable \ Bootstrap}}$
初めて提案されたのは2020年:

[15]
Ilaria Chillotti, Marc Joye, and Pascal Paillier. 2021. Programmable Bootstrapping Enables Efficient Homomorphic Inference of Deep Neural
Networks. In Cyber Security Cryptography and Machine Learning, Shlomi Dolev, Oded Margalit, Benny Pinkas, and Alexander Schwarzmann (Eds.).
Springer International Publishing, Cham, 1–19.

functional bootstrap とほとんど同じ手法だが，TFHEの離散化する際の notation が異なる．

上記からの改善版も提案されている:

[16]
Ilaria Chillotti, Damien Ligier, Jean-Baptiste Orfila, and Samuel Tap. 2021. Improved Programmable Bootstrapping with Larger Precision and Efficient
Arithmetic Circuits for TFHE. In Advances in Cryptology – ASIACRYPT 2021, Mehdi Tibouchi and Huaxiong Wang (Eds.). Springer International
Publishing, Cham, 670–699.

$\underline{\mathrm{Multi-Value \ Functional \ Bootstrap}}$
初めて提案されたのは2019年:

[9]
Sergiu Carpov, Malika Izabachène, and Victor Mollimard. 2019. New Techniques for Multi-value Input Homomorphic Evaluation and Applications.
In Topics in Cryptology – CT-RSA 2019, Mitsuru Matsui (Ed.). Springer International Publishing, Cham, 106–126.

同じインプットに対して，異なる関数を評価する手法であり，単体の functional bootstrap や programmable bootstrap を繰り返し使用するより計算量が削減できる．

Multi-Value Functional Bootstrap と既存の functional bootstrap を組合せたものが[25]であり，
Multi-Value Functional Bootstrap と既存の programmable bootstrap を組合せたものが[16]である．

$\underline{\mathrm{Tensor \ product}}$
既存手法そのものが初めて提案されたのは2012年, 2017年:

[11]
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. 2017. Homomorphic Encryption for Arithmetic of Approximate Numbers. In
Advances in Cryptology – ASIACRYPT 2017, Tsuyoshi Takagi and Thomas Peyrin (Eds.). Springer International Publishing, Cham, 409–437.

[20]
Junfeng Fan and Frederik Vercauteren. 2012. Somewhat Practical Fully Homomorphic Encryption. Cryptology ePrint Archive, Report 2012/144.
https://ia.cr/2012/144.

サンプル同士のTensor積を表現するRLWE問題に基づくFHE方式の導入を上記で行なっている．特に[20]はBFVライクなTensor積（らしい，よくわからん）．

この辺は[16]が詳しい．

$\underline{\mathrm{Full-Domain \ Functional \ Bootstrap}}$
初めて提案されたのは2021年:

[17]
Pierre-Emmanuel Clet, Martin Zuber, Aymen Boudguiga, Renaud Sirdey, and Cédric Gouy-Pailler. 2022. Putting up the swiss army knife of
homomorphic calculations by means of TFHE functional bootstrapping. Cryptology ePrint Archive, Report 2022/149.
https://ia.cr/2022/149.

[29]
Kamil Kluczniak and Leonard Schild. 2021. FDFB: Full Domain Functional Bootstrapping Towards Practical Fully Homomorphic Encryption.
Cryptology ePrint Archive, Report 2021/1135.
https://ia.cr/2021/1135.

[38]
Zhaomin Yang, Xiang Xie, Huajie Shen, Shiying Chen, and Jun Zhou. 2021. TOTA: Fully Homomorphic Encryption with Smaller Parameters and
Stronger Security. Cryptology ePrint Archive, Report 2021/1347.
https://ia.cr/2021/1347.

任意の関数 $f$ をいくつかの関数に分割して，それぞれを評価する手法．
他にも[16]がある．色々文献があるが，全て違う方針っぽい．

$\underline{\mathrm{Evaluating \ large \ Lookup \ tables}}$
初めて提案されたのは2021年，[16]と[25]が詳しい．

LUTのサイズが暗号系のパラメタによって制限されるのを取り除いた手法のこと．

$\underline{\mathrm{Circuit \ Bootstrap}}$
初めて提案されたのは2016年の原論文、その後の詳しい説明↓:

[14]
Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. 2020. TFHE: fast fully homomorphic encryption over the torus. Journal of
Cryptology 33, 1 (2020), 34–91.

TRLWEのサンプルからTRGSWのサンプルへ生成する手法のこと．

$\underline{\mathrm{Full \ TRGSW \ bootstrap}}$
[9], [16], [25]が詳しい．

accumulator vector （Blinde Rotationで出てくる）がTRLWEではなくTRGSWになっている手法のこと．

$\underline{\mathrm{T(R)LWE \ conversion}}$
初めて提案されたのは2021年:

[10]
Hao Chen, Wei Dai, Miran Kim, and Yongsoo Song. 2021. Efficient Homomorphic Conversion Between (Ring) LWE Ciphertexts. In Applied
Cryptography and Network Security, Kazue Sako and Nils Ole Tippenhauer (Eds.). Springer International Publishing, Cham, 460–479.

TRLWEの Key Switching を使って，TLWE の Key Switching を実現する手法のこと．

$\underline{\mathrm{BlindRotate \ Unfolding}}$
初めて提案されたのは2018年:

[40]
Tanping Zhou, Xiaoyuan Yang, Longfei Liu, Wei Zhang, and Ningbo Li. 2018. Faster Bootstrapping With Multiple Addends. IEEE Access 6 (2018),
49868–49876.

Blind Rotation の掛け算の回数を削減する手法のこと．
[40]を改善したのが同年に出ている:

[6]
Florian Bourse, Michele Minelli, Matthias Minihold, and Pascal Paillier. 2018. Fast Homomorphic Evaluation of Deep Discretized Neural Networks.
In Advances in Cryptology – CRYPTO 2018, Hovav Shacham and Alexandra Boldyreva (Eds.). Springer International Publishing, Cham, 483–512.

$\underline{\mathrm{Public \ Key \ compression}}$
初めて提案されたのは[14]．

鍵長が指数的に増えるのを線型で抑える手法のこと．
なんか色々変種がある（最後なので疲れた）．

総括
[16], [25]を読めばほぼ抑えられる感じですね（後，[9]も），結局 functional bootstrap と programmable bootstrap の最新版に大体書いてあるってことになります
後は，Full−Domain Functional Bootstrap の変種を確認すれば良い気がします
（最後の３つはどれほど重要なのかまだよく分からんです）

４章のまとめ

これまで提案されてきたTFHEのライブラリは次のようになります．

TFHEpp
Concrete
PALISADE

TFHEpp

Concrete

PARISADE
https://palisade-crypto.org/

TFHEppのことをべた褒めしていました()パラメタや最適化のレベルもこれに沿って行なっているようです．

終わりに

こうしてみると，TFHEってめちゃめちゃ派生系のアルゴリズムがあって，たくさんのライブラリがあるんだなぁと実感しました（小並感）
programmable bootstrap の原論文だけ読んで満足していましたが，これの改善版もあり，似たような functional bootstrap もあり，他の派生系もありで，まだまだキャッチアップが足りないなと
この論文をきっかけに改めてサーベイをきっちりやって，知識も増やしていきたいです

今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！

今後とも，TFHEに関する論文が出てきたら，今回みたいにさらっとまとめることはやっていこうかなと思います．

本論文全体の流れ

３章のまとめ

４章のまとめ

終わりに

Discussion