この記事はEAGLYS Advent Calendar 2021の22日目の記事です．12/27投稿予定が1/31になってしまいました・・・が，２月には入らなかったのでセーフ（何が？）．
今回の記事は下記の記事からの続きとなります．
原著論文：プログラマブルブートストラップの原著論文
第１回：第１回
第２回：第２回
第３回：第３回
プログラマブルブートストラップの原著論文の第２〜４章を厳密に考察します．
全体を通して使う記号や前提知識などは第１回目の記事にまとめています．
深掘りしたZennの記事
第１回：第１回
第２回：第２回
第2.5回：第2.5回
第３回：第３回
第４回：第４回
突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください
全４回通しでの目次
第１回
- 本論文全体の流れ
- 前提知識
- 今回出てくる予備知識のまとめ
- 2.1 Torus and Torus Polynomials
- Torus
- 加群
- 多項式環
- 既約多項式と円分多項式
- Torus上の多項式
- 2.2 Probability Distributions
- 離散一様分布と正規分布
- 実数から整数への丸め
第２回
- 今回出てくる予備知識のまとめ
- Appendix A : Complexity Assumptions Over the Real Torus
- TLWEとTRLWE
- 3章前説
- 3章の流れ
- ギリシャ文字と花文字
- $\hat{\mathbb{Z}}$ と $\hat{\mathbb{T}}$
- 3章前説の議論
- 3章前説の議論の考察
- 3.1 Encoding/Decoding Messages
- lift
- Upper
- 3.1の議論
- 3.1の議論の考察
第３回
- 今回出てくる予備知識のまとめ
- 3.2 Description
- TFHE方式のアルゴリズム
- TFHE方式のアルゴリズムの具体例
- 無限ノルム
- TFHE方式のアルゴリズムの正当性
- 3.2の議論の考察
- 3.3 Leveled Operation
- Tensor積
- gadget行列
- gadget decompostion
- GGSW方式の概要
- TFHE方式の暗号文の足し算
- TFHE方式の暗号文のスカラー倍
- 結局 Leveled Operaion とは何か
- TFHE方式の暗号文とGGSW方式の暗号文の外積
- Cmuxゲート
- 3.3の議論の考察
第４回（イマココ）
- ４章の流れ
- 4.1 Blind Rotation
- 4.1でやりたいこと
- Rescaling
- bootstrapでやりたいこと
- Blind Rotation
- Sample Extraction
- Key Swicthing
- bootstrapのまとめ
- 4.2 Look-up Table Evaluation
- 4.2の議論
今回は第４回目で，
4 Programmable Bootstrapping
4.1 Blind Rotation
4.2 Look-up Table Evaluation
理論編ラストです．実は第２回・第３回の内容がしっかり理解できていればウイニングランだったりします．
具体的な内容としては，次のようになります:
- ４章の流れ
- 4.1 Blind Rotation
- 4.1でやりたいこと
- Rescaling
- bootstrapでやりたいこと
- Blind Rotation
- Sample Extraction
- Key Swicthing
- bootstrapのまとめ
- 4.2 Look-up Table Evaluation
- 4.2の議論
今回の「４章の流れ」 で詳しいことは触れますが，今回は，暗号文から平文への効率的な復号法（＝bootstrap）を4.1で解説し，前回の Leveled Operations と今回の bootstrap を組合わせて，4.2での本論文メインとなり programmable bootstrap を解説します．
４章の流れ
４章に入ります．
４章では，暗号文からノイズを取り除くことがメインで，これを bootstrap と言います．TLWE/TRLWE方式の暗号文同士の演算ができるかどうかは，ノイズによって定まるのでした．そこで，ノイズを取り除くことで，Leveled Operation を実行できます．
4.1：bootstrap
4.2：programmable bootstrap
4.1のタイトルが「Blind Rotation」になっていますが，これは bootstrap で使うアルゴリズムの1つです．それとは別に Sample Extraction と Key Switching というアルゴリズムも使用します．これら Blind Rotation と Sample Extraction, Key Switching を順に合成したアルゴリズムが bootstrap です．これらのアルゴリズムを定義する際に，3.3 の Leveled Operations が必要になります．
そして，上記の bootstrap を使って暗号文へ任意の演算を作用させることができる手法が，4.2 で解説する programmable bootstrap です．
4.1でやりたいこと
今回は始めに状況設定を共通で行いたいので，議論パートを先に持ってきます．各アルゴリズムの細かい話を各論でやっていきます．
状況設定としては，第３回「TFHE方式のアルゴリズム」 でやったアルゴリズムが必要になります．
始めにKeyGenからです．
始めに，$k$ は1以上の自然数，$\sigma$ は任意の（正の）実数，$\bar{w}, w, \Omega$ は全て正整数で，$\bar{w} + w \leq \Omega$ を満たす，ものとします．
＊論文の $n$ は上記の $k$ に相当しますが，変更する意味がないので $k$ で解説します
次に，$\chi$ を $\mathbb{R} _ N[X]$ 上の正規分布で， $\mathcal{N}(0, \sigma^2)$ として，$p = 2^{\bar{w} + w}, \ q = 2^{\Omega}$ とします．
また，秘密鍵は，$s = (s_0,$ $s_1,$$ \cdots,$$s_{k - 1})$$ \overset{\$}{\leftarrow} \mathbb{B}^k$ です．
最後に，平文空間 $\tilde{P}$ を $\displaystyle \tilde{P} = (\frac{q}{p} \mathbb{Z} / q \mathbb{Z}) \subset \hat{\mathbb{Z}} = (\mathbb{Z} / q \mathbb{Z})$ と定めます．
＊$\tilde{\cdot}$ 記号は多項式を表すことに注意してください，今は多項式ではないので，外しています
このとき，公開鍵 $pk$ を $pk = (k, \sigma, p, q)$ で秘密鍵 $sk$ を $sk = s$ とします．
続いてEncryptです．
$(a_1,$$ a_2,$$ \cdots,$$ a_k) \overset{\$}{\leftarrow} \hat{\mathbb{Z}}^k$ と各係数が $\chi$ に従うノイズ $\tilde{e} \overset{\$}{\leftarrow} \mathbb{R}$ を取る．ノイズ $e$ を $\lfloor e q \rceil$ で離散化した $e^{\prime}$ を取る．
$\hat{\mathbb{Z}} = \mathbb{Z} / q \mathbb{Z}$ 内での計算で $\displaystyle c = \sum_{j = 1}^k s_j a_j + \mu + e^{\prime} \in \hat{\mathbb{Z}}$ を求める．
$C = (a_1, a_2, \cdots, a_k, c) \in \hat{\mathbb{Z}}^{k + 1}$ とする．$C$ を $\overline{\textrm{TFHE-TLWE}}_{s}(\mu)$ と書くことにする．
そして，$C$ から $\mu$ への Decrypt は次のようになるのでした．今回考えるべきところはここです．
$\hat{\mathbb{Z}} = \mathbb{Z} / q \mathbb{Z}$ 内での計算で $\mu + e^{\prime} = c - \sum_{j = 1}^k s_j a_j$ を求める．
$\mathrm{Upper}_{q, p}(\mu + e^{\prime})$ が $\mu$ と一致する．
さて，ここまでが状況設定です．
簡単のため，$\mu^{\ast} = \mu + e^{\prime}$ と置きます．つまり，$\displaystyle - \mu^{\ast} = - (c - \sum_{j = 1}^k s_j a_j) = -c + \sum_{j = 1}^k s_j a_j$ $\in \mathbb{Z} / q \mathbb{Z}$ です．今，$- \mu \in \mathbb{Z} / q \mathbb{Z}$ とさらっと書きましたが，値は $[0, q - 1]$ に制限していることに注意してください．
$\mathrm{Upper}_{q, p}(\mu + e^{\prime})$ が $\mu$ と一致する．
から，$\mathrm{Upper}_{q, p}(\mu^{\ast}) = \mu$ になっています．
ここで，test polynomial というものを考えます．
$\underline{\mathrm{Def(test \ polynomial)}}$
任意の $i \in [0, q - 1]$ に対して，$v_i = \mathrm{Upper}_{q, p}(i) \in \mathbb{Z} / q \mathbb{Z}$ として，
$$\begin{align*}
\tilde{v} = v_0 + v_1 X + \cdots + v_{q - 1} X^{q - 1}
\end{align*}$$
なる $\tilde{v}$ を test polynomial という．
やりたいこととしては，$- \mu^{\ast} \in \mathbb{Z} / q \mathbb{Z}$ ですから，
\displaystyle
\begin{align*}
&X^{- \mu^{\ast}} \cdot \tilde{v} \\
&= X^{- \mu^{\ast}} \cdot (v_0 + v_1 X + \cdots + v_{\mu^{\ast} - 1} X^{\mu^{\ast} - 1} + v_{\mu^{\ast}} X^{\mu^{\ast}} + v_{\mu^{\ast} + 1} X^{\mu^{\ast} + 1} + \cdots + v_{q - 1} X^{q - 1}) \\
&= v_{\mu^{\ast}} + v_{\mu^{\ast} + 1} X + \cdots v_{q - 1} X^{q - 1 - \mu^{\ast}} + v_0 X^{q - \mu^{\ast}} + v_1 X^{q + 1 - \mu^{\ast}} + \cdots + v_{\mu^{\ast} - 1} X^{q - 1}
\end{align*}
となります．何をやっているのかというと，元々 $\tilde{v}$ の中に，先頭から $\mu^{\ast} + 1$ 番目に求めたい $\tilde{v}_{\mu^{\ast}} =$$ \mathrm{Upper}_{q, p}(\mu^{\ast})$ が格納されているのが，$X^{- \mu^{\ast}} \cdot v$ だと，先頭に $\tilde{v}_{\mu^{\ast}}$ が格納されているので，求めやすい（定数項を見るだけでいい），ということです．
そして，$X^{- \mu^{\ast}} \cdot \tilde{v}$ さえ求められれば，その先頭に求めたいものが出てくる，というのは，Decrypt での
$\hat{\mathbb{Z}} = \mathbb{Z} / q \mathbb{Z}$ 内での計算で $\mu + e^{\prime} = c - \sum_{j = 1}^k s_j a_j$ を求める．
$\mathrm{Upper}_{q, p}(\mu + e^{\prime})$ が $\mu$ と一致する．
を達成したことになります．
上手くいきましたね，めでたしめでたし．
と言うとでも思ったか・・・？
実は先ほどの議論には問題点があります．大雑把には合ってるんですけどね．
そして，$X^{- \mu^{\ast}} \cdot \tilde{v}$ さえ求められれば，その先頭に求めたいものが出てくる
の部分の $X^{- \mu^{\ast}} \cdot \tilde{v}$ を求める箇所に３つ問題があります．この３つをこれから詰めます．
- test polynomial $\tilde{v}$ の定義域は？
- $X^{- \mu^{\ast}}$ の定義域は？
- 秘密鍵はそのままでいいのか？
以降ではこれらの問題を考えます．
Rescaling
ここでは，
- test polynomial $\tilde{v}$ の定義域は？
- $X^{- \mu^{\ast}}$ の定義域は？
の2つについて考えます．まず，１つ目ですが，順当に考えたら，$\tilde{v} = v_0 + v_1 X + \cdots + v_{q - 1} X^{q - 1}$ でありますから，$\tilde{v} \in \hat{\mathbb{Z}}[X] / (X^q + 1)$ であってほしいわけです．
しかし，TFHE方式の暗号化アルゴリズムやGGSW方式の暗号化アルゴリズムであったように，暗号文空間の定義域は $\hat{\mathbb{Z}}_N[X] = \hat{\mathbb{Z}}[X] / (X^N + 1)$ でした．
つまり，$\tilde{v}$ を何かしらで変換して $\tilde{v}^{\prime}$ のような多項式にして，$\tilde{v}^{\prime} \in \hat{\mathbb{Z}}_N[X]$ であることを考えます．
実際にどのようにして変換するかは，後に解説します．
次に，２つ目ですが，$X^{- \mu^{\ast}}$ は修正した test polynomial $\tilde{v}^{\prime}$ に作用させたいので，こちらも $X^{- \mu^{\ast}} \in \hat{\mathbb{Z}}_N[X]$ と考えるのが自然でしょう．
そこで，よくよく考えたいこととして $X^{- \mu^{\ast}}$ は $X^{\mu^{\ast}}$ の逆元でした．つまり，$X^{\mu^{\ast}}$ の逆元をどのように表すかを考えていきます．
$X^{- \mu^{\ast}} \in \hat{\mathbb{Z}}_N[X]$ ですから $X^{\mu^{\ast}} \in \hat{\mathbb{Z}}_N[X]$ なので，ここで，$\hat{\mathbb{Z}}_N[X]$ を深く考えていきます．つまり，$\hat{\mathbb{Z}}_N[X]$ での $X$ の指数の周期を考えます．
これは，$2 N$ 次の円分多項式が $X^N + 1$ であることから，$X^N = -1$ であり，また，$\hat{\mathbb{Z}}_N[X] = \hat{\mathbb{Z}}[X] / (X^N + 1)$ の $X$ の指数の周期は $2 N$ です．
つまり，$X^{2 N - \mu^{\ast}} = X^{- \mu^{\ast}} \in \hat{\mathbb{Z}}_N[X]$ が成り立ちます．$X$ の指数部分は $\mathrm{mod} \ 2 N$ で考えればよいわけです．
しかし，肝心の $\mu^{\ast}$ は $\mu^{\ast} \in \mathbb{Z} / q \mathbb{Z}$ ですので，$\mathrm{mod} \ 2 N$ に収まっていませんから，ここも調整する必要があります．これは，$\displaystyle - \mu^{\ast} = - b + \sum_{j = 1}^n s_j a_j$ で $a_j, \ b \in \mathbb{Z} / q \mathbb{Z}$ であることから，$\mu^{\ast}$ を変えるには $a_j, \ b$ を変更する必要があります．
$a_j, \ b \in \mathbb{Z} / q \mathbb{Z}$ を $a_j^{\prime}, \ b^{\prime} \in \mathbb{Z} / 2 N \mathbb{Z}$ に変換するには，単純に $\cfrac{2 N}{q}$ 倍すればいい訳です．つまり，$\displaystyle a_{j, \textrm{res}} = \left \lfloor \frac{2 N a_j}{q} \right \rceil, \ b_{\textrm{res}} = \left \lfloor \frac{2 N b}{q} \right \rceil$ で実現できます．
＊res は restrict の略称で使っています，留数定理とかでは residue の略称で使う（residue の和訳に 留数 も含まれる）こともあるのですが，今は restrict の意味合いで使います
よって，$\displaystyle - \mu^{\ast} = - b + \sum_{j = 1}^n s_j a_j \in \mathbb{Z} / q \mathbb{Z}$ から $- \mu^{\ast \prime} \in \mathbb{Z} / 2 N \mathbb{Z}$ に変換するには，$a_{j, \textrm{res}}, \ b_{\textrm{res}}$ を使って，$\displaystyle - \mu^{\ast}_{\textrm{res}} =$$ - b_{\textrm{res}} +$$ \sum_{j = 1}^n s_j$$ a_{j, \textrm{res}} \in \mathbb{Z} / 2 N \mathbb{Z}$ で実現できます．
よって，$- \mu^{\ast}_{\textrm{res}} \in \mathbb{Z} / 2 N \mathbb{Z}$ ゆえ，test polynomial $\tilde{v}_{\textrm{res}} =$$ v_{0, \textrm{res}} +$$ v_{1, \textrm{res}} X +$$ \cdots + v_{N - 1, \textrm{res}} X^{N - 1} \in$$ \hat{\mathbb{Z}}_N[X]$ は $v_i =$$ \mathrm{Upper}_{q, p}(i)$ に対して， $v_{i, \textrm{res}} =$$\displaystyle \mathrm{Upper}_{q, p}(\frac{q}{2 N} i)$ とすればOKです．
まとめると，$- \mu^{\ast}$ の定義域は， $\displaystyle - \mu^{\ast} = - b + \sum_{j = 1}^n s_j$$ a_j$ において，$\displaystyle a_{j, \textrm{res}} =$$ \left \lfloor \frac{2 N a_j}{q} \right \rceil,$$ \ b_{\textrm{res}} = \left \lfloor \frac{2 N b}{q} \right \rceil$ として，$\displaystyle - \mu^{\ast}_{\textrm{res}} =$$ - b_{\textrm{res}} +$$ \sum_{j = 1}^n s_j$$ a_{j, \textrm{res}} \in \mathbb{Z} / 2 N \mathbb{Z}$ と修正し，test polynomial $v$ を $\tilde{v}_{\textrm{res}} =$$ v_{0, \textrm{res}} +$$ v_{1, \textrm{res}} X + \cdots +$$ v_{N - 1, \textrm{res}} X^{N - 1} \in$$ \hat{\mathbb{Z}}_N[X],$$ \ v_{i, \textrm{res}} =$$ \mathrm{Upper}_{q, p}(\frac{2 N}{q} i)$ と修正することで，$X^{- \mu^{\ast}_{\textrm{res}}} \cdot$$ \tilde{v}_{\textrm{res}}$ を求めることが目標，とできます．
最後にRescalingのアルゴリズムをまとめておきます．
bootstrapでやりたいこと
上記でやりたかったことは，「暗号文のノイズを取り除く」ことです．ノイズは，下位 $\Omega - (\bar{w} + w) - 1$ bit に格納されているのですから，そこをなるべく0にすればOKです．
そのためには，
$X^{- \mu^{\ast}_{\textrm{res}}} \cdot$$ \tilde{v}_{\textrm{res}}$ を求めることが目標
でした．
では，このことをどのようにして実現すればいいでしょうか．そして，今回の 「Rescaling」 の3つ目の問題点である「秘密鍵はそのままでいいのか？」についても考察します．
以下では，Blind Rotation, Sample Extraction, Key Switching と3つのアルゴリズムが出てくるのですが，（前の Rescaling もまとめて）それぞれの処理を図示しました．
Blind Rotation $\circ$ Rescaling は下記の図で，左上の $(\mathbb{Z} / q \mathbb{Z})^{n + 1}$ から右下の $(\mathbb{Z} / q \mathbb{Z})_N[X]^{k + 1}$ に向かう射のことです．
＊五角形の図式にしようかとも思ったのですが，少し見栄えが悪いので，上記のような形にしました
上記の可換図式を射ごとにざっくり説明します．Rescaling 以外のそれぞれの要素については次章以降で説明します．
Blind Rotation
$\hat{\mathbb{Z}} = \mathbb{Z} / q \mathbb{Z}$ 内での計算で秘密鍵 $\tilde{s}^{\prime}$ のもとで $c = \overline{\textrm{TFHE-TLWE}}_{s}(\mu) \in \hat{\mathbb{Z}}^{n + 1}$ から $c^{\prime} = \overline{\textrm{TFHE-TRLWE}}_{\tilde{s}^{\prime}}$$(X^{- \tilde{\mu}^{\ast}_{\textrm{res}}} \cdot \tilde{v}^{\prime}) \in$$ \hat{\mathbb{Z}}_N[X]^{k + 1}$ を求める
Sample Extraction
$c^{\prime} = \overline{\textrm{TFHE-TRLWE}}_{\tilde{s}^{\prime}}$$(X^{- \tilde{\mu}^{\ast}_{\textrm{res}}} \cdot \tilde{v}^{\prime}) \in$$ \hat{\mathbb{Z}}_N[X]^{k + 1}$ から $c^{\prime \prime} = (a^{\prime}_{1, 0},$$ - a^{\prime}_{1, N - 1},$$ \cdots, - a^{\prime}_{1, 1},$$ \cdots, a^{\prime}_{k, 0},$$ - a^{\prime}_{k, N - 1}, \cdots,$$ - a^{\prime}_{k, 1},$$ b^{\prime}_0) \in (\mathbb{Z} / q \mathbb{Z})^{kN + 1}$ を求める．
Key Switching
$c^{\prime \prime} = (a^{\prime}_{1, 0},$$ - a^{\prime}_{1, N - 1},$$ \cdots, - a^{\prime}_{1, 1}, \cdots,$$ a^{\prime}_{k, 0},$$ - a^{\prime}_{k, N - 1}, \cdots,$$ - a^{\prime}_{k, 1},$$ b^{\prime}_0) \in (\mathbb{Z} / q \mathbb{Z})^{kN + 1}$ から秘密鍵 $s$ による $c^{\prime \prime \prime} = (0, \cdots, 0, b^{\prime \prime \prime}) - \sum_{u = 1}^{kN}$$ \sum_{v = 1}^{\ell}$$ a^{\prime \prime \prime}_{u, v} \mathrm{ksk}[u][v] =$$ \overline{\textrm{TFHE-TLWE}}_{s}(\mu) \in \hat{\mathbb{Z}}^{n + 1}$ を求める．
となります．厳密には，Blind Rotation には，Rescaling の操作も含まれています．
つまり，$c = \overline{\textrm{TFHE-TLWE}}_{s}(\mu) \in \hat{\mathbb{Z}}^{n + 1}$ に対して，
Blind Rotation → Sample Extraction → Key Swithing
と処理を施すと，$c^{\prime \prime \prime} = \overline{\textrm{TFHE-TLWE}}_{s}(\mu) \in \hat{\mathbb{Z}}^{n + 1}$ が得られて，これがほしいものでした．
上記の３つのアルゴリズムの input と output が明らかになりました．
では，その過程でやることを軽く解説しようと思います．詳細については，各項目で解説します．
Blind Rotation
秘密鍵云々はここで考えます．具体的には，CMux gate を使う際に，元の秘密鍵を別に秘密鍵 $s^{\prime}$ での $\textrm{GGSW-TRLWE}$ 方式の暗号化でマスキングをします．
更に，External product も考えるため，$\textrm{TFHE-TRLWE}$ 方式の暗号化も登場します．
Sample Extraction
実は，Blind Rotation でやりたいことはほぼできているのですが，問題が２つあります．
- Blind Rotation の出力は多項式だが，実際は整数
- 秘密鍵が変更されたまま
Sample Extraction では前者を考えます．ここで，多項式の係数だけを取り出すことを考えます．
そこで，最終的に定数項のみに関わる部分のみを抜き出すことで，多項式の話から整数に戻します．
Key Switching
Blind Rotation で鍵を変更してから，元の秘密鍵に戻すことを考えます．そのために導出する式はいかついですが，きちんと全て修正されながら戻っていて，その結果初め（全体のinput）にあったノイズも取り除けています．
Blind Rotation
目的はこのようなものでした．
$\hat{\mathbb{Z}} = \mathbb{Z} / q \mathbb{Z}$ 内での計算で秘密鍵 $\tilde{s}^{\prime}$ のもとで $c = \overline{\textrm{TFHE-TLWE}}_{s}(\mu) \in \hat{\mathbb{Z}}^{n + 1}$ から $c^{\prime} = \overline{\textrm{TFHE-TRLWE}}_{\tilde{s}^{\prime}}$$(X^{- \tilde{\mu}^{\ast}_{\textrm{res}}} \cdot \tilde{v}^{\prime}) \in$$ \hat{\mathbb{Z}}_N[X]^{k + 1}$ を求める
Rescaling は行なったものとします．やりたいことから順に手順を遡ってみます．実装ということで，少し効率性も考えます．
$X^{- \mu^{\ast}_{\textrm{res}}} \cdot \tilde{v}_{\textrm{res}}$ を求めたい
$\rightarrow$ そのためには，$X^{- \mu^{\ast}_{\textrm{res}}} =$$ X^{- b_{\textrm{res}} + \sum_{i = 1}^n s_i a_{i, \textrm{res}}}$ を求める必要がある
$\rightarrow$ $i - 1$ 番目の $X^{- b_{\textrm{res}} + \sum_{h = 1}^{i - 1} s_h a_{h, \textrm{res}}}$ まで求まっているなら，それに $X^{s_i a_{i, \textrm{res}}}$ を掛ければいいので，$X^{s_i a_{i, \textrm{res}}}$ を求める必要がある（０番目の初期値は $X^{- b_{\textrm{res}}}$ としている）
$\rightarrow$ $X^{s_i \cdot a_{i, \textrm{res}}}$ の部分は，$s_i \in$ {$0, 1$} であり，CMux gate を使える（$s_i$ の値で場合分けをしなくていい）
$\rightarrow$ 考える必要がある部分は，実質，$X^{- b_{\textrm{res}} + \sum_{h = 1}^{i - 1} s_h a_{h, \textrm{res}}}$$ \cdot X^{a_{i, \textrm{res}}}$ のみ
ここで，$\textrm{CMux}$ の部分を整理してみましょう．
参照：第３回「CMuxゲート」
$\textrm{CMux}$ は，引数を3つ取り，1つめは0か1を $\textrm{GGSW-TRLWE}$ で暗号化したもので，2つめと3つめは $\textrm{TFHE-TRLWE}$ 方式の暗号文でした．
$s_i \in {0, 1}$ ですので，$s_i$ を $\textrm{GGSW-TRLWE}$ で暗号化したものを１つ目の引数にすればOKです．そして，そこの暗号化では別の秘密鍵が必要になります．
と同時に，今回の「4.1でやりたいこと」 での「秘密鍵はそのままでいいのか？」も $s_i$ を適当な暗号化でマスクしたことになるので，これで解決したことになります．
次に $\textrm{TFHE-TRLWE}$ 方式の暗号文を用意する必要がありますが，これは，$X^{- b_{\textrm{res}} + \sum_{h = 1}^{i - 1} s_h a_{h, \textrm{res}}}$ と $X^{- b_{\textrm{res}} + \sum_{h = 1}^{i - 1} s_h a_{h, \textrm{res}}} \cdot X^{a_{i, \textrm{res}}}$ をそれぞれ $\textrm{TFHE-TRLWE}$ 方式で暗号化したものを用意すればOKです．
これは，$\textrm{CMux}$ の演算で External product が出てくるためです．
参照：第３回「TFHE方式の暗号文とGGSW方式の暗号文の外積」
以上の議論をまとめると，
\displaystyle
\begin{align*}
\textrm{CMux}(\overline{\textrm{GGSW-TRLWE}}_{\tilde{s}^{\prime}}(s_i), \overline{\textrm{TFHE-TRLWE}}_{\tilde{s}^{\prime}}(X^{- b_{\textrm{res}} + \sum_{h = 1}^{i - 1} s_h a_{h, \textrm{res}}} \cdot \tilde{v}_{\textrm{res}}), \overline{\textrm{TFHE-TRLWE}}_{\tilde{s}^{\prime}}(X^{- b_{\textrm{res}} + \sum_{h = 1}^{i - 1} s_h a_{h, \textrm{res}}} \cdot X^{a_{i, \textrm{res}}} \cdot \tilde{v}_{\textrm{res}}))
\end{align*}
このようになります．ここで，新しく出てきた秘密鍵 $\tilde{s}^{\prime}$ は，このときのためだけに使用する鍵で，$\tilde{s}^{\prime} \in \mathbb{B}_N[X]^k$ です．
また，External product では，互いの秘密鍵を合わせる必要があるため，$\textrm{TFHE-TRLWE}$ 方式でも $\tilde{s}^{\prime}$ を使う必要があります．
とすると，最終的にでてくるアウトプットは，
\displaystyle
\begin{align*}
\overline{\textrm{TFHE-TRLWE}}_{\tilde{s}^{\prime}}(X^{- b_{\textrm{res}} + \sum_{i = 1}^{n} s_i a_{i, \textrm{res}}} \cdot \tilde{v}_{\textrm{res}})
\end{align*}
となり，$- \mu^{\ast}_{\textrm{res}} =$$ - b_{\textrm{res}} +$$ \sum_{i = 1}^n$$ s_i$$ a_{i, \textrm{res}}$ でしたから，上記のアウトプットは
\displaystyle
\begin{align*}
\overline{\textrm{TFHE-TRLWE}}_{\tilde{s}^{\prime}}(X^{- \mu^{\ast}_{\textrm{res}}} \cdot \tilde{v}_{\textrm{res}})
\end{align*}
このようにまとめられます．
最後に Blind Rotation のアルゴリズムをまとめておきます．
以下では，$\textrm{ACC}$ というのを使って（accumulatorの略），途中の
\displaystyle
\begin{align*}
\overline{\textrm{TFHE-TRLWE}}_{\tilde{s}^{\prime}}(X^{- b_{\textrm{res}} + \sum_{h = 1}^{i - 1} s_h a_{h, \textrm{res}}} \cdot \tilde{v}_{\textrm{res}})
\end{align*}
を表現していますが，$\textrm{ACC}$ だと何に依存するか分かりづらいなって思っています．
Sample Extraction
目的はこのようなものでした．
$\hat{\mathbb{Z}} = \mathbb{Z} / q \mathbb{Z}$ 内での計算で秘密鍵 $\tilde{s}^{\prime}$ のもとで $c = \overline{\textrm{TFHE-TLWE}}_{s}(\mu) \in \hat{\mathbb{Z}}^{n + 1}$ から $c^{\prime} = \overline{\textrm{TFHE-TRLWE}}_{\tilde{s}^{\prime}}$$(X^{- \tilde{\mu}^{\ast}_{\textrm{res}}} \cdot \tilde{v}^{\prime}) \in$$ \hat{\mathbb{Z}}_N[X]^{k + 1}$ を求める
大雑把には，「TRLWEに出てくる多項式をベクトルと見て，それらを連結させて，$\mathbb{Z} / q \mathbb{Z}$ の１つのベクトルと考えることで，TLWEの暗号文とみなす」というものです．
↓を見れば難しいことはやっていないと分かると思います．
Blind Rotation で出てきた秘密鍵 $\tilde{s}^{\prime} = (\tilde{s}^{\prime}_1,$$ \cdots, \tilde{s}^{\prime}_{N - 1}) \in $$\mathbb{B}_N[X]^k$ と $1 \leq j \leq k$ に対して，$\tilde{s}^{\prime}_j =$$ s^{\prime}_{j, 0} +$$ s^{\prime}_{j, 1} X +$$ \cdots + s^{\prime}_{j, N - 1} X^{N - 1}$ とします．
また，input である $c^{\prime} = (\tilde{a}^{\prime}_1, \cdots,$$ \tilde{a}^{\prime}_k, \tilde{b}^{\prime})$ と $1 \leq j \leq k$ に対して，$\tilde{a}^{\prime}_j =$$ a^{\prime}_{j, 0} +$$ a^{\prime}_{j, 1} X + \cdots +$$ a^{\prime}_{j, N - 1} X^{N - 1}$ と $\tilde{b}^{\prime} = b^{\prime}_{0} +$$ b^{\prime}_{1} X + \cdots +$$ b^{\prime}_{N - 1} X^{N - 1}$ とします．
このとき，
\displaystyle
\begin{align*}
c^{\prime \prime} &= (a^{\prime}_{1, 0}, - a^{\prime}_{1, N - 1}, \cdots, - a^{\prime}_{1, 1}, a^{\prime}_{2, 0}, - a^{\prime}_{2, N - 1}, \cdots, - a^{\prime}_{2, 1}, \cdots, a^{\prime}_{k, 0}, - a^{\prime}_{k, N - 1}, \cdots, - a^{\prime}_{k, 1}, b^{\prime}_0) \\ &\in (\mathbb{Z} / q \mathbb{Z})^{k N + 1}
\end{align*}
と秘密鍵
\displaystyle
\begin{align*}
s^{\prime \prime} &= (s^{\prime}_{1, 0}, s^{\prime}_{1, 1}, \cdots, s^{\prime}_{1, N - 1}, s^{\prime}_{2, 0}, s^{\prime}_{2, 1}, \cdots, s^{\prime}_{2, N - 1}, \cdots, s^{\prime}_{k, 0}, s^{\prime}_{k, 1}, \cdots, s^{\prime}_{k, N - 1}) \\ &= (s^{\prime \prime}_1, s^{\prime \prime}_2, \cdots, s^{\prime \prime}_{k N}) \\ &\in \mathbb{B}^{kN}
\end{align*}
について
\displaystyle
\begin{align*}
c^{\prime \prime} = \overline{\textrm{TFHE-TLWE}}_{s^{\prime \prime}}(\mu)
\end{align*}
が成り立っています．
最後に Sample Extraction のアルゴリズムをまとめておきます．
Key Switching
目的はこのようなものでした．
$c^{\prime \prime} = (a^{\prime}_{1, 0},$$ - a^{\prime}_{1, N - 1},$$ \cdots, - a^{\prime}_{1, 1}, \cdots,$$ a^{\prime}_{k, 0},$$ - a^{\prime}_{k, N - 1}, \cdots,$$ - a^{\prime}_{k, 1},$$ b^{\prime}_0) \in (\mathbb{Z} / q \mathbb{Z})^{kN + 1}$ から秘密鍵 $s$ による $c^{\prime \prime \prime} = (0, \cdots, 0, b^{\prime \prime \prime}) - \sum_{u = 1}^{kN}$$ \sum_{v = 1}^{\ell}$$ a^{\prime \prime \prime}_{u, v} \mathrm{ksk}[u][v] =$$ \overline{\textrm{TFHE-TLWE}}_{s}(\mu) \in \hat{\mathbb{Z}}^{n + 1}$ を求める．
Key Switching とは，平文をそのままだけど秘密鍵を変更することで，暗号文を変更する手法のことです．
やりたいこととしては，Blind Rotation で変わってしまった秘密鍵を元に戻します．
以下では，gadget decomposition を使用するため，$\ell$ 桁の $B$ 進展開を行うようにパラメタを予め設定しておきます．
ここで，$\textrm{ksk}[u ] [v ] (1 \leq u \leq kN, \ 1 \leq v \leq \ell)$ という二重配列(key switching key の略)を用意し，$u, v$ を固定したとき，$\mathrm{ksk}[u][v] = \overline{\textrm{TFHE-TLWE}}_{s}$$(s_u^{\prime \prime} \cdot \frac{q}{B^v})$ という値を格納するものとします．
また，input である $c^{\prime \prime} = (a^{\prime}_{1, 0},$$ - a^{\prime}_{1, N - 1}, \cdots,$$ - a^{\prime}_{1, 1},$$ a^{\prime}_{2, 0},$$ - a^{\prime}_{2, N - 1}, \cdots,$$ - a^{\prime}_{2, 1}, \cdots,$$ a^{\prime}_{k, 0},$$ - a^{\prime}_{k, N - 1}, \cdots,$$ - a^{\prime}_{k, 1},$$ b^{\prime}_0)$ について，
\displaystyle
\begin{align*}
& (a^{\prime}_{1, 0}, - a^{\prime}_{1, N - 1}, \cdots, - a^{\prime}_{1, 1}, a^{\prime}_{2, 0}, - a^{\prime}_{2, N - 1}, \cdots, - a^{\prime}_{2, 1}, \cdots, a^{\prime}_{k, 0}, - a^{\prime}_{k, N - 1}, \cdots, - a^{\prime}_{k, 1}) \\
& = (a^{\prime \prime}_1, \cdots, a^{\prime \prime}_{kN})
\end{align*}
とインデックスを変更して，$b^{\prime}_0$ も $b^{\prime \prime \prime}$ に変更しておきます（３つ $\prime$ 付けたのは誤植ではありません）．
さらに，$1 \leq u \leq kN$ に対して，$a^{\prime \prime}_{u}$ の gadget decomposition を考えて，$g^{-1}(a^{\prime \prime}_{u}) =$$ (a^{\prime \prime \prime}_{u, 1},$$ a^{\prime \prime \prime}_{u, 2}, \cdots, $$a^{\prime \prime \prime}_{u, \ell})$ とします．つまり，$\varepsilon < B^{- \ell}$ なる $\varepsilon$ を使って，
\displaystyle
\begin{align*}
a^{\prime \prime}_{u} = q \sum_{v = 1}^{\ell} a^{\prime \prime \prime}_{u, v} B^{- v} + \varepsilon
\end{align*}
が成り立っています．
更に，$c^{\prime \prime \prime} \in (\mathbb{Z} / q \mathbb{Z})^{n + 1}$ を
\displaystyle
\begin{align*}
c^{\prime \prime \prime} = (0, \cdots, 0, b^{\prime \prime \prime}) - \sum_{u = 1}^{kN} \sum_{v = 1}^{\ell} a^{\prime \prime \prime}_{u, v} \mathrm{ksk}[u][v]
\end{align*}
と置くと，$c^{\prime \prime \prime}$ は秘密鍵 $s$ のもとで，$\mu$ を暗号化したものになっています．
最後に Key Switching のアルゴリズムをまとめておきます．
bootstrapのまとめ
この項目を持って，4.1を振り返りします．まず，bootstrap では，いくつかのアルゴリズムを組合せて，暗号文のノイズを取り除くことが目的でした．
先に図式とアルゴリズムを全て再掲します．
１つずつの細かい説明は，各章を確認してください．
主な流れとしては，Blind Rotation でノイズを取り除く作業を行なったものの，出力結果が多項式になっていることと秘密鍵が変更されていることを解消するために，それぞれ更に，Sample Extraction と Key Switching という関数が必要なのでした．
4.2の議論
4.2では Look-up Table というものが新しく出てくるのですが，大したことはやっていないので，いきなり議論に入ろうと思います．
定義域が $\tilde{D}$ で値域が $\tilde{I}$ なる任意の関数 $f$ を取ります．これは任意の演算を表すものとイメージしてください．
$f$ という任意の演算が暗号文の状態でも実現できるようにするには，次のように考えます．
$\mathrm{Encode} : \tilde{D} \rightarrow \mathbb{Z} / q \mathbb{Z}$ と $\mathrm{Encode}^{\prime} : \tilde{I} \rightarrow \mathbb{Z} / q \mathbb{Z}$ なる関数を取ります．これは cleartext から plaintext への encode を表しています．
そして，それらの逆操作として，$\mathrm{Decode} : \mathbb{Z} / q \mathbb{Z} \rightarrow \tilde{D}$ と $\mathrm{Decode}^{\prime} : \mathbb{Z} / q \mathbb{Z} \rightarrow \tilde{I}$ なる関数が取れます．これは plaintext から cleartext への decode を表しています．
ここで，修正版の test polynomial $\tilde{v} = v_0 +$$ v_1 X + \cdots +$$ v_{N - 1} X^{N - 1}$ で $v_i = \mathrm{Upper}_{q, p}(\frac{q}{2N}i)$ を取ります．
$v_i$ に対して，下記の可換図式を作用させて，$\textrm{Encode}^{\prime} \circ f \circ \textrm{Decode}(v_i) = T[i]$ とします．
＊上では look up という関数を考えていますが，特に深い意味はなく，筆者が適当に名前をつけただけなので気にしないでください
つまり，今まで，test polynomial の $\mu^{\ast}_{\textrm{res}}$ 番目は $v_i =$$ \mathrm{Upper}_{q, p}(\frac{q}{2N}i)$ で値が固定だったのが，$f$ は任意だったので，$T[i]$ は $\mathbb{Z} / q \mathbb{Z}$ の任意の値をとることができるようになります．
後は，任意の関数 $f$ を作用させた上記の test polynomial と 4.1 での bootstrap を組合せることで，暗号文に任意の関数を作用させた状態で bootstrap つまり暗号文のノイズを取り除けることができるようになりました．
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！
次回にこれまでのまとめ記事を出します．