今回の記事は下記の記事からの続きとなります．
原著論文：プログラマブルブートストラップの原著論文
第１回：第１回
第２回：第２回
第2.5回:第2.5回
プログラマブルブートストラップの原著論文の第２〜４章を厳密に考察します．
全体を通して使う記号や前提知識などは第１回目の記事にまとめています．
本論文全体の流れ
全体の前提知識と参考文献
この連載を読みやすくリメイクしたQiitaの記事
第１回：第１回
第２回：第２回
第３回：第３回
突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください
全４回通しでの目次
第１回
- 本論文全体の流れ
- 前提知識
- 今回出てくる予備知識のまとめ
- 2.1 Torus and Torus Polynomials
- Torus
- 加群
- 多項式環
- 既約多項式と円分多項式
- Torus上の多項式
- 2.2 Probability Distributions
第２回
- 今回出てくる予備知識のまとめ
- Appendix A : Complexity Assumptions Over the Real Torus
- 3章前説
- 3章の流れ
- ギリシャ文字と花文字
-
\hat{\mathbb{Z}} と \hat{\mathbb{T}}
- 3章前説の議論
- 3章前説の議論の考察
- 3.1 Encoding/Decoding Messages
- lift
- Upper
- 3.1の議論
- 3.1の議論の考察
第2.5回（番外編）
- なぜ番外編が必要なのか
- 今回出てくる予備知識のまとめ
- GGSW方式とは
- 無限ノルム
- Tensor積
- gadget行列
- gadget decomposition
- GGSW方式のアルゴリズム
- GGSW方式のアルゴリズムの具体例
- これまでの議論の考察１
- GGSW方式の暗号文の足し算
- GGSW方式の暗号文同士の内積
- これまでの議論の考察２
第３回（イマココ）
- 今回出てくる予備知識のまとめ
- 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の議論の考察
今回は第３回目で，
3 Discretized TFHE
3.2 Description
3.3 Leveled Operation
正直なところここからが本番って感じです．
これですら目次たっぷりのボリューミーなのに，GGSW方式を１からやるのは無理です()（ので番外編を作りました）．
具体的な内容としては，次のようになります:
- 今回出てくる予備知識のまとめ
- 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の議論の考察
前回の「３章の流れ」でも触れましたが，3.2で plaintext の暗号化アルゴリズムを定義して，3.3 で暗号文同士の演算を考えていきます．
今回の 3.2 や 3.3 はアルゴリズムレベルの話なので，前回のような「3.1の議論」みたいに項目を設けることはしませんので，悪しからず．
また，「TFHE方式の暗号文とGGSW方式の暗号文の外積」では，第2.5回の内容を仮定します．
それに伴い，
今回の「無限ノルム」 は 第2.5回の「無限ノルム」 と同じ内容
今回の「Tensor積」 も 第2.5回の「Tensor積」 と同じ内容
今回の「gadget行列」 も 第2.5回の「gadget行列」 と同じ内容
今回の「gadget decomposition」 も 第2.5回の「gadget decomposition」 と同じ内容
です．一応，番外編を読まずともこの記事は読めるようになっています．
それでは早速見ていきましょう．
今回出てくる予備知識のまとめ
前提知識以外の数学的な予備知識は適宜まとめてはいますが，一覧がほしい方もいらっしゃるかもなので，先にまとめます．折りたたみで出てくる概念のみを対象で，本文中に出てくるものは目次を参考にしてください．
順番は今回の記事で出てくる順で，内容は定義だけざっと並べています．
L_p ノルム
\underline{\mathrm{Def(L_pノルム)}}
1 \leq p < \infty なる実数で，ベクトル x = (x_1, x_2, \cdots, x_n) \in \mathbb{R}^n に対して，x の L_p ノルム ||x||_p を次のように定める:
\begin{align*}
||x||_p = \sqrt[p]{|x_1|^p + |x_2|^p + \cdots + |x_n|^p}
\end{align*}
TFHE方式のアルゴリズム
TFHEは次の３つ組のアルゴリズムから構成されます．
TFHEは格子暗号ベースなので，公開鍵暗号と捉えられることから，「鍵生成・暗号化・復号化」の３つが必要です．
結局何をやっているのかというと，「TRLWE問題に基づく格子暗号」です．「Torus上の多項式環ベースのLWE問題」のことをTRLWE問題と呼ぶのでした．
参照：第２回「TLWEと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(\tilde{\mu}, pk) \mapsto \tilde{C}
KeyGenで定義された平文空間から \tilde{\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 + \tilde{\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 \tilde{\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) 内での計算で \tilde{\mu} + \tilde{e}^{\prime} = \tilde{C} - \sum_{j = 1}^k \tilde{s}_j \tilde{a}_j を求める．
return \mathrm{Upper}_{q, p}(\tilde{\mu} + \tilde{e}^{\prime})
Encrypt step3 について補足します．
論文中では，秘密鍵 sk による平文 \mu の暗号化アルゴリズムの出力（暗号文） \mathrm{Encrypt}_{sk}(\tilde{\mu}) を \overline{\mathrm{GLWE}}_{\tilde{s}}(\tilde{\mu}) と書いています．恐らく元々論文で書いていたGLWE問題に基づくからなのかなと思います．
しかし，この後にTHFE方式とは別のGGSW方式というのを導入するのですが，結局それもTRLWE問題に基づく（っていうか上記の \mathrm{Encrypt}_{sk}(\tilde{\mu}) をサブルーチンとしてクエリする）ので，なんだかなってことで，\overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}) と書きました．
また，平文空間がよく分からない・・・という方は次の折りたたみを.
平文空間
平文空間の定義域が \displaystyle \displaystyle \tilde{P}_N[X] = (\frac{q}{p} \mathbb{Z} / q \mathbb{Z})[X] / (X^N + 1) と急になんか出てきたって感じですが，これは一体どういうことかを解説します．
まず，\hat{\mathbb{Z}}_N[X] は Torus 内の多項式として扱っていることを思い出してください．
参照：第２回「hatについて」
つまり，Torus内の多項式であって，その係数の定義域は \displaystyle \frac{q}{p} \mathbb{Z} / q \mathbb{Z} であるようなもの，ということです．
さて，この \cfrac{q}{p} どこかで見覚えがないでしょうか．そう，Upper 関数ですね．
参照：第２回「Upper」
つまり，\cfrac{q}{p} とは，plaintext のうち，ノイズの情報を含む部分のことでした．そこで，\cfrac{q}{p} 倍するというのは，左にそれだけずらす，ということです．
よって，\displaystyle \frac{q}{p} \mathbb{Z} とは，plaintext のうち，ノイズ部分を除いた部分である padding と cleartext の情報を含んでいる部分と言えます．
plaintext で本質的な部分の情報だけを初めから考えている，という風に解釈できます．
最後の \mathrm{Upper}_{q, p}(\tilde{\mu} + \tilde{e}^{\prime}) に関して，元々のUpper関数の引数は，\mathbb{Z} / q \mathbb{Z} だったので，今回は引数として多項式が入っているのはおかしい！と思うかもしれませんが，これは，各係数ごとにUpper関数を作用させる，ということです．
つまり，\tilde{\mu} + \tilde{e}^{\prime} = \tilde{\mu}_{e, 0} + \tilde{\mu}_{e, 1} X + \cdots + \tilde{\mu}_{e, N - 1} X^{N - 1} としたとき，
\displaystyle \begin{align*}
& \mathrm{Upper}_{q, p}(\tilde{\mu} + \tilde{e}^{\prime}) \\
& = \mathrm{Upper}_{q, p}(\tilde{\mu}_{e, 0} + \tilde{\mu}_{e, 1} X + \cdots + \tilde{\mu}_{e, N - 1} X^{N - 1}) \\
& = \mathrm{Upper}_{q, p}(\tilde{\mu}_{e, 0}) + \mathrm{Upper}_{q, p}(\tilde{\mu}_{e, 1}) X + \cdots + \mathrm{Upper}_{q, p}(\tilde{\mu}_{e, N - 1}) X^{N - 1} \\
& = \tilde{\mu}_{0} + \tilde{\mu}_{1} X + \cdots + \tilde{\mu}_{N - 1} X^{N - 1}
\end{align*}
ということです．
公開鍵暗号などの定義は次の書籍を参考にしています（第１回の記事の参考文献にも追記しました）
聖書（今のところ毎回出てきている）
耐量子計算機暗号
ひとまず暗号の初学者向け（代数・初等整数論も計算量も書かれていて，格子が割と充実しています）
An Introduction to Mathematical Cryptography (Undergraduate Texts in Mathematics)
全部書きましたって感じ（計算量の記述が少ないのが惜しい，アルゴリズムなどの手法が充実しています）
Cryptography Made Simple (Information Security and Cryptography)
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) で， \tilde{\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) とします．
上記は平文以外，第2.5回「GGSW方式のアルゴリズムの具体例」 と同じ設定にしています．
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 + \tilde{\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*}
\tilde{\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*}
\tilde{\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} を次のように定める:
\begin{align*}
||x||_{\infty} = \max \{ | x_1 |, | x_2 |, \cdots, | x_n | \}
\end{align*}
L_p ノルム
実はもう少し一般的な定義が知られています．
\underline{\mathrm{Def(L_pノルム)}}
1 \leq p < \infty なる実数で，ベクトル x = (x_1, x_2, \cdots, x_n) に対して，x の L_p ノルム ||x||_p を次のように定める:
\begin{align*}
||x||_p = \sqrt[p]{|x_1|^p + |x_2|^p + \cdots + |x_n|^p}
\end{align*}
各要素の絶対値を p 乗して総和を取ってから，p 乗根を取っています．
p = 1 なら Manhattan 距離ですし，p = 2 なら Euclid 距離です．無理して p = \infty と考えると，各要素の \mathrm{max} となります．
例えば，ベクトル x = (-3, 2, 0) に対しては，||x||_{\infty} = 3 です．
論文中では，多項式をベクトルと見ることで無限ノルムを使っています．
TFHE方式のアルゴリズムの正当性
上で出てきた無限ノルムを使って，TFHEのアルゴリズムの正当性を証明します．
任意の平文 \tilde{\mu} \in \tilde{P}_N[X] に対して，\mathrm{Decrypt}(sk, \mathrm{Encrypt}(pk, \tilde{\mu})) = \tilde{\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 に復号できますので，これで正当性が示されました．
3.2の議論の考察
ここでは本文の議論をもう１歩踏み込んだ考察をします．踏み込み方は人それぞれだと思うので，興味のない方は飛ばしてくださって構いません．
「ノイズは小さすぎても大きすぎてもダメ」
みたいな文言を見たことないでしょうか．
直感的には，図で考えると，\Omega bit のうち，\Omega - (\bar{w} + w) - 1 bit 分だけノイズが入るのだから，割合的に \frac{2^{\Omega - (\bar{w} + w) - 1}}{2^\Omega} ぐらいなんじゃないかなぁと思うかもしれません．概ね正しいのですが，ここでは実数範囲まで拡張して，もう少し精密に（ギリギリを狙って）考えて見ます．
一旦状況を整理します．\bar{w}, w, \Omega で \bar{w} + w \leq \Omega を満たす正整数を固定します．そして，p = 2^{\bar{w} + w}, \ q = 2^{\Omega} とします．
ノイズ \tilde{e} の各係数 e_i を離散化した \tilde{e}^{\prime} について，各係数 \tilde{e}^{\prime}_i = \lceil q \cdot e_i \rfloor を考えます．
任意の 1 \leq i \leq k で \tilde{e}^{\prime}_i の上限を考えましょう．\lceil \cdot \rfloor の定義から \tilde{e}^{\prime}_i \in \mathbb{Z} に注意します．
ノイズは，下位 \Omega - (\bar{w} + w) - 1 bit に収まる必要があるのでした．すると，\tilde{e}^{\prime}_i < 2^{\Omega - (\bar{w} + w) - 1} つまり， \tilde{e}^{\prime}_i \leq 2^{\Omega - (\bar{w} + w) - 1} - 1 であることが必要です．これは \tilde{e}^{\prime}_i \leq \frac{1}{2} \frac{q}{p} - 1 です．
このとき，\lceil q \cdot e_i \rfloor \leq \frac{1}{2} \frac{q}{p} - 1 ですので，q \cdot e_i < \frac{1}{2} \frac{q}{p} - \frac{1}{2} が成り立ちます．
よって，\displaystyle e_i < \frac{1}{2} \left( \frac{1}{p} - \frac{1}{q} \right) = \frac{q - p}{2q} が必要です．
元の \displaystyle e_i < \frac{p}{2q} と比べると，例えば \Omega = (\bar{w} + w) + 2 つまり q = 4p のとき，\displaystyle \frac{q - p}{2q} = 3 \frac{p}{2q} ですので，余裕があることがわかります．
今回の「TFHE方式のアルゴリズムの具体例」 では，p = 64, q = 256 でしたので，任意の i \in [0, 3] に対して，
\displaystyle \begin{align*}
e_i < \frac{1}{2} \left( \frac{1}{64} - \frac{1}{256} \right) = \frac{3}{512} < 0.0059
\end{align*}
なら，ノイズが下位1 bit に収まってくれて，具体例ではノイズの係数が 0.0059 未満で取れているので確かにOKです．
\displaystyle \frac{p}{2q} で上界を設定した方が正当性の証明はしやすいですが，もう少しギリギリを狙うこともできる，ということでした．
では，下界を考えて見ましょう．自明には0以上なのですが，例えば，今回の具体例でノイズが全て 0.00000001 とかだったら，\tilde{e}^{\prime} \equiv 0 となってしまいます．
ノイズが全て0のときは，第２回「TLWEとTRLWE」 の折りたたみでも書いたように，簡単に求められてしまいます．
ですから，\tilde{e}^{\prime} の k 個の係数のうち，少なくとも1つは1以上であることが必要です．この状況を考えてみます．
これは，ある 1 \leq j \leq k で \lceil q \cdot e_j \rfloor \geq 1 ，よって，\displaystyle q \cdot e_j \geq \frac{1}{2} が成り立てば良い（＝必要）です．つまり，\displaystyle e_j \geq \frac{1}{2q} となります．
具体例では，ノイズの係数のうち少なくとも１つが \frac{1}{512} \geq 0.0019 であることが必要だとわかりますが，これは e_0 と e_3 でOKです．
以上をまとめると，ノイズの係数（k 個）の範囲は，
任意の 1 \leq i \leq k で \displaystyle e_i < \frac{q - p}{2q} ，かつ，ある 1 \leq j \leq k で \displaystyle e_j \geq \frac{1}{2q} が必要
だとわかりました．
結構シビアなんだなぁと思いました．条件がきつめのランダム？サンプリングなんですね．
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となっています．
trapdoor
公開鍵から秘密鍵を求めるのはNP困難ですが，公開鍵とその情報を組合せると簡単に秘密鍵や平文を求められる，という「その情報」のことを trapdoor と言います．落とし戸，と和訳されます．
gadget行列がLWE問題のtrapdoorとなっていることのチェック
g = (1, 2, \cdots, 2^{\Omega - 1}) \in (\mathbb{Z} / q \mathbb{Z})^{\Omega} とします．それに対応する gadget 行列を G とします．
このとき，s \in \mathbb{B}^n を秘密鍵とします．このとき，十分回数計測して B = G \tilde{s} + E, \ R = (r_1, r_2, \cdots, r_{\Omega n}) \in \mathbb{T}[X]^{\Omega n}, \ \forall i \in [1, k + 1], e_i \overset{\#}{\leftarrow} \mathcal{X}, \ E = (e_1, e_2, \cdots, e_{\Omega n}) なる (B, G) の組が得られたとします．
＊要するに TRLWE 問題で \displaystyle \tilde{r} = \sum_{i = 1}^n \tilde{s}_i \tilde{a}_i + \tilde{e} の部分を十分回数計測すると，(\tilde{r}, \tilde{a}_1, \tilde{a}_2, \cdots, \tilde{a}_n, \tilde{e}) の組が「たくさん」得られます．
＊「十分回数」とは，上記の組からある \Omega n 個の組を取り出すと，その組1つ１つは \tilde{a}_1, \tilde{a}_2, \cdots, \tilde{a}_n を n \Omega \times n 行列の行ベクトルとみなせます．うまくそれら行ベクトルを並べたときに， G と一致する，ぐらいの回数です
そして，G と一致したとき，その行ベクトルの順番で \tilde{r} と \tilde{e} のそれぞれ長さが \Omega n のベクトルが得られて，それらを R と E で置いています．
本題に戻ると，両辺見比べて
\begin{align*}
\begin{pmatrix} \tilde{b}_1 \\ \vdots \\ \tilde{b}_n \\ \tilde{b}_{n + 1} \\ \vdots \\ \tilde{b}_{\Omega n} \end{pmatrix} =
\begin{pmatrix} \begin{pmatrix} 1 \\ 2 \\ \vdots \\ 2^{\Omega - 1} \end{pmatrix} & & \\ & \ddots & \\ & & \begin{pmatrix} 1 \\ 2 \\ \vdots \\ 2^{\Omega - 1} \end{pmatrix} \end{pmatrix}
\begin{pmatrix} \tilde{s}_1 \\ \vdots \\ \tilde{s}_n \end{pmatrix} +
\begin{pmatrix} \tilde{e}_1 \\ \vdots \\ \tilde{e}_n \\ \tilde{e}_{n + 1} \\ \vdots \\ \tilde{e}_{\Omega n} \end{pmatrix}
\end{align*}
という形をしており，
右辺を計算すると，
\begin{align*}
\begin{pmatrix} \tilde{b}_1 \\ \tilde{b}_2 \\ \vdots \\ \tilde{b}_{\Omega} \\ \tilde{b}_{\Omega + 1} \\ \vdots \\ \tilde{b}_{2 \Omega} \\ \tilde{b}_{2 \Omega + 1} \\ \vdots \\ \tilde{b}_{n \Omega} \end{pmatrix} =
\begin{pmatrix} \tilde{s}_1 + \tilde{e}_1 \\ 2 \tilde{s}_1 + \tilde{e}_2 \\ \vdots \\ 2^{\Omega - 1} \tilde{s}_1 + \tilde{e}_{\Omega} \\ \tilde{s}_2 + \tilde{e}_{\Omega + 1} \\ \vdots \\ 2^{\Omega - 1} \tilde{s}_2 + \tilde{e}_{2 \Omega} \\ \tilde{s}_3 + \tilde{e}_{2 \Omega + 1} \\ \vdots \\ 2^{\Omega - 1} \tilde{s}_n + \tilde{e}_{n \Omega} \end{pmatrix}
\end{align*}
となっています．つまり，\forall i \in [1, n] に対して，
\begin{align*}
\begin{pmatrix} \tilde{b}_{(i - 1) \Omega + 1} \\ \tilde{b}_{(i - 1) \Omega + 2} \\ \vdots \\ \tilde{b}_{(i - 1) \Omega + (\Omega - 1)} \end{pmatrix} =
\begin{pmatrix} \tilde{s}_i + \tilde{e}_{(i - 1) \Omega + 1} \\ 2 \tilde{s}_i + \tilde{e}_{(i - 1) \Omega + 2} \\ \vdots \\ 2^{\Omega - 1} \tilde{s}_i + \tilde{e}_{(i - 1) \Omega + (\Omega - 1)} \end{pmatrix}
\end{align*}
です．ノイズの影響は小さいのですので，上記で (\tilde{b}_{(i - 1) \Omega + 1}, \tilde{b}_{(i - 1) \Omega + 2}, \cdots, \tilde{b}_{(i - 1) \Omega +(\Omega - 1)}) の値は仮定からわかるため， \tilde{s}_i が復元できます．
よって，\tilde{s} を求められ，秘密鍵が分かるとLTWE問題は解けるため，示されました
＊参照：第２回「TLWEとTRLWE」
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} になります．
上記の説明
等比数列の和の公式を使います．初項が \frac{1}{4} で公比が \frac{1}{4} の数列の第 n 項は \frac{1}{4^n} です．
第 n 項までの和は \displaystyle \frac{\frac{1}{4} - \frac{1}{4^{n + 1}}}{1 - \frac{1}{4}} になります．ここで，\frac{1}{4^{n + 1}} の部分は n \rightarrow \infty で 0 に収束するため，初項が \frac{1}{4} で公比が \frac{1}{4} の数列の級数（数列の無限和）は収束し，その値は \displaystyle \frac{\frac{1}{4}}{1 - \frac{1}{4}} = \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) とは結局何か，何が「逆行列」っぽいのか
-
d_i の範囲
- 定義での2つ目の条件
g^{-1}(d) とは結局何か，何が「逆行列」っぽいのか
先に結論をかくと，g^{-1}(d) とは，「0以上 q - 1 以下の元を B 進展開したときに現れる係数のベクトル」のことです．
まずは何も考えずに \hat{\mathbb{T}} = q^{-1} \mathbb{Z} / \mathbb{Z} から元を取ります．
このとき，0以上 q - 1 以下と指定しておきます．そうすると，\frac{d}{q} < 1 で都合が良いからです．
有理数上で \frac{d}{q} を \ell bit で B 進展開しようと思うと，
\begin{align*}
\frac{d}{q} \sim d_1 B^{-1} + d_2 B^{-2} + \cdots + d_{\ell} B^{- \ell} = \sum_{i = 1}^{\ell} d_i B^{-i}
\end{align*}
が得られます．\sim は「大体等しい」ぐらいで思ってください．２つ目の条件でどのくらい等しいのかを正当化しています．
すると，両辺に q をかけることで，
\begin{align*}
d \sim q \sum_{i = 1}^{\ell} d_i B^{-i} = \sum_{i = 1}^{\ell} d_i (q B^{-i}) = \sum_{i = 1}^{\ell} d_i (2^{\Omega} (2^{\beta})^{-i}) = \sum_{i = 1}^{\ell} d_i 2^{\Omega - i \beta}
\end{align*}
となります．ここで，最右辺を次の2つのベクトルの内積と見ます．
\begin{align*}
\sum_{i = 1}^{\ell} d_i 2^{\Omega - i \beta} = (d_1, d_2, \cdots, d_{\ell}) \begin{pmatrix} 2^{\Omega - \beta} \\ 2^{\Omega - 2 \beta} \\ \vdots \\ 2^{\Omega - \ell \beta} \end{pmatrix}
\end{align*}
となり，無事に gadget 行列が現れました．
つまり，g^{-1}(d) とは，d を B 進展開したときの係数だとわかります．
g が与えられたときに，g^{-1}(d) があれば d の情報を復元できるのが逆行列っぽいのです．
ちなみにですが，g が与えられていても，d が変われば，g^{-1}(d) も変わります．d を引数に取っているのはそのためです．
これは具体的には，同じ4進展開でも 3 を4進展開したときに現れる係数と，5 を4進展開したときに現れる係数は異なることから分かります．
d_i の範囲
g^{-1}(d) は，B 進展開したときの係数だとわかりました．そこで，定義の「任意の i \in [1, \ell] で \displaystyle d_i \in [- \frac{B}{2}, \frac{B}{2} - 1] \subset \mathbb{Z}」に注目します．
「何も指定をしなければ」 B 進展開するときに出てくる係数は0以上 B - 1 以下です．
しかし，第１回「実数から整数への丸め」 の折り畳みでも触れたように，[- \frac{B}{2}, \frac{B}{2}) 上の整数は，\mathrm{mod} \ B での代表元と一致します．
そして，範囲が対称なので扱いやすいという利点があり，今回の係数は [- \frac{B}{2}, \frac{B}{2} - 1] の範囲です．
定義での2つ目の条件
\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}
についてです．この条件で「B進展開」を指定していて，「近似の精度」にも言及しています．
もしこの条件がなければ，d \neq 0 のときでも g^{-1}(d) = (0, 0, \cdots, 0) は条件を満たしてしまいます．
そもそも「B進展開」とはなんでしょうか．それは，整数 d が与えられたらそれを B で「割って」，その余りをまた B で「割って」，ということを繰り返すアルゴリズムのことです．
であれば，\ell bit 長で，B^{– \ell} までの展開した係数に誤差はなく，B^{– \ell - 1} 以降に現れる係数に問題があることになります．
とすると，それらの係数にある条件を考えることができます．それが定義の２つ目の条件です．
さて，では定義の２つ目の条件はどうやって導かれるかを解説します．
そのときの B 進展開の誤差を考えます．先ほど，\sim でごまかしたところは無限和を考えると，
\displaystyle \begin{align*}
\frac{d}{q} = \sum_{i = 1}^{\infty} d_i B^{-i}
\end{align*}
と直せるので，
\begin{align*}
| g^{-1}(d) g - d | = | q \cdot \sum_{i = 1}^{\ell} d_i B^{-i} - q \cdot \sum_{i = 1}^{\infty} d_i B^{-i} | = q \cdot \left | \sum_{i = \ell + 1}^{\infty} d_i B^{-i} \right |
\end{align*}
となります．
\displaystyle \begin{align*}
& q \cdot \left | \sum_{i = \ell + 1}^{\infty} d_i B^{-i} \right | \\
& \leq q \cdot \sum_{i = \ell + 1}^{\infty} | d_i | B^{-i} \hspace{10pt} \because) \ \mathrm{三角不等式} \\
& \leq q \cdot \sum_{i = \ell + 1}^{\infty} \left( \frac{B}{2} \right) B^{-i} \\
& = q \cdot \frac{B}{2} \sum_{i = \ell + 1}^{\infty} B^{-i} \\
& = q \cdot \frac{B}{2} \frac{B^{- (\ell + 1)}}{1 - B^{-1}} \\
& = \frac{q B}{2} \frac{B^{- \ell}}{B - 1} \\
& = \frac{q}{2 B^{\ell}} \frac{B}{B - 1}
\end{align*}
となり，ぶじに得られました．
上記と同様の議論が \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) = \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方式の概要
詳しいことは 第2.5回の記事「GGSW方式のアルゴリズム」 を参照してください．ざっくりとまとめます．
まず，KeyGenはTFHE方式とほぼ同じなので，割愛します．ただし，平文空間は \mathbb{Z}_N[X] です（この仮定が割とクリティカル）．
一応KeyGenのアルゴリズム
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}_1,\tilde{s}_2, \cdots, \tilde{s}_k) \overset{\#}{\leftarrow} \mathbb{B}_N[X] とする．
平文空間 \tilde{P}_N[X] を \displaystyle \mathbb{Z}_N[X] = \mathbb{Z}[X] / (X^N + 1) と定める．
step3
公開鍵 pk を pk = (k, N, \sigma, p, q) で秘密鍵 sk を sk = \tilde{s} とする．
return (pk, sk)
ここでは，Encrypt のみ紹介します（Decryptは使わないので）（と言っても，第2.5回の記事「GGSW方式のアルゴリズム」 で解説しています）
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}}(\tilde{m}) と書くことにする．
return \tilde{C}
なぜ途中でTFHE方式での0の暗号文を加えるのか，については 今回の「TFHE方式の暗号文とGGSW方式の暗号文の外積」 で解説します．
途中で出てくるベクトルや行列の要素に関して，色々な注意を 第2.5回の記事「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
始めは平文 \tilde{\mu} \in \mathbb{Z}_N[X] の gadget 行列 G へのスカラー倍を考えています．つまり，G の各要素を \tilde{\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 と平文 \tilde{\mu}_1, \tilde{\mu}_2 \in \tilde{P}_N[X] が与えられたとき，\overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}_1) と \overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}_2) の和を考えます．
\begin{align*}
\overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}_1) + \overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}_2) = \overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}_1 + \tilde{\mu}_2)
\end{align*}
を示します．
\displaystyle \begin{align*}
\overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}_1) + \overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\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} + \tilde{\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} + \tilde{\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}) + (\tilde{\mu}_1 + \tilde{\mu}_2) + (\tilde{e}^{\prime}_1 + \tilde{e}^{\prime}_2) \\
& = \overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}_1 + \tilde{\mu}_2)
\end{align*}
ですので，示されました．
もちろん \tilde{\mu}_1 を暗号化する際に出てくるノイズ \tilde{e}^{\prime}_1 と \tilde{\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 と平文 \tilde{\mu}_1, \tilde{\mu}_2 \in \tilde{P}_N[X] と整数 K が与えられたとき，\overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}_1) と K とのスカラーを考えます．
\begin{align*}
K \cdot \overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}) = \overline{\mathrm{TFHE}}_{\tilde{s}}(K \cdot \tilde{\mu})
\end{align*}
を示します．
K \cdot \overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}) とは K \geq 0 であれば \overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}) を K 回足す（\overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}) は足し算できることは直前の 「TFHE方式の暗号文の足し算」 でチェック済み）ということです．
K < 0 であれば，-K > 0 で，- \overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}) を - K 回足す（\overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}) は 単位元を \overline{\mathrm{TFHE}}_{\tilde{s}}(0) とみなした \overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}) の逆元）ということです．
K の正負が変わってもやることは同じです．
K \geq 0 のとき
\begin{align*}
& K \cdot \overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\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 + \tilde{\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 \tilde{\mu} + K \cdot \tilde{e}^{\prime}) \\
& = \overline{\mathrm{TFHE}}_{\tilde{s}}(K \cdot \tilde{\mu})
\end{align*}
ですので，示されました．
もちろん \tilde{\mu} を暗号化する際に出てくるノイズ \tilde{e}^{\prime} について \displaystyle || K \cdot \tilde{e}^{\prime}||_{\infty} < \frac{p}{2q} という仮定を満たす必要があります．
K < 0 のとき
\begin{align*}
& - K \cdot \overline{\mathrm{TFHE}}_{\tilde{s}}(- \tilde{\mu}) \\
& - K \cdot (-\overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\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 + \tilde{\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 \tilde{\mu} + K \cdot \tilde{e}^{\prime}) \\
& = \overline{\mathrm{TFHE}}_{\tilde{s}}((-K) \cdot (- \tilde{\mu}))
\end{align*}
ですので，示されました．
もちろん \tilde{\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 と平文 \tilde{\mu} \in \tilde{P}_N[X] が与えられたとします．このとき，\overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}) に離散化された0ではないノイズ \tilde{e}^{\prime} が加えられているとき，\overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\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 回足す，ということに対応しているためです．
あと，本当は今回扱う4つの Leveled Operations について，数値を踏まえた具体例をやりたかったのですが，手計算は厳しそうなので，諦めました()．
TFHE方式の暗号文とGGSW方式の暗号文の外積
TFHE 方式の暗号文同士の足し算ができるのなら，暗号文の掛け算もできないか，と考えるのは自然な発想だと思います．しかし，これは上手くいきません．
上手くいかない理由
公開鍵 pk = (k, N, \sigma, p, q) と秘密鍵 sk と平文 \tilde{\mu}_1, \tilde{\mu}_2 \in \tilde{P}_N[X] が与えられたとき，\overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}_1) と \overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}_2) の「積」（本当はできないので，「」付き）を考えます．
\overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}_1) = (\tilde{a}_{11}, \tilde{a}_{21}, \cdots, \tilde{a}_{k1}, \tilde{c}_1), \overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}_2) = (\tilde{a}_{12}, \tilde{a}_{22}, \cdots, \tilde{a}_{k2}, \tilde{c}_2) でしたから，これらの「積」は内積と見るのが妥当で，
\begin{align*}
& \overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}_1) \cdot \overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}_2) \\
&= (\tilde{a}_{11}, \tilde{a}_{21}, \cdots, \tilde{a}_{k1}, \tilde{c}_1) \cdot (\tilde{a}_{12}, \tilde{a}_{22}, \cdots, \tilde{a}_{k2}, \tilde{c}_2) \\
&= (\tilde{a}_{11} \tilde{a}_{12}, \tilde{a}_{21} \tilde{a}_{22}, \cdots, \tilde{a}_{k1} \tilde{a}_{k2}, \tilde{c}_{1} \tilde{c}_{2})
\end{align*}
となっていて，
\displaystyle \begin{align*}
\tilde{c}_{1} \tilde{c}_{2}
& = \left( \sum_{i = 1}^{k} \tilde{a}_{1i} \tilde{s}_i + \tilde{\mu}_1 + \tilde{e}^{\prime}_1 \right) \times \left( \sum_{i = 1}^{k} \tilde{a}_{2i} \tilde{s}_i + \tilde{\mu}_2 + \tilde{e}^{\prime}_2 \right) \\
& = \sum_{i = 1}^{k} \tilde{a}_{1i} \tilde{s}_i \sum_{i = 1}^{k} \tilde{a}_{2i} \tilde{s}_i + \sum_{i = 1}^{k} \tilde{a}_{2i} \tilde{s}_i \tilde{\mu}_1 + \sum_{i = 1}^{k} \tilde{a}_{1i} \tilde{s}_i \tilde{\mu}_2 + \tilde{\mu}_1 \tilde{\mu}_2 \\
& + \left( \sum_{i = 1}^{k} \tilde{a}_{2i} \tilde{s}_i + \tilde{\mu}_2 \right) \tilde{e}^{\prime}_1 + \left( \sum_{i = 1}^{k} \tilde{a}_{1i} \tilde{s}_i + \tilde{\mu}_1 \right) \tilde{e}^{\prime}_2 + \tilde{e}^{\prime}_1 \tilde{e}^{\prime}_2
\end{align*}
と計算できますが，これは明らかに \tilde{\mu}_1 \tilde{\mu}_2 を暗号化したものではありません．っていうかノイズやばそう()．
でも「掛け算っぽい」ことならできます．それが今回紹介するTFHE方式の暗号文とGGSW方式の暗号文の外積です．
やりたいこととしては，平文 \tilde{\mu} \in \tilde{P}[X] を TFHE 方式で暗号化した暗号文 \tilde{c} と 平文 \tilde{m} \in \mathbb{Z}[X] を GGSW 方式で暗号化した暗号文 \tilde{c}^{\prime} との「掛け算っぽい」ものを考えて，その暗号文は \tilde{\mu} \tilde{m} \in \tilde{P}[X] を TFHE 方式で暗号化した暗号文に相当する，というイメージです．
手法としては，第2.5回「GGSW方式の暗号文同士での内積」 での gadget decomposition を使って，暗号文を整数係数のベクトルに「引き戻す」ことを行います．
ちなみに「あれ？Torusの掛け算って考えないんじゃなかったっけ？Torusの暗号文は掛け算できるの？」と思うかもしれませんが，\mathbb{T} を \hat{\mathbb{Z}} = \mathbb{Z} / q \mathbb{Z} に離散化していることを思い出してください．
参照：第２回「hatについて」
「Torus を \mathbb{Z} / q \mathbb{Z} で離散化して，しかも掛け算を考えるなら，始めからわざわざ Torus なんて考える必要なかったんじゃない？」と思う方もいらっしゃるかもしれません．安心してください．僕もそう思っています．
Torus という言葉を使いたかっただけ，まである
\underline{\mathrm{Def(external \ product)}}
GGSW方式のKeyGenを行い，その出力を (pk = (k, N, \sigma, p, q), sk) とする．
また，GGSW方式での平文として \tilde{m}_1 \in \mathbb{Z}_N[X] を取り，\tilde{c}_1 = \overline{\mathrm{GGSW}}_{\tilde{s}}(\tilde{m}_1) とする．また，\tilde{\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} + \tilde{m}_1 G) \\
& = G^{-1}(\tilde{c}_2) \tilde{X} + G^{-1}(\tilde{c}_2) \tilde{m}_1 G \\
& = G^{-1}(\tilde{c}_2) \tilde{X} + \tilde{m}_1 G^{-1}(\tilde{c}_2) G \\
& \sim \tilde{m}_1 \tilde{c}_2
\end{align*}
となっています．
上記の式変形のフォロー
最後の式変形についてです．
まず，G^{-1}(\tilde{c}_2) \tilde{X} に関しては，\tilde{X} は TFHE 方式で0を暗号化したものなので，TFHE 方式の観点で見るとここは0とみなせます．
次に，\tilde{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 と考えられます．
また，\tilde{m}_1 \in \mathbb{Z}_N[X] なので，\tilde{\mu}_2 へのスカラーと見ることができます．よって，\tilde{m}_1 \tilde{c}_2 = \tilde{m}_1 \overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}_2) = \overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{m}_1 \tilde{\mu}_2) が成り立ちます．
まとめると，\tilde{c}_1 \boxdot \tilde{c}_2 は \tilde{m}_1 \tilde{\mu}_2 を TFHE 方式で暗号化したものになっている，ということです．
これを見ると色々とわかることがあります．
とその前に，gadget decomposition について，重要なイメージを再掲します．
多項式の組に作用させても，整数の組が返ってくる，というのがめちゃくちゃ扱いやすいのです
-
gadget decomposition はどう使われるのか
→\tilde{c}_1 = \tilde{X} + \tilde{m}_1 G を TFHE 方式の観点から見ると，\tilde{X} はほぼ無視できる．そこで，\tilde{c}_2 の情報込みで，\tilde{m}_1 G の G を消そうと思うと，自然と gadget decomposition が考えられる．
-
なぜ gadget 行列を使うのか
→gadget decomposition 的なことをできる行列であれば，なんでも良い．たぶん他にもある．
-
GGSW 方式で TFHE 方式で0の暗号文を加えるのはなぜか
→\tilde{c}_1 = \tilde{X} + \tilde{m}_1 G で \tilde{X} を加えないとほぼ平文状態なので，すぐに破られるため．ただ，考え方としては，\tilde{c}_1 = (ノイズ) + \tilde{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) とする．また，\tilde{\mu}_0, \tilde{\mu}_1 \in \tilde{P}_N[X] を TFHE 方式での平文として，\tilde{c}_0 = \overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}_0), \ \tilde{c}_1 = \overline{\mathrm{TFHE}}_{\tilde{s}}(\tilde{\mu}_1) とする．
このとき，b, \tilde{c}, \tilde{c}_0, \tilde{c}_1 をインプットとして，\tilde{c}^{\prime} = \tilde{c} \boxdot (\tilde{c}_1 - \tilde{c}_0) + \tilde{c}_0 を出力する．これを \mathrm{CMux}(b, \tilde{c}, \tilde{c}_0, \tilde{c}_1) と書く．
厳密には \tilde{c} は b の情報も含んでいますが，最終的なインプットとして必要なので，上記では付け加えています（論文では省かれていますが）．
b = 0 のとき，\mathrm{CMux}(0, \tilde{c}, \tilde{c}_0, \tilde{c}_1) = \tilde{c}_0 であり，b = 1 のとき，\mathrm{CMux}(1, \tilde{c}, \tilde{c}_0, \tilde{c}_1) = \tilde{c}_1 です．これを確認してみましょう．
上記の確認
b = 0，つまり，\tilde{c} = \overline{\mathrm{GGSW}}_{\tilde{s}}(0) のとき
\begin{align*}
\tilde{c} \boxdot (\tilde{c}_1 - \tilde{c}_0) + \tilde{c}_0
& = \overline{\mathrm{GGSW}}_{\tilde{s}}(0) \boxdot (\tilde{c}_1 - \tilde{c}_0) + \tilde{c}_0 \\
& = G^{-1}(\tilde{c}_1 - \tilde{c}_0) (\tilde{X} + 0 \cdot G) + \tilde{c}_0 \\
& = G^{-1}(\tilde{c}_1 - \tilde{c}_0) \tilde{X} + 0 \cdot G G^{-1}(\tilde{c}_1 - \tilde{c}_0) + \tilde{c}_0
\end{align*}
となり，最後の行は G^{-1}(\tilde{c}_1 - \tilde{c}_0) \tilde{X} を \tilde{X} は0を暗号化したベクトルで，0 \cdot G G^{-1}(\tilde{c}_1 - \tilde{c}_0) もほぼ0と考えられるので，上記の式は \tilde{c}_0 が出力されます．
b = 1，つまり，\tilde{c} = \tilde{c}_1 のとき
\begin{align*}
\tilde{c} \boxdot (\tilde{c}_1 - \tilde{c}_0) + \tilde{c}_0
& = \overline{\mathrm{GGSW}}_{\tilde{s}}(1) \boxdot (\tilde{c}_1 - \tilde{c}_0) + \tilde{c}_0 \\
& = G^{-1}(\tilde{c}_1 - \tilde{c}_0) (\tilde{X} + 1 \cdot G) + \tilde{c}_0 \\
& = G^{-1}(\tilde{c}_1 - \tilde{c}_0) \tilde{X} + 1 \cdot G G^{-1}(\tilde{c}_1 - \tilde{c}_0) + \tilde{c}_0
\end{align*}
となり，最後の行は G^{-1}(\tilde{c}_1 - \tilde{c}_0) \tilde{X} を \tilde{X} は0を暗号化したベクトルで，0 \cdot G G^{-1}(\tilde{c}_1 - \tilde{c}_0) もほぼ1と考えられるので，上記の式は (\tilde{c}_1 - \tilde{c}_0) + \tilde{c}_0 = \tilde{c}_1 が出力されます．
以上より示されました．
3.3の議論の考察
ここでは本文の議論をもう１歩踏み込んだ考察をします．踏み込み方は人それぞれだと思うので，興味のない方は飛ばしてくださって構いません．
第2.5回「これまでの議論の考察１」 では，gadget 行列が「疎」であることや， subroutine で呼び出す際の計算量について考察しました．
ここでは，もう少し根本的な問題として，gadget decomposition ってどのくらいのノイズが出てくるの？ということを考えます．
gadget decomposition とは，振り返ってみると，「実数を \ell bit で B 進展開した際に現れる係数」のことでした．そして，\ell + 1 bit 以降で誤差が現れる，そして，その誤差は大きくても \displaystyle \frac{B}{B - 1} 2^{\Omega - \beta \ell - 1} ということを 今回の「gadget decomposition」 で解説しました．
\displaystyle \frac{B}{B - 1} の部分は B が大きいほど（＝\beta が大きいほど）無視できます．
ちなみに \beta が小さいほど，\displaystyle \frac{B}{B - 1} と 2^{\Omega - \beta \ell - 1} の部分は大きく，\beta が大きいほど，\displaystyle \frac{B}{B - 1} と 2^{\Omega - \beta \ell - 1} の部分は小さくなるので，\displaystyle \frac{B}{B - 1} 2^{\Omega - \beta \ell - 1} の部分は，単調減少であると言えます．
＊このことは，\beta （＝B）が大きいほど，B 進展開で表せる数が大きくなり，誤差は小さくできることから直感的に理解できます
誤差と言えば，第２回「3.1の議論」 において，平文が格納できるノイズのサイズというのを考察しました．このことが，今回の「TFHE方式のアルゴリズムの正当性」 での許容できるノイズに繋がるのでした．
ここに出てくる \displaystyle \frac{q}{2p} = 2^{\Omega - (\bar{w} + w) - 1} というのは，上記に出てくる 2^{\Omega - \beta \ell - 1} と非常に形がよく似ています．これは偶然なのでしょうか．
結論から書くと，直接関係はないが，同じようなものとして考えられる，ということです．
先頭 \bar{w} + w bit が本質的な情報で，\bar{w} + w bit の整数を考えることは，\ell bit の B 進展開，つまり，\beta \ell bit の整数を考えるのは，考え方としてほとんど同じだからです．
ただ，ノイズに触れておくと，\displaystyle \frac{q}{2p} = 2^{\Omega - (\bar{w} + w) - 1} の方は，例えば，暗号文の足し算をするたびに増えますが，gadget decomposition の誤差は gadget decomposition を行うたびに増える，というものではありません．
他の考察と比べるとちょっと軽いですが，今までの内容が重いですし，後できになることができたら，サイレント修正しようと思います．
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！
Discussion