この記事は EAGLYS Advent Calendar 2022 の12日目の記事です
はじめに
TFHEに触れ始めてから１年弱経ったこともあり，人に聞かれることも増え始めてきたこの頃，今回のアドカレでTFHE関連の話題を予備知識なしの状態から始めて，詳細までまとめようと思います
突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください
今回のアドカレの関連記事（気になるところから読んでください）
TFHEの概要
１日目：Torus・TLWEの概要
５日目：TRLWE・TFHEの概要
10日目：プログラマブルブートストラップの概要
TFHEの詳細
11日目 : TFHEの暗号化方式の詳細（前半）
12日目（イマココ）（TFHEの暗号化方式の詳細（後半））：
18日目（プログラマブルブートストラップの詳細（前半））：
19日目（プログラマブルブートストラップの詳細（後半））：
multi-key TFHEの概要
15日目（multi-key TFHEの概要）：
TFHEの最新動向
20日目（TFHEの最新動向（理論編））：
25日目（TFHEの最新動向（実装編））：
前回の続きです．
前回は，TFHE方式のリメイクを行ないました．今回はGGSW方式のリメイクをします．
はじめに
この記事は，昨年のアドカレの記事
「プログラマブルブートストラップの原著論文を理解する回」を理解する回 3/4
のリメイク版となります．
分かりづらかった箇所の修正を行なったり，構成を入れ替えたり，そのとき書けなかった話を加えています
＊具体例とか修正がない箇所もありますが，それはその都度明示します
1/4, 2/4 の記事は基本的に修正しませんが，それらの記事のサマリーは概要と称して，今回の1,5日目に載せていますので，そちらをご参照ください
また，「プログラマブルブートストラップの原著論文を理解する回」を理解する回 3/4での↓の内容は本記事で扱いません（リメイクすることがないので）
- TFHE方式のアルゴリズム，TFHE方式のアルゴリズムの具体例（前記事参照）
- 無限ノルム
- TFHE方式のアルゴリズムの正当性
- Tensor積
- gadget行列
- gadget decomposition
- TFHE方式の暗号文の足し算
- TFHE方式の暗号文のスカラー倍
- TFHE方式の暗号文とGGSW方式の暗号文の掛け算
- CMuxゲート
つまり本記事では，GGSW方式のリメイクしかしません
＊TFHE方式の暗号文で足し算とスカラー倍ができるのは，Torusで足し算とスカラー倍ができること由来です
GGSW方式
GGSW方式とは，TFHE-TRLWE方式をサブルーチンとした，別の暗号化方式です
Decに関しては今回使わないので省略しています（というか詳細をあまり知らない）
書き忘れましたが，$\tilde{\mu} \in \mathbb{Z}_N[X]$ です
また，$G = I_{k + 1} \otimes g$ なので，$G \in \mathbb{Z}_N[X]^{(k + 1)\ell \times (k + 1)}$ ゆえ，$\tilde{\mu} G \in \mathbb{Z}_N[X]^{(k + 1)\ell \times (k + 1)}$ですし，
$\tilde{X}_w = \mathrm{TFHE-TRLWE}_{\tilde{s}}(0) \in \mathbb{Z}_N[X]^{k + 1}$ なので，$\tilde{X} \in \mathbb{Z}_N[X]^{(k + 1)\ell \times (k + 1)}$ ですから，$\tilde{X}$ と $\tilde{\mu} G$ のサイズが一致していることから足し算ができます
Encの計算量ですが，TFHE-TRLWE方式では，
- $\mathbb{Z} / q \mathbb{Z}$ での足し算 : $(n + 1) N$ 回
- $\mathbb{Z} / q \mathbb{Z}$ での掛け算 : $n N^2$ 回
でした 前回の記事 から，サブルーチン全体（3-6行目）では，
- $\mathbb{Z} / q \mathbb{Z}$ での足し算 : $(k + 1) \ell (n + 1) N$ 回
- $\mathbb{Z} / q \mathbb{Z}$ での掛け算 : $(k + 1) \ell n N^2$ 回
となります．また，２行目は
- $\mathbb{Z} / q \mathbb{Z}$ での掛け算 : $(k + 1)^2 \ell$ 回
ですし，7行目は，$\tilde{\mu} G$ は，$\mathbb{Z}_N[X]$ の掛け算を $(k + 1)^2 \ell$ 回で，$\tilde{X} + \tilde{\mu} G$ は $\mathbb{Z}_N[X]$ の足し算を $(k + 1)^2 \ell$ 回ですので，
- $\mathbb{Z} / q \mathbb{Z}$ での足し算 : $(k + 1)^2 \ell N^2$ 回
- $\mathbb{Z} / q \mathbb{Z}$ での掛け算 : $(k + 1)^2 \ell N^2$ 回
を得ます．以上より，GGSW方式全体では，
- $\mathbb{Z} / q \mathbb{Z}$ での足し算 : $(k + 1) \ell((k + 1)N^2 + (n + 1)N + (k + 1))$ 回
- $\mathbb{Z} / q \mathbb{Z}$ での掛け算 : $(k + 1) \ell (n + k + 1) N^2$ 回
です．
TFHE-TRLWEと比べると，（$(k + 1)\ell$ 回呼ぶ以上に）だいぶ計算回数が増えていることがわかります
まとめ
前回と今回で（ほとんどやっていませんが）「プログラマブルブートストラップの原著論文を理解する回」を理解する回 3/4 のリメイクができたと思います
次回からはbootstrapのリメイクをやっていきます！
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！