TFHEの最新動向（2022年版）

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

# はじめに

TFHEに触れ始めてから１年弱経ったこともあり，人に聞かれることも増え始めてきたこの頃，今回のアドカレでTFHE関連の話題を予備知識なしの状態から始めて，詳細までまとめようと思います

**突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください**

今回のアドカレの関連記事（気になるところから読んでください）

#### TFHEの概要
１日目：[Torus・TLWEの概要](https://qiita.com/0917laplace/items/1c5f35e0397de2d19062)
５日目：[TRLWE・TFHEの概要](https://qiita.com/0917laplace/items/b9fd6603ad9fe0a23ec9)
10日目：[プログラマブルブートストラップの概要](https://qiita.com/0917laplace/items/ad1d9e1920d516086d9b)

#### TFHEの詳細
11日目:[TFHEの暗号化方式の詳細（前半）](https://qiita.com/0917laplace/items/0635aa2598a9528e3a7f)
12日目:[TFHEの暗号化方式の詳細（後半）](https://qiita.com/0917laplace/items/0dc6f6c9bb512425cc9a)
18日目:[プログラマブルブートストラップの詳細（前半）](https://qiita.com/0917laplace/items/efc5013a4d50fbae6ea4)
19日目（プログラマブルブートストラップの詳細（後半））：

#### multi-key TFHEの概要
15日目（multi-key TFHEの概要）：

#### TFHEの最新動向
20日目(イマココ)（TFHEの最新動向（2022年版））：

今回はTFHEの最新動向に関して，理論に絞って書いていきます
初めに今年読んだ（or読んでいる）TFHE関連のePrintを紹介し，その後に今年出たePrintをさらっていきます（arXivは本数少なかったので今回は割愛します）

# A. Guimarães, E. Borin, D. F. Aranha:``MOSFHET: Optimized Software for FHE over the Torus'', Cryptology ePrint Archive, Report 2022/515, 2022.

[上記のePrint](https://eprint.iacr.org/2022/515.pdf)

[上記のGithub](https://github.com/antoniocgj/MOSFHET)

これはサーベイePrintで，TFHEの理論を追いたいなら，まずはこのePrintから見るといいと思います
出たのも今年の５月ですし，かなり良くサーベイされています

~~MOSFHETのMってなんだっけっていつも忘れるんですが，特に意味はないんですよね・・・~~

プログラマブルブートストラップと functional bootstrap(プログラマブルブートストラップと同じもの，同じぐらいの時期に別の人たちが提案したから混在しているらしい)から始まり，multi-value bootstrap などもまとめられています

＊プログラマブルブートストラップの概要は今回の10日目の記事を [プログラマブルブートストラップの概要](https://qiita.com/0917laplace/items/ad1d9e1920d516086d9b)

また，Blind RotationやKey Switching の最適化などもまとまっていて，ひとまずこれを見ておけば，自分がやりたいことに対してどの論文を参照すればいいかわかると思います

ついでに？僕が書いた記事を載せておきます↓

[MOSFHETを読む](https://zenn.dev/0917laplace/articles/9a80b68cdd3927)

# M. Joye, M. Walter: ``Liberating TFHE: Programmable Bootstrapping with General Quotient Polynomial'', Cryptology ePrint Archive, Report 2022/1177, 2022.

[上記のePrint](https://eprint.iacr.org/2022/1177.pdf)

考える剰余環を拡張することで，TFHEの一般化も狙うePrintです

ちなみに理論的な話が多いので，実装だけ知りたい方にはおすすめできません()
~~でも書いている人Zamaの人だしいずれconcreteに組み込まれそうですが~~

このePrintを読む上で・円分多項式とかFFTの知識は必須だと思います

ついでに？僕が書いた記事を載せておきます（未完ですが・・・）↓

[【ePrint解説】Liberating TFHE　1/4](https://zenn.dev/0917laplace/articles/76f06dcf137a9a)

# H. Kwak, S. Min, Y. Song: ``Towards Practical Multi-key TFHE: Parallelizable, Key-Compatible, Quasi-linear Complexity'', Cryptology ePrint Archive, Report 2022/1460, 2022.

[上記のePrint](https://eprint.iacr.org/2022/1460.pdf)

multi-key TFHE の原論文
[H. Chen, I. Chillotti, Y. Song: ``Multi-key homomorphic encryption from TFHE'', In: International Conference on the Theory and Application of Cryptology and Information Security. Springer, Cham, pp.446-472, 2019.](https://link.springer.com/chapter/10.1007/978-3-030-34621-8_16) の改善版です
＊[上記のePrint](https://eprint.iacr.org/2019/116.pdf)

正直multi-key TFHE の原論文がかなり読みづらいので，こっちのePrintでまとまっている方を確認してから，原論文に戻るやり方で現状読んでいます

どちらかというとこちらも理論的な論文（そもそもmulti-key TFHEの実装が現状かなり少ない）ですので，実装だけ知りたい方にはこちらも勧められないかもです・・・

multi-key プロトコル（というより複数人登場するプロトコル）の場合，誰がそのアルゴリズムを動かすのか，というのが実用上（でもプロトコルを理解する上でも）非常に重要なのですが，そこまで言及されていてすごく読みやすいです

TFHEも最低限まとまっていて，学会とかにそのまま出せる完成度だと思います

ここからは2022年に出たTFHE関連のePrintをさらっと見ていきます

# 2022年に出たePrint一覧

なるべく時系列順になるようにします
＊2022年12月27日現在withdrawnのものは対象外

|著者  |タイトル  |number  |URL |
|---|---|---|---|
|J. Klemsa, M. Önen|Parallel Operations over TFHE-Encrypted Multi-Digit Integers|2022/067|https://eprint.iacr.org/2022/067.pdf|
|C. Bonte, I. Iliashenko, J. Park, H.V.L. Pereira, N.P. Smart|FINAL: Faster FHE instantiated with NTRU and LWE|2022/074|https://eprint.iacr.org/2022/074.pdf|
|K. Kluczniak|NTRU-$\nu$-um: Secure Fully Homomorphic Encryption from NTRU with Small Modulus|2022/089|https://eprint.iacr.org/2022/089.pdf|
|P.-E. Clet, M. Zuber, A. Boudguiga, R. Sirdey, C. Gouy-Pailler|Putting up the swiss army knife of homomorphic calculations by means of TFHE functional bootstrapping|2022/149|https://eprint.iacr.org/2022/149.pdf|
|O. Cosseron, C. Hoffmann, P. Méaux, F.-X. Standaert|Towards Globally Optimized Hybrid Homomorphic Encryption - Featuring the Elisabeth Stream Cipher|2022/180|https://eprint.iacr.org/2022/180.pdf|
|Y. Lee, D. Micciancio, A. Kim, R. Choi, M. Deryabin, J. Eom, D. Yoo|Efficient FHEW Bootstrapping with Small Evaluation Keys, and Applications to Threshold Homomorphic Encryption|2022/198|https://eprint.iacr.org/2022/198.pdf|
|T. Feneuil, J. Maire, M. Rivain, D. Vergnaud|Zero-Knowledge Protocols for the Subset Sum Problem from MPC-in-the-Head with Rejection|2022/223|https://eprint.iacr.org/2022/223.pdf|
|A. Guimarães, E. Borin, D.F. Aranha|MOSFHET: Optimized Software for FHE over the Torus|2022/515|https://eprint.iacr.org/2022/515.pdf|
|I. Iliashenko, M. Izabachène, A. Mertens, H.V.L. Pereira|Homomorphically counting elements with the same property|2022/572|https://eprint.iacr.org/2022/572.pdf|
|O. Chakraborty, M. Zuber|Efficient and Accurate homomorphic comparisons|2022/672|https://eprint.iacr.org/2022/622.pdf|
|B. Chaturvedi, A. Chakraborty, A. Chatterjee, D. Mukhopadhyay|Error Leakage using Timing Channel in FHE Ciphertexts from TFHE Library|2022/685|https://eprint.iacr.org/2022/685.pdf|
|L. Bergerat, A. Boudi, Q. Bourgerie, I. Chillotti, D. Ligier, J.-B. Orfila, S. Tap|Parameter Optimization & Larger Precision for (T)FHE|2022/704|https://eprint.iacr.org/2022/704.pdf|
|A.A. Badawi, J. Bates, F. Bergamaschi, D.B. Cousins, S. Erabelli, N. Genise, S. Halevi, H. Hunt, A. Kim, Y. Lee, Z. Liu, D. Micciancio, I. Quah, Y. Polyakov, K. Rohloff, R.V. Saraswathy, J. Saylor, D. Suponitsky, M. Triplett, V. Vaikuntanathan, V. Zucca|OpenFHE: Open-Source Fully Homomorphic Encryption Library|2022/915|https://eprint.iacr.org/2022/915.pdf|
|S. Azogagh, V. Delfour, S. Gambs, M.-O. Killijian|PROBONITE : PRivate One-Branch-Only Non-Interactive decision Tree Evaluation|2022/936|https://eprint.iacr.org/2022/936.pdf|
|M. Joye, M. Walter|Liberating TFHE: Programmable Bootstrapping with General Quotient Polynomial|2022/1177|https://eprint.iacr.org/2022/1177.pdf|
|N. Drucker, G. Moshkowich, T. Pelleg, H. Shaul|BLEACH: Cleaning Errors in Discrete Computations over CKKS|2022/1298|https://eprint.iacr.org/2022/1298.pdf|
|J. Klemsa|Hitchhiker’s Guide to a Practical Automated TFHE Parameter Setup for Custom Applications|2022/1315|https://eprint.iacr.org/2022/1315.pdf|
|F. Bourse, M. Izabachène|Plug-and-play sanitization for TFHE|2022/1438|https://eprint.iacr.org/2022/1438.pdf|
|K. Kluczniak|Circuit Privacy for FHEW/TFHE-Style Fully Homomorphic Encryption in Practice|2022/1459|https://eprint.iacr.org/2022/1459.pdf|
|H. Kwak, S. Min, Y. Song|Towards Practical Multi-key TFHE: Parallelizable, Key-Compatible, Quasi-linear Complexity|2022/1460|https://eprint.iacr.org/2022/1460.pdf|
|B. Chaturvedi, A. Chakraborty, A. Chatterjee, D. Mukhopadhyay|A Practical Full Key Recovery Attack on TFHE and FHEW by Inducing Decryption Errors|2022/1563|https://eprint.iacr.org/2022/1563.pdf|
|M.V. Beirendonck, J.-P. D'Anvers, I. Verbauwhede|FPT: a Fixed-Point Accelerator for Torus Fully Homomorphic Encryption|2022/1635|https://eprint.iacr.org/2022/1635.pdf|
|M. Walter|On Side-Channel and CVO Attacks against TFHE and FHEW|2022/1722|https://eprint.iacr.org/2022/1722.pdf|

今まで紹介してきたePrintは理論系だったので，実装に関して今後読んでみたいなと思っているePrintを３つほど紹介します

# L. Bergerat, A. Boudi et al.: ``Parameter Optimization & Larger Precision for (T)FHE'', Cryptology ePrint Archive, Report 2022/704, 2022.

[上記のePrint](https://eprint.iacr.org/2022/704.pdf)

TFHEのパラメタについてのePrintです

自分で設計するわけではないのですが，色々とパラメタをいじったりすることはあると思いますし，
かなりしっかり目に書かれている（ように見える）ので，一度は読んでおきたいシリーズのものなのかなと

# A.A. Badawi, J. Bates et al.: ``OpenFHE: Open-Source Fully Homomorphic Encryption Library'', Cryptology ePrint Archive, Report 2022/915, 2022.

[上記のePrint](https://eprint.iacr.org/2022/915.pdf)

[OpenFHEのGithub](https://github.com/openfheorg/openfhe-development)

OpenFHEに関するePrintです

理論的なことはそこそこに，実装の話などが多く書かれています

OpenFHEとは何か，とか，実際に動かしてみた結果などは↓の記事をご参照ください

[OpenFHEのバージョン１系が出た！！準同型暗号のIEEE標準化も間近か！？](https://qiita.com/kenmaro/items/de53308b2c964f7469b0)

[OpenFHE チュートリアル：　CKKS形式で演算＋近似演算＋ブートストラップの組み合わせにチャレンジしてみたかった。](https://qiita.com/kenmaro/items/44c42080b4056b3d2d58)

# M.V. Beirendonck, J.-P. D'Anvers, I. Verbauwhede: ``FPT: a Fixed-Point Accelerator for Torus Fully Homomorphic Encryption'', Cryptology ePrint Archive, Report 2022/1635, 2022.

[上記のePrint](https://eprint.iacr.org/2022/1635.pdf)

TFHEのbootstrapをFPGA上で動かしてみたっていう内容です

FPGAは本当に全然詳しくないのですが，さすがに読んでみようかなぁと思っています

# まとめ
今回は2022年に出てきたTFHEのePrintについてみてきました

ちょっと数が多くてまとめるのが大変だったので，今後は四半期ぐらいのペースでもうちょっと目を通す頻度を増やそうかなと考えています

参考までに [2023年 暗号と情報セキュリティシンポジウム（SCIS2023）](https://www.iwsec.org/scis/2023/) でもTFHEに関する発表がありますので，興味のある方はそちらの聴講もいかがでしょうか？（僕も来年TFHEで発表できたらなぁ・・・）

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