😸

MOSFHETを読む

2022/05/06に公開約9,100字

今週5/2にIACRに掲載されたプレプリント(以下めんどいので論文とかペーパーとか)について,簡単に解説します.

対象とするペーパーとGithubのリンクは次のとおりです:

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

上記のGithub

この記事の目標は,これまでTFHEのアルゴリズムとライブラリがどのような変遷を経てきたのかを理解することです

本論文全体の流れ

  • どういう背景や課題・モチベーションがあって,
  • どのようなアイディアのもとで,
  • どのような結果が得られたのか

を整理します.

背景・課題
TFHE方式に関して,色々な方式が提案されていますが,様々な実装があり,比較するのが難しい

アイディア
これまで提案されている方式をまとめる
そして,全ての実装を1つのライブラリにまとめて最適化まで行う

結果
MOSFHETなるライブラリを作成し,Intel AVX2, FMA と AVX-512 での最適化を行なった

それらを元に各章を整理すると,次のようになります:

1章:イントロ
2章:TFHEの導入
3章:これまで提案されてきたTFHE関係のアルゴリズムのまとめ
4章:3章の実装と既存のライブラリとの実行時間の比較
5章:まとめ

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

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

3章のまとめ

初めに,これまで提案されてきた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.

https://doi.org/10.1007/978-3-030-20951-3_20

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.

https://doi.org/10.46586/tches.v2021.i2.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.

https://doi.org/10.1007/s00145-019-09319-x

(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.

https://link.springer.com/chapter/10.1007/978-3-662-46800-5_24

[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.

https://doi.org/10.1007/978-3-030-78086-9_1

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.

https://link.springer.com/chapter/10.1007/978-3-030-92078-4_23

\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.

https://doi.org/10.1007/978-3-030-12612-4_6

同じインプットに対して,異なる関数を評価する手法であり,単体の 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.

https://link.springer.com/chapter/10.1007/978-3-319-70694-8_15

[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.

https://doi.org/10.1007/s00145-019-09319-x

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.

https://doi.org/10.1007/978-3-030-78372-3_18

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.

https://doi.org/10.1109/ACCESS.2018.2867655

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.

https://doi.org/10.1007/978-3-319-96878-0_17

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

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


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

4章のまとめ

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

  • TFHEpp
  • Concrete
  • PALISADE

TFHEpp

https://github.com/virtualsecureplatform/TFHEpp

Concrete

https://link.springer.com/chapter/10.1007/978-3-030-78086-9_1

PARISADE

https://palisade-crypto.org/

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

終わりに

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


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

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

Discussion

ログインするとコメントできます