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

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

# はじめに

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の暗号化方式の詳細（後半））：
18日目（プログラマブルブートストラップの詳細（前半））：
19日目（プログラマブルブートストラップの詳細（後半））：

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

#### TFHEの最新動向
20日目（TFHEの最新動向（理論編））：
25日目（TFHEの最新動向（実装編））：

前回の続きです．

前回は，TFHE方式のリメイクを行ないました．今回はGGSW方式のリメイクをします．

# はじめに
この記事は，昨年のアドカレの記事

[「プログラマブルブートストラップの原著論文を理解する回」を理解する回　3/4](https://qiita.com/0917laplace/items/cd5b06067f2315944fb1)

のリメイク版となります．

分かりづらかった箇所の修正を行なったり，構成を入れ替えたり，そのとき書けなかった話を加えています
＊具体例とか修正がない箇所もありますが，それはその都度明示します

1/4, 2/4 の記事は基本的に修正しませんが，それらの記事のサマリーは概要と称して，今回の1,5日目に載せていますので，そちらをご参照ください

また，[「プログラマブルブートストラップの原著論文を理解する回」を理解する回　3/4](https://qiita.com/0917laplace/items/cd5b06067f2315944fb1)での↓の内容は本記事で扱いません（リメイクすることがないので）
- TFHE方式のアルゴリズム，TFHE方式のアルゴリズムの具体例（前記事参照）
- 無限ノルム
- TFHE方式のアルゴリズムの正当性
- Tensor積
- gadget行列
- gadget decomposition
- TFHE方式の暗号文の足し算
- TFHE方式の暗号文のスカラー倍
- TFHE方式の暗号文とGGSW方式の暗号文の掛け算
- CMuxゲート

つまり本記事では，GGSW方式のリメイクしかしません

＊TFHE方式の暗号文で足し算とスカラー倍ができるのは，Torusで足し算とスカラー倍ができること由来です

# GGSW方式

GGSW方式とは，TFHE-TRLWE方式をサブルーチンとした，別の暗号化方式です

![GGSW.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1298501/438d5613-1305-f2fb-fb69-07696a49fa64.png)

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$ のサイズが一致していることから足し算ができます

![GGSW_Enc.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1298501/418817df-6c5b-e57b-77bc-5d57d906fc42.png)

Encの計算量ですが，TFHE-TRLWE方式では，

- $\mathbb{Z} / q \mathbb{Z}$ での足し算 : $(n + 1) N$ 回
- $\mathbb{Z} / q \mathbb{Z}$ での掛け算 : $n N^2$ 回

でした [前回の記事](https://qiita.com/0917laplace/items/0635aa2598a9528e3a7f#tfhe-trlwe) から，サブルーチン全体（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](https://qiita.com/0917laplace/items/cd5b06067f2315944fb1) のリメイクができたと思います

次回からはbootstrapのリメイクをやっていきます！

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