この記事は EAGLYS Advent Calendar 2022 の19日目の記事です
はじめに
TFHEに触れ始めてから１年弱経ったこともあり，人に聞かれることも増え始めてきたこの頃，今回のアドカレでTFHE関連の話題を予備知識なしの状態から始めて，詳細までまとめようと思います
突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください
今回のアドカレの関連記事（気になるところから読んでください）
TFHEの概要
１日目：Torus・TLWEの概要
５日目：TRLWE・TFHEの概要
10日目：プログラマブルブートストラップの概要
TFHEの詳細
11日目:TFHEの暗号化方式の詳細（前半）
12日目:TFHEの暗号化方式の詳細（後半）
18日目：プログラマブルブートストラップの詳細（前半）
19日目(イマココ)（プログラマブルブートストラップの詳細（後半））：
TFHEの最新動向
20日目：TFHEの最新動向（2022年版）
前回の続きです．前回はbootstrapの概要・Rescaling・Blind Rotation・Sample Extractionを扱いました．
今回はKey Switching・bootstrapのまとめ・programmable bootstrapを扱います．
はじめに
この記事は，昨年のアドカレの記事
「プログラマブルブートストラップの原著論文を理解する回」を理解する回 4/4
のリメイク版となります．
分かりづらかった箇所の修正を行なったり，構成を入れ替えたり，そのとき書けなかった話を加えています
＊具体例とか修正がない箇所もありますが，それはその都度明示します
1/4, 2/4 の記事は基本的に修正しません（と言っても今回の記事で一部リメイクします）が，それらの記事のサマリーは概要と称して，今回の1,5日目に載せていますので，そちらをご参照ください
Key Switching
gadget decomposition 自体は 「プログラマブルブートストラップの原著論文を理解する回」を理解する回 3/4 を参照ください
長さ $\ell$ での $\beta$ 進展開する際の gadget decompoisiton の計算量は
- $\mathbb{Z} / q \mathbb{Z}$ での足し算 : $2 \ell$ 回
- $\mathbb{Z} / q \mathbb{Z}$ での掛け算 : $\ell$ 回
で，TLWE方式の計算量は
- $\mathbb{Z} / q \mathbb{Z}$ での足し算 : $n + 1$ 回
- $\mathbb{Z} / q \mathbb{Z}$ での掛け算 : $n$ 回
になり，そのときの引数の計算量は
- $\mathbb{Z} / q \mathbb{Z}$ での掛け算 : 2回
です．よって，1-6行目でのループの計算量は
- $\mathbb{Z} / q \mathbb{Z}$ での足し算 : $k N \ell(n + 3)$ 回
- $\mathbb{Z} / q \mathbb{Z}$ での掛け算 : $k N \ell(n + 3)$ 回
です．7行目の計算量は
- $\mathbb{Z} / q \mathbb{Z}$ での足し算 : $k N \ell n$ 回
- $\mathbb{Z} / q \mathbb{Z}$ での掛け算 : $k N \ell (n + 1)$ 回
ですから，Key Switching トータルでの計算量は，
- $\mathbb{Z} / q \mathbb{Z}$ での足し算 : $k N \ell (2 n + 3)$ 回
- $\mathbb{Z} / q \mathbb{Z}$ での掛け算 : $2 k N \ell (n + 2)$ 回
となります．
bootstrapのまとめ
bootstrap での計算量を考えてみると，
Rescaling
- $\mathbb{Z} / q \mathbb{Z}$ での足し算 : 0 回
- $\mathbb{Z} / q \mathbb{Z}$ での掛け算 : $3(n + N + 1)$ 回
Blind Rotation
- $\mathbb{Z} / q \mathbb{Z}$ での足し算 : $(k + 1) n \ell((k + 1)N^2 + (n + 1)N + (k + 1)) + n$ 回
- $\mathbb{Z} / q \mathbb{Z}$ での掛け算 : $(k + 1) n \ell (n + k + 1) N^2$ 回
Sample Extraction
- $\mathbb{Z} / q \mathbb{Z}$ での足し算 : 0 回
- $\mathbb{Z} / q \mathbb{Z}$ での掛け算 : $k (N - 1)$ 回
Key Switching
- $\mathbb{Z} / q \mathbb{Z}$ での足し算 : $k N \ell (2 n + 3)$ 回
- $\mathbb{Z} / q \mathbb{Z}$ での掛け算 : $2 k N \ell (n + 2)$ 回
となるので，bootstrap を実行した際には，Blind Rotation の部分でかなり時間がかかりそうだということがこのことからもわかるし，
bootstrap の計算量を下げたいと思うなら，まず初めに Blind Rotation を削減しようと考えればOKなわけです
programmable bootstrap
$\tilde{D}, \tilde{I}$ を $\mathbb{Z} / q \mathbb{Z}$ の部分集合とするとき，$f : \tilde{D} \rightarrow \tilde{I}$ とすると，$\tilde{D}, \tilde{I}$ は 任意の部分集合なので，暗号文に$\mathbb{Z} / q \mathbb{Z}$ 上の任意の関数を作用させることができます
まとめ
リメイクでは bootstrap の計算量という観点から振り返ってみました
予想通りというか，Blind Rotation がかなりネックなことを理論的に示しました
今後もTFHEの理解を深めていきたいなと！話題ができたらリメイクのリメイクするかもです
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！