この記事はEAGLYS Advent Calendar 2021の17日目の記事です。
今回の記事は下記の記事からの続きとなります．
原著論文：プログラマブルブートストラップの原著論文
第１回：第１回
第２回：第２回
プログラマブルブートストラップの原著論文の第２〜４章を厳密に考察します．
全体を通して使う記号や前提知識などは第１回目の記事にまとめています．
深掘りしたZennの記事
第１回：第１回
第２回：第２回
第2.5回：第2.5回
第３回：第３回
突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください
本記事にはリメイク記事がありますので，そちらもあわせてご確認ください
（リメイク）「プログラマブルブートストラップの原著論文を理解する回」を理解する回 3/4（前半）
全４回通しでの目次
第１回
- 本論文全体の流れ
- 前提知識
- 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.1 Encoding/Decoding Messages
- lift
- Upper
- 3.1の議論
第３回（イマココ）
- 3.2 Description
- TFHE方式のアルゴリズム
- TFHE方式のアルゴリズムの具体例
- 無限ノルム
- TFHE方式のアルゴリズムの正当性
- 3.3 Leveled Operation
- Tensor積
- gadget行列
- gadget decompostion
- GGSW方式の概要
- TFHE方式の暗号文の足し算
- TFHE方式の暗号文のスカラー倍
- 結局 Leveled Operaion とは何か
- TFHE方式の暗号文とGGSW方式の暗号文の外積
- Cmuxゲート
今回は第３回目で，
3 Discretized TFHE
3.2 Description
3.3 Leveled Operation
正直なところここからが本番って感じです．
具体的な内容としては，次のようになります:
- 3.2 Description
- TFHE方式のアルゴリズム
- TFHE方式のアルゴリズムの具体例
- 無限ノルム
- TFHE方式のアルゴリズムの正当性
- 3.3 Leveled Operation
- Tensor積
- gadget行列
- gadget decompostion
- GGSW方式の概要
- TFHE方式の暗号文の足し算
- TFHE方式の暗号文のスカラー倍
- 結局 Leveled Operaion とは何か
- TFHE方式の暗号文とGGSW方式の暗号文の外積
- Cmuxゲート
前回の「３章の流れ」でも触れましたが，3.2で plaintext の暗号化アルゴリズムを定義して，3.3 で暗号文同士の演算を考えていきます．
今回の 3.2 や 3.3 はアルゴリズムレベルの話なので，前回のような「3.1の議論」みたいに項目を設けることはしませんので，悪しからず．
それでは早速見ていきましょう．
TFHE方式のアルゴリズム
TFHEは次の３つ組のアルゴリズムから構成されます．
TFHEは格子暗号ベースなので，公開鍵暗号と捉えられることから，「鍵生成・暗号化・復号化」の３つが必要です．
結局何をやっているのかというと，「TRLWE問題に基づく格子暗号」です．「Torus上の多項式環ベースのLWE問題」のことをTRLWE問題と呼ぶのでした．
$\underline{\mathrm{Def(TFHEの暗号化アルゴリズム)}}$
以下の3つ組の確率的多項式時間アルゴリズム (KeyGen, Encrypt, Decrypt) からなる:
KeyGen$(1^{\lambda}) \mapsto (pk, sk)$
step1
セキュリティパラメータ $\lambda$ を入力として，次の6つのパラメータを取る:
$k$ $\cdots$ 1以上の自然数
$N$ $\cdots$ 2べきの自然数
$\sigma$ $\cdots$ 任意の（正の）実数
$\bar{w}, w, \Omega$ $\cdots$ 全て正整数，ただし $\bar{w} + w \leq \Omega$ を満たす
step2
$\chi$ を $ \mathbb{R} _ N[X] $ 上の正規分布 $\mathcal{N}(0, \sigma^2)$ として，$p = 2^{\bar{w} + w}, \ q = 2^{\Omega}$ とする．
また，$\tilde{s} = (\tilde{s}_0,$ $\tilde{s}_1,$ $\cdots,$ $\tilde{s}_{k - 1})$ $\overset{$}{\leftarrow}$ $\mathbb{B}_N[X]$ とする．
平文空間 $ \tilde{P}_N[X] $ を $ \displaystyle \tilde{P}_N[X] = (\frac{q}{p} \mathbb{Z} / q \mathbb{Z})[X] / (X^N + 1) \subset \hat{\mathbb{Z}_N[X]} = (\mathbb{Z} / q \mathbb{Z}[X]) / (X^N + 1) $ と定める．
step3
このとき，公開鍵 $pk$ を $pk = (k, N, \sigma, p, q)$ で秘密鍵 $sk$ を $sk = \tilde{s}$ とする．
return (pk, sk)
Encrypt$(\mu, pk) \mapsto \tilde{C}$
KeyGenで定義された平文空間から $\mu \in \tilde{P}_N[X]$ と公開鍵 $pk$ を入力とする．
step1
$(\tilde{a}_1,$ $\tilde{a}_2,$ $\cdots,$ $\tilde{a}_k)$ $\overset{$}{\leftarrow}$ $\hat{\mathbb{Z}}_N[X]^k$ と各係数が $\chi$ に従うノイズ $\tilde{e}$ $\overset{$}{\leftarrow}$ $\mathbb{R}_N[X] = \mathbb{R}[X] / (X^N + 1)$ を取る．ノイズ $\tilde{e}$ の各係数 $\tilde{e}_i$ を $\lfloor \tilde{e}_i q \rceil$ で離散化した $\tilde{e}^{\prime}$ を取る．
step2
$\hat{\mathbb{Z}}_N[X]$ $= (\mathbb{Z} / q \mathbb{Z})[X] / (X^N + 1)$ 内での計算で $\displaystyle \tilde{c} = \sum_{j = 1}^k \tilde{s}_j \tilde{a}_j + \mu + \tilde{e}^{\prime} \in \hat{\mathbb{Z}}_N[X]$ を求める．
step3
$\tilde{C}$ $= $ $(\tilde{a}_1,$ $\tilde{a}_2,$ $\cdots,$ $\tilde{a}_k,$ $\tilde{c})$ $\in \hat{\mathbb{Z}}_N[X]^{k + 1}$ とする．$\tilde{C}$ を $\overline{\mathrm{TFHE}}_{\tilde{s}}(\mu)$ と書くことにする．
return $\tilde{C}$
Decrypt$(\tilde{C}, sk) \mapsto \mu$
Encrypt での $\tilde{C} = (\tilde{a}_1, \tilde{a}_2, \cdots, \tilde{a}_k, \tilde{c})$ と秘密鍵 $sk$ を入力とする．
step1
$\hat{\mathbb{Z}}_N[X] = (\mathbb{Z} / q \mathbb{Z})[X] / (X^N + 1)$ 内での計算で $\mu + \tilde{e}^{\prime} = \tilde{C} - \sum_{j = 1}^k \tilde{s}_j \tilde{a}_j$ を求める．
return $Upper_{q, p}(\mu + \tilde{e}^{\prime})$
Encrypt step3 について補足します．
論文中では，秘密鍵 $sk$ による平文 $\mu$ の暗号化アルゴリズムの出力（暗号文） $\mathrm{Encrypt}_{sk}(\mu)$ を $\overline{\mathrm{GLWE}}_{\tilde{s}}(\mu)$ と書いています．恐らく元々論文で書いていたGLWE問題に基づくからなのかなと思います．
しかし，この後にTHFE方式とは別のGGSW方式というのを導入するのですが，結局それもTRLWE問題に基づく（っていうか上記の $\mathrm{Encrypt}_{sk}(\mu)$ をサブルーチンとしてクエリする）ので，なんだかなってことで，$\overline{\mathrm{TFHE}}_{\tilde{s}}(\mu)$ と書きました．
平文空間の定義域が $\displaystyle \displaystyle \tilde{P}_N[X] = (\frac{q}{p} \mathbb{Z} / q \mathbb{Z})[X] / (X^N + 1)$ と急になんか出てきたって感じですが，plaintext のうち，ノイズ部分を除いた部分である padding と cleartext の情報を含んでいる部分であり，plaintext で本質的な部分の情報だけを初めから考えている，という風に解釈できます．
TFHE方式のアルゴリズムの具体例
それでは，具体例を確認してみましょう．前回の「3.1の議論」 で cleartext から plaintext へのエンコードとデコードの具体例を紹介したので，そのときの数値をそのまま使います．
つまり，$N = 4, \ w = 4, \ \Omega = 8, \bar{w} = 2$ で，$p = 2^{\bar{w} + w} = 2^6 = 64, \ q = 2^{\Omega} = 256$ とする．
平文空間は $\tilde{P}_N[X] = (\frac{q}{p} \mathbb{Z} / q \mathbb{Z})[X] / (X^N + 1) = (4 \mathbb{Z} / 64 \mathbb{Z})[X] / (X^4 + 1)$ で， $\mu = 52 + 16X + 36X^2 + 24X^3 \in \tilde{P}_N[X]$ とします．
鍵長パラメタは $k = 2$ で，秘密鍵は $\tilde{s} = (1 + X^2, X + X^2 + X^3) \in \mathbb{B}_N[X] = \mathbb{B}[X]/(X^4 + 1)$ とします．
Encrypt step1
$(\tilde{a}_0, \tilde{a}_1) = (120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3) \in \hat{\mathbb{Z}}_4[X]^2$ と $\tilde{e} = (0.0053 - 0.0011 X + 0.0009 X^2 + 0.0035X^3) \in \mathbb{R}_4[X]$ で，$\lfloor 0.0053 \cdot 256 \rceil = 1$ であり，他の係数も同様にして， $\tilde{e}^{\prime} = 1 + X^3$ を得ます．
＊なんでこんなにノイズが小さいんだと思うかもしれませんが，plaintext の構成上，今回だとノイズは末尾 1 bit に格納する必要があるためです
Encrypt step2（この辺はどうでもええやろって言いながら計算したのでミスあるかもです・・・）
\displaystyle
\begin{align*}
\tilde{c} &= \sum_{j = 1}^2 \tilde{s}_j \tilde{a}_j + \mu + \tilde{e}^{\prime} \\
&= (1 + X^2)(120 + 33X + 9X^2 + 82X^3) + (X + X^2 + X^3)(155 + 13X + 203X^2 + 95X^3) \\
&+ (52 + 16X + 36X^2 + 24X^3) + (1 + X^3) \\
&= (129 + 115 X + 129 X^2 + 115 X^3) + (55 + 197 X + 7 X^2 + 115 X^3) \\
&+ (52 + 16X + 36X^2 + 24X^3) + (1 + X^3) \\
&= (184 + 56 X + 136 X^2 + 230 X^3) + (52 + 16X + 36X^2 + 24X^3) + (1 + X^3) \\
&= 237 + 72 X + 172 X^2 + 255 X^3
\end{align*}
Encrypt step3
\begin{align*}
\tilde{C} &= (\tilde{a}_0, \tilde{a}_1, \tilde{c}) \\
&= (120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 237 + 72 X + 172 X^2 + 255 X^3)
\end{align*}
Decrypt step1
\begin{align*}
\mu + \tilde{e}^{\prime} &= \tilde{c} - \sum_{j = 1}^2 \tilde{s}_j \tilde{a}_j \\
&= 53 + 16 X + 36 X^2 + 25 X^3
\end{align*}
$\mu + \tilde{e}^{\prime}$ の各係数を8 bit 表現したものは，それぞれ，(00110101, 00010000, 00100100, 00011001) となって，
今回のUpper関数は上位6 bit を取り出す（＝ノイズは下位1 bit にしか入らない）ので，Upper関数を噛ませた後の各係数の8 bit 表現は (00110100, 00010000, 00100100, 00011000) となり，無事に plaintext に復号できました．
無限ノルム
ノルムとはベクトルの大きさを与えるものです．「大きさ」とは，そのベクトルと原点（零ベクトル）がどのくらい離れているか，を表し，ノルムによってその空間内に距離を与えることができます．
ノルムには色々な与え方があり，今回は無限ノルムを参照しています．無限ノルムは，直感的には「各成分の絶対値で一番大きいもの」です．
有限次元ベクトルの無限ノルムは次のように定義されます．
$\underline{\mathrm{Def(無限ノルム)}}$
ベクトル $x = (x_1, x_2, \cdots, x_n)$ に対して，$x$ の無限ノルム $||x||_{\infty}$ を次のように定める:
||x||_{\infty} = \max \{ | x_1 |, | x_2 |, \cdots, | x_n | \}
例えば，ベクトル $x = (-3, 2, 0)$ に対しては，$||x||_{\infty} = 3$ です．
論文中では，多項式をベクトルと見ることで無限ノルムを使っています．
TFHE方式のアルゴリズムの正当性
上で出てきた無限ノルムを使って，TFHEのアルゴリズムの正当性を証明します．
任意の平文 $\mu \in \tilde{P}_N[X]$ に対して，$\mathrm{Decrypt}(sk, \mathrm{Encrypt}(pk, \mu)) = \mu$ を示します．
Decrypt step1 まではいいとして，問題となるのは，Decrypt の Upper 関数です．
$\mu + \tilde{e}^{\prime}$ を求めた際に，ノイズが末尾 $\Omega - (\bar{w} + w) - 1$ bit に収まっているような値の必要がある，ということです．
つまり，ノイズの各係数が $2^{\Omega - (\bar{w} + w) - 1}$ 未満である必要があります．
それは無限ノルムを使うと，$|| \tilde{e}^{\prime} ||_{\infty} < \frac{p}{2q} = 2^{\Omega - (\bar{w} + w) - 1}$ と表せます．
すると，$|| \tilde{e}^{\prime} ||_{\infty} < \frac{p}{2q}$ が仮定されていれば，後はUpper関数によって plaintext に復号できますので，これで正当性が示されました．
Tensor積
ここから3.3の内容です．
もちろん行列に関するTensor積です．定義は仰々しいかもしれませんが，例を見れば大したことはないと思います．
ここでは実数成分の行列を考えます．
同じ行列を「複製」したいときや「重ねたい」ときなどに使います．
量子情報では，与えられた行列がそれより小さい行列のTensor積に分解できるかが関わる場面が多いです（分解できないとき，量子エンタングルメント，とか言ったりします）．
$\underline{\mathrm{Def(行列のTensor積)}}$
行列 $A = (a_{i, j}) \in \mathbb{R}^{n_1 \times m_1}, B = (b_{i, j}) \in \mathbb{R}^{n_2 \times m_2}$ に対して，$A$ と $B$ の Tensor 積 $A \otimes B$ を次のように定める:
\begin{align*}
A \otimes B := \begin{pmatrix}
a_{1, 1} B & a_{1, 2} B & \cdots & a_{1, m_1} B \\
a_{2, 1} B & a_{2, 2} B & \cdots & a_{2, m_1} B \\
\vdots & \vdots & \ddots & \vdots \\
a_{n_1, 1} B & a_{n_1, 2} B & \cdots & a_{n_1, m_1} B \\
\end{pmatrix}
\in \mathbb{R}^{(n_1 n_2) \times (m_1 m_2)}
\end{align*}
ここで，$a_{i, j} B$ とは次の行列を表す．
\begin{align*}
a_{i, j} B := \begin{pmatrix}
a_{i, j} b_{1, 1} & a_{i, j} b_{1, 2} & \cdots & a_{i, j} b_{1, m_2} \\
a_{i, j} b_{2, 1} & a_{i, j} b_{2, 2} & \cdots & a_{i, j} b_{2, m_2} \\
\vdots & \vdots & \ddots & \vdots \\
a_{i, j} b_{n_2, 1} & a_{i, j} b_{n_2, 2} & \cdots & a_{i, j} b_{n_2, m_2} \\
\end{pmatrix}
\in \mathbb{R}^{n_2 \times m_2}
\end{align*}
Tensor積では行列の型に指定はないことに注意してください．
つまり，$(m_1, n_1)$ 行列 $A$ と $(m_2, n_2)$ 行列 $B$ の「通常の積」を考えるときは，$n_1 = m_2$ が必要ですが，Tensor積ではそのような条件は不要です．$n_1 \neq m_2$ でもOKです．
例を見てましょう．
\displaystyle A = \begin{pmatrix} 2 & -1 \\ 0 & 5 \end{pmatrix} , \ B = \begin{pmatrix} 1 & 4 \\ -3 & 2 \end{pmatrix}
とします．このとき，$A \otimes B$ は次のように計算できます:
\begin{align*}
A \otimes B &= \begin{pmatrix}
2 B & -1 B \\
0 B & 5 B \\
\end{pmatrix} \\
&= \begin{pmatrix}
2 & 8 & -1 & -4 \\
-6 & 4 & 3 & -2 \\
0 & 0 & 10 & 20 \\
0 & 0 &-15 & 10
\end{pmatrix}
\end{align*}
gadget行列
上のTensor積の例としてgadget行列を考えます．
論文ではTensor積を使って同じベクトルを「複製」した行列として，gadget 行列を使っています．
これはどこで使うのか，どういう意図があるのか，については 今回の「TFHE方式の暗号文とGGSW方式の暗号文の外積」 で解説します．
定義しましょう．
念のため断りますが，$x = (-3, 2, 0)$ なるベクトルを取る，と書いたら，このベクトルは縦ベクトルを表すのが通例です． この辺が曖昧だとTensor積を取った後の行列の型がぶれるので，初めに宣言しておきます．要するに論文中で転置を取っている箇所は，この記事中では転置を取らずにそのまま扱います．
$\underline{\mathrm{Def(gadget行列)}}$
$\ell, \Omega, n$ を正整数とする．$q = 2^{\Omega}$ として，$g = (g_1, g_2, \cdots, g_{\ell}) \in [0, q - 1]^{\ell}$ なるベクトルを取って，$G^T = I_n \otimes g \in (\mathbb{Z} / q \mathbb{Z})^{\ell n \times n}$ なる行列を gadget 行列という．
早速具体例を見てみましょう．
$\ell \leq \Omega$ で，$g = (1, 2, \cdots, 2^{\ell - 1})$ とします．
$\Omega = 6, \ \ell = 4, \ n = 2$ とすると，$q = 64, \ g = (1, 2, 4, 8)$ であり，
\displaystyle
\begin{align*}
G &= I_2 \otimes g \\
&= \begin{pmatrix}
1 & 0 \\
2 & 0 \\
4 & 0 \\
8 & 0 \\
0 & 1 \\
0 & 2 \\
0 & 4 \\
0 & 8
\end{pmatrix} \in (\mathbb{Z} / 64 \mathbb{Z})^{8 \times 2}
\end{align*}
です．
また，論文中で使う（GGSW方式の暗号化で使う）ものとして，$\beta$ を正整数で $\ell \beta \leq \Omega$ を満たすものとします．このとき，$g = (2^{\Omega - \beta}, 2^{\Omega - 2 \beta}, \cdots, 2^{\Omega - \ell \beta})$ とすると，
\displaystyle
\begin{align*}
G &= I_n \otimes g \\
&= \begin{pmatrix}
g & 0 & \cdots & 0 \\
0 & g & \cdots & 0 \\
\vdots & \vdots & \ddots & 0 \\
0 & 0 & \cdots & g
\end{pmatrix} \in (\mathbb{Z} / q \mathbb{Z})^{\ell n \times n}
\end{align*}
です．ただし，行列中の0は長さ $\ell$ の0ベクトル（縦ベクトル）であるとします．
ちなみに，gadget行列はLWE問題のtrapdoor（公開鍵とその情報を組合せると簡単に秘密鍵や平文を求められる情報のこと）となっています．
gadget decompostion
gadget 行列の「逆行列」的なものを考えます．これはどこで使うのか，どういう意図があるのか，については 今回の「TFHE方式の暗号文とGGSW方式の暗号文の外積」 で解説します．
＊上記の軽い説明であれば，本チャプターの最後に記載しています
突然ですが，$13$ の２進展開はどうなるでしょうか．もちろん $1101$ ですね．もし 6 bit で2進展開せよ，と言われたら $001101$ とできます．
また，2進展開は整数だけでなく，有理数にも適用できます．例えば，$\displaystyle \frac{3}{8} = 0 \cdot \frac{1}{2} + 1 \cdot \frac{1}{4} + 1 \cdot \frac{1}{8}$ です．
次に4進展開を考えてみます．$13$ の4進展開は $31$ ですね．では，唐突ですが，$\frac{1}{3}$ の4進展開を考えます．実は $\frac{1}{4} + \frac{1}{4}^2 + \frac{1}{4}^3 + \cdots$ は収束し，その収束先は $\frac{1}{3}$ になります．
実際の計算機上では，$\Omega$ bit しか使えないので，無限和は表現できず，近似値となってしまいますが，「ある程度の近似の元で」有理数を計算機上で表すことを考えていきます．
具体的には，$B$ を2べきとすると，$\hat{\mathbb{T}} = q^{-1} \mathbb{Z} / \mathbb{Z}$ の元を「$B$進展開」すると，gadget 行列の「逆行列」的なものが現れます．
定義を見てみましょう．
$\underline{\mathrm{Def(引数が整数の \ gadget \ decomposition)}}$
$\ell, \Omega, \beta$ を正整数で，$\ell \beta \leq \Omega$ を満たすものする．$g = (2^{\Omega - \beta}, 2^{\Omega - 2 \beta}, \cdots, 2^{\Omega - \ell \beta})$ とする．$q = 2^{\Omega}, B = 2^{\beta}$ で $\forall d \in [0, q - 1]$ を取る．
このとき，任意の $i \in [1, \ell]$ で $\displaystyle d_i \in [- \frac{B}{2}, \frac{B}{2} - 1] \subset \mathbb{Z}$ であって，$g^{-1}(d) := (d_1, \cdots, d_{\ell}) \in \mathbb{Z}^{\ell}$ なるベクトルを考える．
$g^{-1}(d)$ は次の２条件を満たすものとする:
- $\displaystyle \sum_{i = 1}^{\ell} d_i 2^{\Omega - i \beta} = g^{-1}(d) g$
- $\displaystyle | g^{-1}(d) g - d | \leq \frac{q}{2 B^{\ell}} \frac{B}{B - 1} = \frac{B}{B - 1} 2^{\Omega - \beta \ell - 1}$
＊論文では，定義の２つ目の条件の不等式の右辺は $\displaystyle \frac{q}{2 B^{\ell}} = 2^{\Omega - \beta \ell - 1}$ となっていますが，上記が正しいです
先ほどのイメージとはかけ離れたようないかつい定義ですが，多少の補足をします．
$g^{-1}(d)$ とは，「0以上 $q - 1$ 以下の元を $B$ 進展開したときに現れる係数のベクトル」のことで，何が「逆行列」っぽいのかというと，$g$ が与えられたときに，$g^{-1}(d)$ があれば $d$ の情報を復元できるのが逆行列っぽいのです．
ちなみにですが，$g$ が与えられていても，$d$ が変われば，$g^{-1}(d)$ も変わります．$d$ を引数に取っているのはそのためです．
これは具体的には，同じ4進展開でも $3$ を4進展開したときに現れる係数と，$5$ を4進展開したときに現れる係数は異なることから分かります．
$d_i$ の範囲は，$[- \frac{B}{2}, \frac{B}{2} - 1]$ であることに注意してください．
定義での２つ目の条件は，$B$進展開を指定していて，近似の精度を言及したものです．要するに，「普通に」$B$ 進展開をしろよってことです．
上記と同様の議論が $\hat{\mathbb{Z}}$ ではなく，$\hat{\mathbb{Z}}_N[X]$ でも行えます．
これは多項式の各係数に対して，gadget decomposition を行います．
$\underline{\mathrm{Def(引数が多項式の \ gadget \ decomposition)}}$
$\ell, \Omega, \beta$ を正整数で，$\ell \beta \leq \Omega$ を満たすものする．$g = (2^{\Omega - \beta}, 2^{\Omega - 2 \beta}, \cdots, 2^{\Omega - \ell \beta})$ とする．$q = 2^{\Omega}, B = 2^{\beta}$ で $\forall d \in [0, q - 1]$ を取る．
$\tilde{p} = p_0 + p_1 X + \cdots + p_{N - 1} X^{N - 1} \in \hat{\mathbb{Z}}_N[X]$ と置く．
このとき，任意の $n \in [0, N - 1]$ で $\tilde{p}$ の各係数 $p_n$ に対して，
任意の $i \in [1, \ell]$ で $\displaystyle d_i \in [- \frac{B}{2}, \frac{B}{2} - 1] \subset \mathbb{Z}$ であって，$g^{-1}(p_n) := (p_{n, 1}, \cdots, p_{n, \ell}) \in \mathbb{Z}^{\ell}$ なるベクトルを考える．
$g^{-1}(p_n)$ は次の２条件を満たすものとする:
- $\displaystyle \sum_{i = 1}^{\ell} p_{n, i} 2^{\Omega - i \beta} = g^{-1}(p_n) g$
- $\displaystyle | g^{-1}(p_n) g - p_n | \leq \frac{B}{B - 1} \frac{q}{(2B)^{\ell}} = \frac{B}{B - 1} 2^{\Omega- \beta \ell - 1}$
そして，$g^{-1}(\tilde{p}) \in$ $\mathbb{Z}_N[X]^{\ell}$ を $\displaystyle g^{-1}(\tilde{p})$ $= \sum_{n = 0}^{N - 1} g^{-1}(p_n) X^n$ と置く．
これは $\displaystyle || g^{-1}(\tilde{p}) g - \tilde{p} ||_{\infty} \leq \frac{B}{B - 1} 2^{\Omega - \beta \ell - 1}$ を満たす．
多項式の各係数 $g^{-1}(p_n)$ に関して，$\displaystyle | g^{-1}(p_n) g - p_n | \leq \frac{B}{B - 1} 2^{\Omega- \beta \ell - 1}$ が成り立っていて，右辺は $n$ に無関係です．
よって，多項式 $\tilde{p}$ の $| g^{-1}(p_n) g - p_n |$ に関する無限ノルム（$| g^{-1}(p_n) g - p_n |$ で $n$ に関して max の値）を考えても，その値は $\displaystyle \frac{B}{B - 1} 2^{\Omega- \beta \ell - 1}$ 以下です．
ここから定義の最後の式が導かれています．
また，$\displaystyle g^{-1}(\tilde{p}) = \sum_{n = 0}^{N - 1} g^{-1}(p_n) X^n \in \mathbb{Z}_N[X]^{\ell}$ とはどういうことかというと，
\begin{align*}
& \sum_{n = 0}^{N - 1} g^{-1}(p_n) X^n = g^{-1}(p_0) + g^{-1}(p_1) X + \cdots + g^{-1}(p_{N - 1}) X^{N - 1} \\
& = (p_{0, 1}, p_{0, 2}, \cdots, p_{0, \ell}) + (p_{1, 1}, p_{1, 2}, \cdots, p_{1, \ell}) X + \cdots + (p_{N - 1, 1}, p_{N - 1, 2}, \cdots, p_{N - 1, \ell}) X^{N - 1} \\
& = ((p_{0, 1} + p_{1, 1} X + \cdots + p_{N - 1, 1} X^{N - 1}), (p_{0, 2} + p_{1, 2} X + \cdots + p_{N - 1, 2} X^{N - 1}), \cdots \ , (p_{0, \ell} + p_{1, \ell} X + \cdots + p_{N - 1, \ell} X^{N - 1}))
\end{align*}
となり，$p_{i, j} \in \mathbb{Z}$ ですので，最右辺のベクトルの各要素は $\mathbb{Z}_N[X]$ であり， $\ell$ 個の多項式があることから，$\mathbb{Z}_N[X]^{\ell}$ に属することがわかります．
最後に，引数が多項式のベクトルの場合を考えましょう．
上の定義を繰り返し用いるだけです．ベクトルの各要素（多項式）の各係数に対して，gadget decomposition を行います．
$\underline{\mathrm{Def(引数が多項式のベクトルの \ gadget \ decomposition)}}$
$\ell, \Omega, \beta$ を正整数で，$\ell \beta \leq \Omega$ を満たすものする．$g = (2^{\Omega - \beta}, 2^{\Omega - 2 \beta}, \cdots, 2^{\Omega - \ell \beta})$ とする．$q = 2^{\Omega}, B = 2^{\beta}$ で $\forall d \in [0, q - 1]$ を取る．
$k$ を正整数で，$j \in [1, k + 1]$ に対して，$\tilde{p}_j$ $= p_{j, 0}$ $+ p_{j, 1} X +$ $\cdots + p_{j, N - 1} X^{N - 1}$ $\in \hat{\mathbb{Z}}_N[X]$ と置く．$P =$ $(\tilde{p}_1,$ $\tilde{p}_2,$ $\cdots,$ $\tilde{p}_{k + 1})$ $\in \mathbb{Z}_N[X]^{k + 1}$ とする．
このとき，任意の $n \in [0, N - 1]$ で $\tilde{p}_j$ の各係数 $p_{j, n}$ に対して，
任意の $i \in [1, \ell]$ で $\displaystyle d_i \in [- \frac{B}{2}, \frac{B}{2} - 1] \subset \mathbb{Z}$ であって，$g^{-1}(p_{j, n}) :=$ $(p_{j, n, 1},$ $\cdots,$ $p_{j, n, \ell}) \in \mathbb{Z}^{\ell}$ なるベクトルを考える．
$g^{-1}(p_{j, n})$ は次の２条件を満たすものとする:
- $\displaystyle \sum_{i = 1}^{\ell} p_{j, n, i} 2^{\Omega - i \beta} = g^{-1}(p_{j, n}) g$
- $\displaystyle | g^{-1}(p_{j, n}) g - p_{j, n} | \leq \frac{B}{B - 1} \frac{q}{(2B)^{\ell}} = \frac{B}{B - 1} 2^{\Omega- \beta \ell - 1}$
そして，$g^{-1}(\tilde{p})$ $\in \mathbb{Z}_N[X]^{\ell}$ を $\displaystyle g^{-1}(\tilde{p}_j)$ $\displaystyle = \sum_{n = 0}^{N - 1}$ $g^{-1}(p_{j, n}) X^n$ と置く．
更に，$G^{-1}(\tilde{p}) \in$ $\mathbb{Z}_N[X]^{(k + 1) \ell}$ を $G^{-1}(\tilde{p}) =$ $(g^{-1}(\tilde{p}_1),$ $g^{-1}(\tilde{p}_2),$ $\cdots, g^{-1}(\tilde{p}_{k + 1}))$ と置く．
これは $\displaystyle || G^{-1}(\tilde{P}) G - \tilde{P} ||_{\infty} \leq \frac{B}{B - 1} 2^{\Omega - \beta \ell - 1}$ を満たす．
$G^{-1}(\tilde{p}) \in \mathbb{Z}_N[X]^{(k + 1) \ell}$ については，$g^{-1}(\tilde{p}_1) \in \mathbb{Z}_N[X]^{\ell}$ でしたので，それらが $k + 1$ 個あることから分かります．
なぜ引数である多項式のベクトルの長さが $k + 1$ であるかというと，それは TFHE 方式の暗号文の長さを $k + 1$ としていたからです．つまり，$\tilde{C} = \overline{TFHE}_{\tilde{s}}(\mu) \in \hat{\mathbb{Z}}_N[X]^{k + 1}$ でした．
この $\tilde{C}$ に gadget decompostion を行うことを 今回の「TFHE方式とGGSW方式の暗号文の外積」 では考えます．そうすると，下記の GGSW 方式での暗号文で余計に出てきた gadget 行列 $G$ を消すことができます．
多項式の組に作用させても，整数の組が返ってくる，というのがめちゃくちゃ扱いやすいのです
GGSW方式の概要
まず，KeyGenはTFHE方式とほぼ同じなので，割愛します．ただし，平文空間は $\mathbb{Z}_N[X]$ です（この仮定が割とクリティカル）．
ここでは，Encrypt のみ紹介します（Decryptは使わないので）．
＊上記の詳しいアルゴリズムや具体例については，第2.5回のZennの記事 で触れています
Encrypt$(\mu, pk) \mapsto \tilde{C}$
KeyGenで定義された平文空間から $\tilde{m} \in \hat{\mathbb{Z}}_N[X]$ と公開鍵 $pk = (k, N, \sigma, p, q)$ を入力とする．
subroutine
まず，サブルーチンとして，$\overline{TFHE}_{\tilde{s}}(0) \in$ $\hat{\mathbb{Z}}_N[X]^{k + 1} = ((\mathbb{Z} / q \mathbb{Z})[X] / (X^N + 1))^{k + 1}$ を次のように定める:
$(\tilde{a}_1,$ $\tilde{a}_2,$ $\cdots, \tilde{a}_k) \overset{$}{\leftarrow}$ $\hat{\mathbb{Z}}_N[X]^k$ と各係数が $\chi$ に従うノイズ $\tilde{e} \overset{$}{\leftarrow}$ $\mathbb{R}_N[X] = \mathbb{R}[X] / (X^N + 1)$ を取る．ノイズ $\tilde{e}$ の各係数 $\tilde{e}_i$ を $\lfloor \tilde{e}_i q \rceil$ で離散化した $\tilde{e}^{\prime}$ を取る．
以上から，$\hat{\mathbb{Z}}_N[X] = (\mathbb{Z} / q \mathbb{Z})[X] / (X^N + 1)$ 内での計算で $\displaystyle \tilde{c} = \sum_{j = 1}^k$ $\tilde{s}_j$ $\tilde{a}_j +$ $\tilde{e}^{\prime} \in \hat{\mathbb{Z}}_N[X]$ を求めて，$\overline{TFHE}_{\tilde{s}}(0) =$ $(\tilde{a}_1,$ $\tilde{a}_2,$ $\cdots, \tilde{a}_k,$ $\tilde{c}) \in \hat{\mathbb{Z}}_N[X]^{k + 1}$ とする．
step1
$\ell, \beta$ を正整数で，$\ell \beta \leq \Omega$ を満たすものとする．$g = (2^{\Omega - \beta}, 2^{\Omega - 2 \beta}, \cdots, 2^{\Omega - \ell \beta})$ として，$G = I_{k + 1} \otimes g \in \mathbb{Z}_N[X]^{(k + 1) \ell \times (k + 1)}$ と置く．
step2
subroutine を使って，$\overline{TFHE}_{\tilde{s}}(0)$ を求める操作を $(k + 1)\ell$ 回行い，$i \ (1 \leq i \leq (k + 1)\ell)$ 回目の操作で $\overline{TFHE}_{\tilde{s}}(0)_i \in \hat{\mathbb{Z}}_N[X]^{k + 1}$ が得られるとする．
そうして
\tilde{X} = \begin{pmatrix}(\overline{TFHE}_{\tilde{s}}(0)_1)^T \\ (\overline{TFHE}\_{\tilde{s}}(0)\_2)^T \\ \vdots \\ (\overline{TFHE}_{\tilde{s}}(0)_{(k + 1)\ell})^T) \end{pmatrix}
を考える．ここで，$\tilde{X} \in \hat{\mathbb{Z}}_N[X]^{(k + 1) \ell \times (k + 1)}$ ．
step3
$\tilde{C} = \tilde{X} + \tilde{m} G \in \hat{\mathbb{Z}}_N[X]^{(k + 1) \ell \times (k + 1)} = ((\mathbb{Z} / q \mathbb{Z})[X] / (X^N + 1))^{(k + 1) \ell \times (k + 1)}$ を求める．$\tilde{C}$ を $\overline{\mathrm{GGSW}}_{\tilde{s}}(\mu)$ と書くことにする．
return $\tilde{C}$
なぜ途中でTFHE方式での0の暗号文を加えるのか，については 今回の「TFHE方式の暗号文とGGSW方式の暗号文の外積」 で解説します．
Encryptについて
舞台は $\hat{\mathbb{Z}}[X]$ ，つまり多項式ではありますが，「数」のように扱っていることに注意してください．
ちなみに上では，$\hat{\mathbb{Z}}[X]$ 内で考えていると書きましたが，平文の定義域が $\hat{\mathbb{Z}}_N[X]$ ではなく $\mathbb{Z}_N[X]$ なのは誤植ではなく，クリティカルな仮定です （step3 の始めで説明しています）
subroutine
サブルーチンはTFHE方式でやっていることそのままです．平文は0なので，単に秘密鍵とランダムベクトルを掛け合わせたものに更にノイズを加えたものが，暗号文になります．
その暗号文の長さは $k + 1$ です（先頭 $k$ 個がランダムベクトル $\tilde{a}_i$ で最後が暗号文 $\tilde{c}$ です）．
step1
$g = (2^{\Omega - \beta}, 2^{\Omega - 2 \beta}, \cdots, 2^{\Omega - \ell \beta})$ とした gadget 行列 $G$ を構成します．
$g$ の要素は全て $\hat{\mathbb{Z}}$ の元と見ることができる（$q = 2^{\Omega}$ 以下のため）上に，多項式の定数項とみなすことで，$g \in \hat{\mathbb{Z}}_N[X]^{\ell}$ と考えることができます．
また，$I_{k + 1}$ についても，1を$\hat{\mathbb{Z}}$ の元であり，多項式の定数項とみなすことで，$I_{k + 1} \in$ $\hat{\mathbb{Z}}_N[X]^{(k + 1)(k + 1)}$ と考えられます．
よって，$G \in \hat{\mathbb{Z}}_N[X]^{(k + 1) \ell \times (k + 1)}$ です．
＊始めに注意しましたが，上で書いたベクトルや行列の要素は全て「多項式」です
＊Gの概形は 今回の「gadget 行列」 の具体例で見たように，かなり「細長い」イメージです
step2
TFHEで0を暗号化する，ということを $(k + 1)\ell$ 回（step1 で作った $G$ の行数に対応）行います．一回行うと長さ $k + 1$ のベクトルが得られるので，全体で $(k + 1)\ell \times (k + 1)$ の行列ができます．要素は $\hat{\mathbb{Z}}_N[X]$ 内です．
ちなみに $\overline{TFHE}_{\tilde{s}}(0)_i =$ $(\tilde{a}_{i,1},$ $\tilde{a}_{i,2},$ $\cdots, \tilde{a}_{i,k+1},$ $\tilde{c}_i)$ について $\tilde{a}_{i,1}$ や $\tilde{a}_{i,2}$ などは全てランダムなので，各行や各列で異なる多項式が現れます
＊行列っぽさを意識して，下付きの添字は「,」で区切っています
$\tilde{c}_i$ などは0のTFHE方式による暗号文です．
step3
始めは平文 $\mu \in \mathbb{Z}_N[X]$ の gadget 行列 $G$ へのスカラー倍を考えています．つまり，$G$ の各要素を $\mu$ 倍しています．このとき $\hat{\mathbb{Z}}_N[X]$ 内での演算，つまり，係数は $\hat{\mathbb{Z}} = \mathbb{Z} / q \mathbb{Z}$ で考えていることに注意してください．
ここが分かりづらいので，何度も「多項式」を「数」と考えている，と書いています．
もちろん上記の演算は実際には（多項式） $\times$ （多項式）なので，色々展開して係数を $\hat{\mathbb{Z}}$ に抑えて（＝$\mathrm{mod} \ q$ で計算して）いることに注意してください．
ただし，結果的に（多項式） $\times$ （多項式）は（多項式）であり，特に $N - 1$ 次以下ですので，$\hat{\mathbb{Z}}_N[X]$ の要素となります．
そして，上記とstep2でできた $\hat{\mathbb{Z}}_N[X]^{(k + 1)\ell \times (k + 1)}$ の行列 $\tilde{X}$ との和で暗号文とします．
TFHE方式の暗号文の足し算
Leveled operation というのは，演算回数を制限して，足し算や掛け算を行うことで，ノイズの増大の影響を防ぐ，ということです．今回の記事では４つ扱います．
ここでは暗号文の足し算を考えますが，Torusには和が定まっていましたね．それを思い返すと，それと同じように考えればOKです．
参照：第１回「Torus」
公開鍵 $pk = (k, N, \sigma, p, q)$ と秘密鍵 $sk$ と平文 $\mu_1, \mu_2 \in \tilde{P}_N[X]$ が与えられたとき，$\overline{\mathrm{TFHE}}_{\tilde{s}}(\mu_1)$ と $\overline{\mathrm{TFHE}}_{\tilde{s}}(\mu_2)$ の和を考えます．
\begin{align*}
\overline{\mathrm{TFHE}}_{\tilde{s}}(\mu_1) + \overline{\mathrm{TFHE}}_{\tilde{s}}(\mu_2) = \overline{\mathrm{TFHE}}_{\tilde{s}}(\mu_1 + \mu_2)
\end{align*}
を示します．
\displaystyle \begin{align*}
\overline{\mathrm{TFHE}}_{\tilde{s}}(\mu_1) + \overline{\mathrm{TFHE}}_{\tilde{s}}(\mu_2)
& = (\tilde{a}_{11}, \tilde{a}_{21}, \cdots, \tilde{a}_{k1}, \tilde{c}_1)
+ (\tilde{a}_{12}, \tilde{a}_{22}, \cdots, \tilde{a}_{k2}, \tilde{c}_2) \\
& = (\tilde{a}_{11}, \tilde{a}_{21}, \cdots, \tilde{a}_k1, \sum_{j = 1}^k \tilde{s}_j \tilde{a}_{j1} + \mu_1 + \tilde{e}^{\prime}_1) \\
& + (\tilde{a}_{12}, \tilde{a}_{22}, \cdots, \tilde{a}_{k2}, \sum_{j = 1}^k \tilde{s}_j \tilde{a}_{j2} + \mu_2 + \tilde{e}^{\prime}_2) \\
& = (\tilde{a}_{11} + \tilde{a}_{12}, \tilde{a}_{21} + \tilde{a}_{22}, \cdots, \tilde{a}_{k1} + \tilde{a}_{k2}, \sum_{j = 1}^k \tilde{s}_j (\tilde{a}_{j1} + \tilde{a}_{j2}) + (\mu_1 + \mu_2) + (\tilde{e}^{\prime}_1 + \tilde{e}^{\prime}_2)
& = \overline{\mathrm{TFHE}}_{\tilde{s}}(\mu_1 + \mu_2)
\end{align*}
ですので，示されました．
もちろん $\mu_1$ を暗号化する際に出てくるノイズ $\tilde{e}^{\prime}_1$ と $\mu_2$ を暗号化する際に出てくるノイズ $\tilde{e}^{\prime}_2$ の和 $\displaystyle || \tilde{e}^{\prime}_1 +$ $\tilde{e}^{\prime}_2$ $||_{\infty} < \frac{p}{2q}$ という仮定を満たす必要があります．
参照：今回の「TFHE方式のアルゴリズムの正当性」
TFHE方式の暗号文のスカラー倍
続いてスカラー倍です．スカラー倍もTorusのときと考え方は同様です．
第２回「３章前説の議論」 でも書きましたが，$\hat{\mathbb{T}}$ 内で掛け算は定義されませんが，スカラー倍は定義できます．
公開鍵 $pk = (k, N, \sigma, p, q)$ と秘密鍵 $sk$ と平文 $\mu_1,$ $\mu_2 $ $\in \tilde{P}_N[X]$ と整数 $K$ が与えられたとき，$\overline{\mathrm{TFHE}}_{\tilde{s}}(\mu_1)$ と $K$ とのスカラーを考えます．
\begin{align*}
K \cdot \overline{\mathrm{TFHE}}_{\tilde{s}}(\mu) = \overline{\mathrm{TFHE}}_{\tilde{s}}(K \cdot \mu)
\end{align*}
を示します．
$K \cdot \overline{\mathrm{TFHE}}_{\tilde{s}}(\mu)$ とは $K \geq 0$ であれば $\overline{\mathrm{TFHE}}_{\tilde{s}}(\mu)$ を $K$ 回足す（$\overline{\mathrm{TFHE}}_{\tilde{s}}(\mu)$ は足し算できることは直前の 「TFHE方式の暗号文の足し算」 でチェック済み）ということです．
$K < 0$ であれば，$-K > 0$ で，$- \overline{\mathrm{TFHE}}_{\tilde{s}}(\mu)$ を $- K$ 回足す（$\overline{\mathrm{TFHE}}_{\tilde{s}}(\mu)$ は 単位元を $\overline{\mathrm{TFHE}}_{\tilde{s}}(0)$ とみなした $\overline{\mathrm{TFHE}}_{\tilde{s}}(\mu)$ の逆元）ということです．
$K$ の正負が変わってもやることは同じです．
$K \geq 0$ のとき
\begin{align*}
& K \cdot \overline{\mathrm{TFHE}}_{\tilde{s}}(\mu) \\
& = K \cdot (\tilde{a}_1, \tilde{a}_2, \cdots, \tilde{a}_k, \tilde{c}) \\
& = K \cdot (\tilde{a}_1, \tilde{a}_2, \cdots, \tilde{a}_k, \sum_{j = 1}^k \tilde{s}_j \tilde{a}_j + \mu + \tilde{e}^{\prime}) \\
& = (K \cdot \tilde{a}_1, K \cdot \tilde{a}_2, \cdots, K \cdot \tilde{a}_k, \sum_{j = 1}^k \tilde{s}_j (K \cdot \tilde{a}_j) + K \cdot \mu + K \cdot \tilde{e}^{\prime}) \\
& = \overline{\mathrm{TFHE}}_{\tilde{s}}(K \cdot \mu)
\end{align*}
ですので，示されました．
もちろん $\mu$ を暗号化する際に出てくるノイズ $\tilde{e}^{\prime}$ について $\displaystyle || K \cdot \tilde{e}^{\prime}||_{\infty} < \frac{p}{2q}$ という仮定を満たす必要があります．
結局 Leveled Operaion とは何か
今回の「TFHE方式の暗号文の足し算」 の始めに，
Leveled operation というのは，演算回数を制限して，足し算や掛け算を行うことで，ノイズの増大の影響を防ぐ
と書きましたが，具体的にどういうことかを解説します（そうしないと結局なんだったのかを解説するタイミングがないため）．
例えば，公開鍵 $pk = (k, N, \sigma, p, q)$ と秘密鍵 $sk$ と平文 $\mu \in \tilde{P}_N[X]$ が与えられたとします．このとき，$\overline{\mathrm{TFHE}}_{\tilde{s}}(\mu)$ に離散化された0ではないノイズ $\tilde{e}^{\prime}$ が加えられているとき，$\overline{\mathrm{TFHE}}_{\tilde{s}}(\mu)$を $q$ 回足すことはできるのか？ということを考えます．
結論から書くと無理です．離散化されたノイズ $\tilde{e}^{\prime}$ には条件が必要で，それが $\displaystyle || \tilde{e}^{\prime} ||_{\infty} < \frac{p}{2q}$ というものでした．
$\tilde{e}^{\prime}$ が0でないとき，$|| \tilde{e}^{\prime} ||_{\infty} \neq 0$ なので，$|| \tilde{e}^{\prime} ||_{\infty} \in \mathbb{N}$ だから，$|| \tilde{e}^{\prime} ||_{\infty} \geq 1$ が成り立ちます．
すると，$\overline{\mathrm{TFHE}}_{\tilde{s}}(\mu)$を $q$ 回足すというのは，$\tilde{e}^{\prime}$ も $q$ 回足されるので，$|| q \cdot \tilde{e}^{\prime} ||_{\infty} \geq q$ となってしまい，$\displaystyle || q \cdot \tilde{e}^{\prime} ||_{\infty} < \frac{p}{2q}$ を満たしません．
そうすると，復号ができない（正確には，復号できるけど元の平文に戻らない）ので困るよねっていう話になります．
1つの解決策が，「演算回数に制約を設ける」というものです．つまり，$q$ 回も足そうとするからだめなのであって，例えば，$\frac{q}{p}$ 回までしか足し算はできない，とかにすると，ノイズによっては上手く行ったり上手くいかなかったりということになります．
今回の Leveled operation の章では，一々「何回までなら演算ができる」というのは指定しません（その回数以内であることを暗に仮定している）．
その代わりに演算を行うことで得られるノイズを評価することで，その演算の正当性を保証している，ということになります．
ちなみにですが，暗号文を $K$ 回足したときのノイズの影響と暗号文にスカラー $K$ を掛けたときのノイズの影響は同じものです．
そもそもスカラー $K$ を掛ける，というのは，$K \geq 0$ なら，$K$ 回足す，ということに対応しているためです．
TFHE方式の暗号文とGGSW方式の暗号文の外積
TFHE 方式の暗号文同士の足し算ができるのなら，暗号文の掛け算もできないか，と考えるのは自然な発想だと思います．しかし，これは上手くいきません．
でも「掛け算っぽい」ことならできます．それが今回紹介するTFHE方式の暗号文とGGSW方式の暗号文の外積です．
やりたいこととしては，平文 $\mu \in \tilde{P}[X]$ を TFHE 方式で暗号化した暗号文 $\tilde{c}$ と 平文 $\tilde{m} \in \mathbb{Z}[X]$ を GGSW 方式で暗号化した暗号文 $\tilde{c}^{\prime}$ との「掛け算っぽい」ものを考えて，その暗号文は $\mu \tilde{m} \in \tilde{P}[X]$ を TFHE 方式で暗号化した暗号文に相当する，というイメージです．
手法としては，gadget decomposition を使って，暗号文を整数係数のベクトルに「引き戻す」ことを行います．
ちなみに「あれ？Torusの掛け算って考えないんじゃなかったっけ？Torusの暗号文は掛け算できるの？」と思うかもしれませんが，$\mathbb{T}$ を $\hat{\mathbb{Z}} = \mathbb{Z} / q \mathbb{Z}$ に離散化していることを思い出してください．
参照：第２回「hatについて」
$\underline{\mathrm{Def(external \ product)}}$
GGSW方式のKeyGenを行い，その出力を $(pk = (k, N, \sigma, p, q), sk)$ とする．
また，GGSW方式での平文として $m_1$ $\in \mathbb{Z}_N[X]$ を取り，$\tilde{c}_1$ $= \overline{\mathrm{GGSW}}_{\tilde{s}}(m_1)$ とする．また，$\mu_2$ $\in \tilde{P}_N[X]$ を TFHE 方式での平文として，$c_2$ $= \overline{\mathrm{TFHE}}_{\tilde{s}}(\mu_2)$ とする．
また，$\ell, \beta$ を正整数で，$\ell \beta \leq \Omega$ を満たすものとする．$g = (2^{\Omega - \beta}, 2^{\Omega - 2 \beta}, \cdots, 2^{\Omega - \ell \beta})$ として，$G = I_{k + 1} \otimes g$ $\in \mathbb{Z}_N[X]^{(k + 1) \ell \times (k + 1)}$ と置く．
このとき，$\tilde{c}_1$ と $\tilde{c}_2$ の external product を $\tilde{c}_1 \boxdot$ $\tilde{c}_2$ と書いて，$g$ に対する gadget decomposition を用いて $\tilde{c}_1 \boxdot \tilde{c}_2$ $= G^{-1}(\tilde{c}_2)$ $\tilde{c}_1$ と定める．$\tilde{c}_1 \boxdot$ $\tilde{c}_2$ を $\tilde{c}_3$ と置く．
結局，何をやっているのかというと，
\begin{align*}
& \tilde{c}_1 \boxdot \tilde{c}_2 \\
& = G^{-1}(\tilde{c}_2) \tilde{c}_1 \\
& = G^{-1}(\tilde{c}_2) (\tilde{X} + m_1 G) \\
& = G^{-1}(\tilde{c}_2) \tilde{X} + G^{-1}(\tilde{c}_2) m_1 G \\
& = G^{-1}(\tilde{c}_2) \tilde{X} + m_1 G^{-1}(\tilde{c}_2) G \\
& \sim m_1 c_2
\end{align*}
となっています．
最後の式変形についてです．
まず，$G^{-1}(\tilde{c}_2) \tilde{X}$ に関しては，$\tilde{X}$ は TFHE 方式で0を暗号化したものなので，TFHE 方式の観点で見るとここは0とみなせます．
次に，$m_1$ $G^{-1}(\tilde{c}_2) G$ ですが，$G^{-1}(\tilde{c}_2) G$ の部分が誤差ありだけど，$c_2$ とみなせる，というのが gadget decomposition の話でした．
よって，$m_1$ $G^{-1}(\tilde{c}_2)$ $G \sim m_1$ $c_2$ と考えられます．
また，$m_1 \in$ $\mathbb{Z}_N[X]$ なので，$\mu_2$ へのスカラーと見ることができます．よって，$m_1$ $c_2$ $= m_1$ $\overline{\mathrm{TFHE}}_{\tilde{s}}(\mu_2)$ $= \overline{\mathrm{TFHE}}_{\tilde{s}}(m_1 \mu_2)$ が成り立ちます．
まとめると，$\tilde{c}_1 \boxdot$ $\tilde{c}_2$ は $m_1$ $\mu_2$ を TFHE 方式で暗号化したものになっている，ということです．
これを見ると色々とわかることがあります．
とその前に，gadget decomposition について，重要なイメージを再掲します．
多項式の組に作用させても，整数の組が返ってくる，というのがめちゃくちゃ扱いやすいのです
-
gadget decomposition はどう使われるのか
→$\tilde{c}_1 = \tilde{X} + m_1 G$ を TFHE 方式の観点から見ると，$\tilde{X}$ はほぼ無視できる．そこで，$\tilde{c}_2$ の情報込みで，$m_1 G$ の $G$ を消そうと思うと，自然と gadget decomposition が考えられる． -
なぜ gadget 行列を使うのか
→gadget decomposition 的なことをできる行列であれば，なんでも良い．たぶん他にもある． -
GGSW 方式で TFHE 方式で0の暗号文を加えるのはなぜか
→$\tilde{c}_1 = \tilde{X} + m_1 G$ で $\tilde{X}$ を加えないとほぼ平文状態なので，すぐに破られるため．ただ，考え方としては，$\tilde{c}_1 = (ノイズ) + m_1 G$ で，「簡単にTFHE方式へ変換できるような扱いやすいノイズ」として，TFHE 方式での0の暗号文を加えているのだと思います．
CMuxゲート
これまでの暗号文に関する３つの演算を理解していれば（それが難しいんですが・・・），この部分は楽だと思います．
タイトルのCMux は Controlled Multiplexer の略称のことです．
$b = 0, 1$ として，$b$ の値に応じて出力を変えたいときがあります．それを暗号文の状態で行いたい，そういうモチベーションがCMuxゲートにあります．
早速定義しましょう．
$\underline{\mathrm{Def(CMux \ gate)}}$
GGSW方式のKeyGenを行い，その出力を $(pk = (k, N, \sigma, p, q), sk)$ とする．
GGSW方式での平文として $b \in \mathbb{B}$ を取り，$\tilde{c} = \overline{\mathrm{GGSW}}_{\tilde{s}}(b)$ とする．また，$\mu_0,$ $\mu_1$ $\in \tilde{P}_N[X]$ を TFHE 方式での平文として，$c_0$ $= \overline{\mathrm{TFHE}}_{\tilde{s}}(\mu_0),$ $c_1$ $= \overline{\mathrm{TFHE}}_{\tilde{s}}(\mu_1)$ とする．
このとき，$b, \tilde{c}, c_0,$ $c_1$ をインプットとして，$\tilde{c}^{\prime} = \tilde{c} \boxdot (c_1$ $- c_0)$ $+ c_0$ を出力する．これを $\mathrm{CMux}(b, \tilde{c},$ $c_0,$ $c_1)$ と書く．
厳密には $\tilde{c}$ は $b$ の情報も含んでいますが，最終的なインプットとして必要なので，上記では付け加えています（論文では省かれていますが）．
$b = 0$ のとき，$\mathrm{CMux}(0, \tilde{c},$ $c_0,$ $c_1)$ $= c_0$ であり，$b = 1$ のとき，$\mathrm{CMux}(1, \tilde{c},$ $c_0,$ $c_1)$ $= c_1$ です．
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！