この記事は EAGLYS Advent Calendar 2022 の19日目の記事です

はじめに

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

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

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

前回の続きです．前回は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の理解を深めていきたいなと！話題ができたらリメイクのリメイクするかもです

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

（リメイク）「プログラマブルブートストラップの原著論文を理解する回」を理解する回 4/4（後半）

はじめに

TFHEの概要

TFHEの詳細

TFHEの最新動向

Key Switching

bootstrapのまとめ

programmable bootstrap

まとめ

（リメイク）「プログラマブルブートストラップの原著論文を理解する回」を理解する回　4/4（後半）