今回の記事は下記の記事からの続きとなります．
原著論文：プログラマブルブートストラップの原著論文
第１回：第１回
第２回：第２回
プログラマブルブートストラップの原著論文の第２〜４章を厳密に考察します．
全体を通して使う記号や前提知識などは第１回目の記事にまとめています．
本論文全体の流れ
全体の前提知識と参考文献
この連載を読みやすくリメイクした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の議論の考察
今回は第2.5回目です．
具体的な内容としては，次のようになります:
- なぜ番外編が必要なのか
- 今回出てくる予備知識のまとめ
- GGSW方式とは
- 無限ノルム
- Tensor積
- gadget行列
- gadget decomposition
- GGSW方式のアルゴリズム
- GGSW方式のアルゴリズムの具体例
- これまでの議論の考察１
- GGSW方式の暗号文の足し算
- GGSW方式の暗号文同士の内積
- これまでの議論の考察２
なぜ急に番外編が出てきたのか，それも含めて早速内容の方に入っていきます．
なぜ番外編が必要なのか
第３回では，第１回と第２回で扱ってきたTFHE方式とは別のGGSW方式での暗号文を考えます．
始めは第３回の記事だけで扱おうと思い，折りたたみで下記の内容を書いていたのですが，
あまりにも分量が多く，可読性が低い判断したため，急遽番外編を作成することにしました．
本記事では，GGSW方式の解説に注力し，TFHE方式との暗号文との関連は（External product）については解説しません（そちらは第３回を参照してください）
今回出てくる予備知識のまとめ
前提知識以外の数学的な予備知識は適宜まとめてはいますが，一覧がほしい方もいらっしゃるかもなので，先にまとめます．折りたたみで出てくる概念のみを対象で，本文中に出てくるものは目次を参考にしてください．
順番は今回の記事で出てくる順で，内容は定義だけざっと並べています．
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*}
GGSW方式とは何か
GSW方式は，下記の論文で提唱された「通常の」LWE仮定に基づく暗号化の方式で，著者の頭文字を取っています．
Gentry, C., Sahai, A., Waters, B.:
Homomorphic encryption from learning with errors: Conceptually-simpler,asymptotically-faster, attribute-based.
In: Advances in Cryptology – CRYPTO 2013, Part I. Lecture Notes in Computer Science, vol. 8042, pp. 75–92. Springer (2013)
上記では「通常の」LWE仮定で定義されているため，Torus上の多項式環へ拡張した方式をGGSW方式といいます．
＊論文では，GGSW方式になっていますこれもあまりにもセンスがないため，本当はTRGSW方式に変更したいですが，影響箇所が多そうで断念しました
今回は，上記の論文を解説するのではなく，
上記をまとめて，TRLWE問題へリメイクしたものを解説することで プログラマブルブートストラップの原論文 で使われる GGSW 方式の解説とします．
がっつりやろうとすると，それだけでまた何本も記事が必要になってしまいますし，プログラマブルブートストラップの原論文 を理解する目的がぼやけてしまうので・・・．
＊原論文や「聖書」縫田 光司，『耐量子計算機暗号』，森北出版，2020年 では，BitDecomp という関数を用いて理論を展開していますが，いつかGSW方式の理論を理解する記事を出しますので，それまでお待ちください
無限ノルム
ノルムとはベクトルの大きさを与えるものです．「大きさ」とは，そのベクトルと原点（零ベクトル）がどのくらい離れているか，を表し，ノルムによってその空間内に距離を与えることができます．
ノルムには色々な与え方があり，今回は無限ノルムを参照しています．無限ノルムは，直感的には「各成分の絶対値で一番大きいもの」です．
有限次元ベクトルの無限ノルムは次のように定義されます．
\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 です．
論文中では，多項式をベクトルと見ることで無限ノルムを使っています．
Tensor積
もちろん行列に関する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方式のアルゴリズム
\underline{\mathrm{Def(GGSWの暗号化アルゴリズム)}}
以下の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}_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(\mu, pk) \mapsto \tilde{C}
KeyGenで定義された平文空間から \tilde{m} \in \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}
Decrypt(\tilde{C}, sk) \mapsto \mu
暗号文 \tilde{C} と秘密鍵 \tilde{s} を入力とする．
step1
\tilde{C} = \tilde{X} + \mu G に対して，左から (2^{\beta}, 2^{2 \beta}, \cdots, 2^{\ell \beta}) \in \hat{\mathbb{Z}}_N[X]^{\ell} を k + 1 回繰り返したベクトル R = (2^{\beta}, 2^{2 \beta}, \cdots, 2^{\ell \beta}, 2^{\beta}, 2^{2 \beta}, \cdots, 2^{\ell \beta}, \cdots, 2^{\beta}, 2^{2 \beta}, \cdots, 2^{\ell \beta}) \in \hat{\mathbb{Z}}_N[X]^{\ell(k + 1)} を両辺に左から掛ける．
\tilde{RC} = R \cdot \tilde{C} と置く．
step2
\tilde{RC} = R \tilde{X} + R \mu G であり，RG = (\ell, \ell, \cdots, \ell) = \ell(1, 1, \cdots, 1) \in \hat{\mathbb{Z}}_N[X]^{k + 1} である．
また，R \tilde{X} = (\tilde{a}_{t1}, \tilde{a}_{t2}, \cdots, \tilde{a}_{tk}, \tilde{c}_t) とする．このとき，
\begin{align*}
& \sum_{i = 1}^{k} \tilde{rc}_i \tilde{s}_i - \tilde{rc}_{k + 1} \\
& = \sum_{i = 1}^{k} (\tilde{a}_{t1} + \ell \mu) \tilde{s}_i - (\tilde{c}_t + \ell \mu) \\
& = (\sum_{i = 1}^{k} \tilde{a}_{t1} \tilde{s}_i - \tilde{c}_t) + \ell (\sum_{i = 1}^k \tilde{s}_i - 1) \mu
\end{align*}
であり，秘密鍵 \tilde{s} を仮定すると， \sum_{i = 1}^{k} \tilde{rc}_i \tilde{s}_i - \tilde{rc}_{k + 1}, \ \ell, (\sum_{i = 1}^k \tilde{s}_i - 1) を全て計算することで，よって，\mu を復元できる．
return \mu
めちゃくちゃややこしいと思うので，アルゴリズムごとに補足します．後，Decrypt は保証できません()．
なぜ途中でTFHE方式での0の暗号文を加えるのか，については 第３回の「TFHE方式の暗号文とGGSW方式の暗号文の外積」 で解説します．
KeyGen
基本的にTFHEと同じです．と言っても，時系列的にはこちらが先なので，一応補足します．
パラメタに必要なのは，第２回「3.1の議論」 で出てきたものたちです．
ただし，そのとき（TFHEもそう）と違って，平文空間は \mathbb{Z}_N[X] で良いことに注意してください．\hat{\mathbb{Z}}_N[X] ではありません．
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} との和で暗号文とします．
Decrypt
イメージとしては「\tilde{X} は所詮0の暗号文だからどうにでもなるので，\tilde{C} = \tilde{X} + \mu G から \mu を求めるには，どうにかして G を消したい，と考えます．
そのとき，R という長さが \ell(k + 1) のベクトルを考えます．Encrypt と同じように各要素は q = 2^{\Omega} 以下なので，\hat{\mathbb{Z}} の要素と見ることができます．
RG というベクトルと行列の「内積」を考えると，step2 の１行目になります．
一方で，R \tilde{X} はどうなっているでしょうか．例えば，\tilde{X} の1行目の部分だけを抜き出すと，
\begin{align*}
(2^{\Omega - \beta} \tilde{a}_{1,1}, 2^{\Omega - \beta} \tilde{a}_{1,2}, \cdots, 2^{\Omega - \beta} \tilde{a}_{1,k}, 2^{\Omega - \beta} \tilde{c}_1)
\end{align*}
となっていて，
\displaystyle \begin{align*}
\tilde{c}_1 = \sum_{i = 1}^k \tilde{a_{1,i}} \tilde{s}_i + \tilde{e}_1^{\prime}
\end{align*}
という式に対して，両辺に 2^{\Omega - \beta} をかけることで，
\displaystyle \begin{align*}
2^{\Omega - \beta} \cdot \tilde{c}_1 = \sum_{i = 1}^k (2^{\Omega - \beta} \cdot \tilde{a_{1,i}}) \tilde{s}_i + 2^{\Omega - \beta} \cdot \tilde{e}_1^{\prime}
\end{align*}
が成り立ちます．念のためですが「\cdot」はスカラー倍です．
上記の式は先ほど抜き出した１行目から再現でき，「ノイズを無視できる仮定のもとで」
\displaystyle \begin{align*}
2^{\Omega - \beta} \cdot \tilde{c}_1 - \sum_{i = 1}^k (2^{\Omega - \beta} \cdot \tilde{a_{1,i}}) \tilde{s}_i = 0
\end{align*}
と考えられます．つまり，秘密鍵 \tilde{s} を持っていたら，１行目の要素を使って，0に持っていけることを表します．これは他の行でも同様です．
すると，step2 で書いた \displaystyle (\sum_{i = 1}^{k} \tilde{a}_{t1} \tilde{s}_i - \tilde{c}_t) のように，\tilde{X} の部分を0に変換できることから，秘密鍵と平文という2つが組合さった情報を取り出すことができ，無事に復号できます．
Decryptが確証持てないので，早急に調べると共に，このアルゴリズムの正当性（任意の平文 \mu \in \tilde{P}_N[X] に対して，\mathrm{Decrypt}(sk, \mathrm{Encrypt}(pk, \mu)) = \mu）は省略します・・・（というか普通暗号化扱うなら復号も扱うよな・・・）
のちにしれっとサイレント修正とサイレント立項をしているかもしれません()
GGSW方式のアルゴリズムの具体例
第２回「3.1の議論」 でのパラメタを用いて，上記の具体例を与えます．もちろんEncryptまでです．
前回のパラメタは，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] = \mathbb{Z}[X] / (X^N + 1) = \mathbb{Z}[X] / (X^4 + 1) で， \mu = 90 + 311X + 77X^2 + 140X^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) とします．
上記は平文以外，第３回「TFHE方式のアルゴリズムの具体例」 と同じ設定にしています．
Encrypt step1
\ell = 3, \ \beta = 2 として， g = (2^{\Omega - \beta}, 2^{\Omega - 2 \beta}, \cdots, 2^{\Omega - \ell \beta}) = (2^6, 2^4, 2^2) とします．すると，gadget 行列 G は，
\begin{align*}
G &= I_{k + 1} \otimes g = I_{3} \otimes g \\
&= \begin{pmatrix}
2^6 & 0 & 0 \\
2^4 & 0 & 0 \\
2^2 & 0 & 0 \\
0 & 2^6 & 0 \\
0 & 2^4 & 0 \\
0 & 2^2 & 0 \\
0 & 0 & 2^6 \\
0 & 0 & 2^4 \\
0 & 0 & 2^2 \\
\end{pmatrix}
\end{align*}
です．
Encrypt step2
subroutine を使って，\overline{TFHE}_{\tilde{s}}(0) を求める操作を (k + 1) \ell = 3 \cdot 3 = 9 回行います．
しかし，第３回「TFHE方式のアルゴリズムの具体例」 でも触れていますが，計算がめちゃくちゃめんどくさいので，今回は \tilde{a}_0, \tilde{a}_1 の値を固定します．
つまり，(\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 ですので，
\displaystyle \begin{align*}
& \sum_{i = 1}^2 \tilde{a}_i \tilde{s}_i \\
& = (1 + X^2)(120 + 33X + 9X^2 + 82X^3) + (X + X^2 + X^3)(155 + 13X + 203X^2 + 95X^3) \\
& = 184 + 56 X + 136 X^2 + 230 X^3
\end{align*}
までの値を固定します．
\tilde{e}^{\prime} は次数が高々3の多項式で係数は 0, 1 のいずれかしか取らないので，ここの値を変えます．
以上を仮定して，\tilde{X} として，例えば，次の値を考えることができます．
\displaystyle \begin{align*}
\tilde{X} &= \begin{pmatrix}
(\overline{TFHE}_{\tilde{s}}(0)_1)^T \\
(\overline{TFHE}_{\tilde{s}}(0)_2)^T \\
(\overline{TFHE}_{\tilde{s}}(0)_3)^T \\
(\overline{TFHE}_{\tilde{s}}(0)_4)^T \\
(\overline{TFHE}_{\tilde{s}}(0)_5)^T \\
(\overline{TFHE}_{\tilde{s}}(0)_6)^T \\
(\overline{TFHE}_{\tilde{s}}(0)_7)^T \\
(\overline{TFHE}_{\tilde{s}}(0)_8)^T \\
(\overline{TFHE}_{\tilde{s}}(0)_9)^T \\
\end{pmatrix} \\
&= \begin{pmatrix}
(120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 185 + 56 X + 137 X^2 + 231 X^3)^T \\
(120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 185 + 57 X + 136 X^2 + 231 X^3)^T \\
(120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 184 + 56 X + 136 X^2 + 230 X^3)^T \\
(120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 184 + 56 X + 137 X^2 + 230 X^3)^T \\
(120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 185 + 56 X + 136 X^2 + 231 X^3)^T \\
(120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 184 + 57 X + 137 X^2 + 231 X^3)^T \\
(120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 184 + 57 X + 136 X^2 + 231 X^3)^T \\
(120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 184 + 57 X + 136 X^2 + 230 X^3)^T \\
(120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 185 + 56 X + 136 X^2 + 230 X^3)^T \\
\end{pmatrix}
\end{align*}
Encrypt step3
G への \mu = 90 + 311X + 77X^2 + 140X^3 \in \mathbb{Z}_N[X] のスカラー倍を考えます．係数は \hat{\mathbb{Z}} = \mathbb{Z} / 256 \mathbb{Z} です．
\displaystyle \begin{align*}
\mu G & = (90 + 311X + 77X^2 + 140X^3)
\begin{pmatrix}
2^6 & 0 & 0 \\
2^4 & 0 & 0 \\
2^2 & 0 & 0 \\
0 & 2^6 & 0 \\
0 & 2^4 & 0 \\
0 & 2^2 & 0 \\
0 & 0 & 2^6 \\
0 & 0 & 2^4 \\
0 & 0 & 2^2 \\
\end{pmatrix} \\
& = \begin{pmatrix}
128 + 192 X + 64 X^2 & 0 & 0 \\
160 + 112 X + 208 X^2 + 192 X^3 & 0 & 0 \\
104 + 220 X + 52 X^2 + 48 X^3 & 0 & 0 \\
0 & 128 + 192 X + 64 X^2 & 0 \\
0 & 160 + 112 X + 208 X^2 + 192 X^3 & 0 \\
0 & 104 + 220 X + 52 X^2 + 48 X^3 & 0 \\
0 & 0 & 128 + 192 X + 64 X^2 \\
0 & 0 & 160 + 112 X + 208 X^2 + 192 X^3 \\
0 & 0 & 104 + 220 X + 52 X^2 + 48 X^3 \\
\end{pmatrix} \\
\end{align*}
以上から，\tilde{C} = \tilde{X} + \mu G は次のように求められます:
\begin{align*}
& \begin{pmatrix}
(120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 185 + 56 X + 137 X^2 + 231 X^3)^T \\
(120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 185 + 57 X + 136 X^2 + 231 X^3)^T \\
(120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 184 + 56 X + 136 X^2 + 230 X^3)^T \\
(120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 184 + 56 X + 137 X^2 + 230 X^3)^T \\
(120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 185 + 56 X + 136 X^2 + 231 X^3)^T \\
(120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 184 + 57 X + 137 X^2 + 231 X^3)^T \\
(120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 184 + 57 X + 136 X^2 + 231 X^3)^T \\
(120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 184 + 57 X + 136 X^2 + 230 X^3)^T \\
(120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 185 + 56 X + 136 X^2 + 230 X^3)^T \\
\end{pmatrix} \\
& +
\begin{pmatrix}
128 + 192 X + 64 X^2 & 0 & 0 \\
160 + 112 X + 208 X^2 + 192 X^3 & 0 & 0 \\
104 + 220 X + 52 X^2 + 48 X^3 & 0 & 0 \\
0 & 128 + 192 X + 64 X^2 & 0 \\
0 & 160 + 112 X + 208 X^2 + 192 X^3 & 0 \\
0 & 104 + 220 X + 52 X^2 + 48 X^3 & 0 \\
0 & 0 & 128 + 192 X + 64 X^2 \\
0 & 0 & 160 + 112 X + 208 X^2 + 192 X^3 \\
0 & 0 & 104 + 220 X + 52 X^2 + 48 X^3 \\
\end{pmatrix} \\
& = \begin{pmatrix}
248 + 225X + 73X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 185 + 56 X + 137 X^2 + 231 X^3 \\
24 + 145X + 217X^2 + 18X^3, 155 + 13X + 203X^2 + 95X^3, 185 + 57 X + 136 X^2 + 231 X^3 \\
224 + 253X + 61X^2 + 130X^3, 155 + 13X + 203X^2 + 95X^3, 184 + 56 X + 136 X^2 + 230 X^3 \\
120 + 33X + 9X^2 + 82X^3, 17 + 205X + 11X^2 + 95X^3, 184 + 56 X + 137 X^2 + 230 X^3 \\
120 + 33X + 9X^2 + 82X^3, 59 + 125X + 155X^2 + 31X^3, 185 + 56 X + 136 X^2 + 231 X^3 \\
120 + 33X + 9X^2 + 82X^3, 3 + 233X + 255X^2 + 143X^3, 184 + 57 X + 137 X^2 + 231 X^3 \\
120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 56 + 249 X + 200 X^2 + 231 X^3 \\
120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 88 + 169 X + 88 X^2 + 166 X^3 \\
120 + 33X + 9X^2 + 82X^3, 155 + 13X + 203X^2 + 95X^3, 33 + 20 X + 188 X^2 + 22 X^3 \\
\end{pmatrix}
\end{align*}
一生分の計算をしましたね・・・（検算はむり）．
これまでの議論の考察１
ここでは本文の議論をもう１歩踏み込んだ考察をします．踏み込み方は人それぞれだと思うので，興味のない方は飛ばしてくださって構いません．
gadget 行列が「疎」っぽいなって思いました．要するに各行で非零要素が１つしかなくて，残りの k 個は要素が 0 なわけです．
こういう疎（sparse）な行列は僕が専門の符号理論ではちょくちょく出てきて，LDPC符号なんかがあったりします．向こうは各行の非零要素が O(1) ですが．
そういう意味で，作り方も作為的ですし，他にもっと面白い性質があるんじゃないかなって思っています．
ただその行列の組合せ論的な性質を調べるならまだしも，単純にスカラー倍でマスクを取っているのは，ちょっと行列のサイズの無駄遣いなんじゃない？という感覚はあります．要するに大きすぎってことです．
それに伴って，TFHE で0を暗号化するサブルーチンも (k + 1) \ell 回行わないといけないのも気になります．
サブルーチンでは演算回数が O(k) で，それぞれの bit 長が N なので，トータルの計算量は O(k N) です．そのサブルーチンを (k + 1) \ell 回行うとなると，\ell は plaintext の bit 長である \Omega に比例しますので，O(k^2 \Omega n) です．
ここで2乗が出てくるのが気にかかるポイントです．k とは，秘密鍵のサイズ（ほぼ暗号文のサイズ）のことでしたので，ここを増やせば増やすほど，ここのサブルーチン処理に時間がかかることになります．
個人的にはここを \ell 回とかに抑えられたら，もう少し（っていうかかなり）効率が良くなるんじゃないかなって思っています．
上記の例でもちょっと手頃な例を考えようかなって感じだったのに，(9, 3) 型行列で各要素は次数が3の多項式ですからね・・・ちょっと行列のサイズが大きすぎなのではっていう簡単な感想でした．
GGSW方式の暗号文の足し算
公開鍵 pk = (k, N, \sigma, p, q) と秘密鍵 sk と平文 \mu_1, \mu_2 \in \mathbb{Z}_N[X] が与えられたとき，\overline{\mathrm{GGSW}}_{\tilde{s}}(\mu_1) と \overline{\mathrm{GGSW}}_{\tilde{s}}(\mu_2) の和を考えます．
\begin{align*}
\overline{\mathrm{GGSW}}_{\tilde{s}}(\mu_1) + \overline{\mathrm{GGSW}}_{\tilde{s}}(\mu_2) = \overline{\mathrm{GGSW}}_{\tilde{s}}(\mu_1 + \mu_2)
\end{align*}
を示します．
\begin{align*}
\overline{\mathrm{GGSW}}_{\tilde{s}}(\mu_1) = \tilde{X} + \mu_1 G
\end{align*}
でしたから，
\begin{align*}
& \overline{\mathrm{GGSW}}_{\tilde{s}}(\mu_1) + \overline{\mathrm{GGSW}}_{\tilde{s}}(\mu_2) \\
& = (\tilde{X} + \mu_1 G) + \tilde{X}^{\prime} + \mu_2 G \\
& = \left( \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} + \mu_1 G \right) + \left( \begin{pmatrix}(\overline{TFHE}_{\tilde{s}}(0)_1^{\prime})^T \\ (\overline{TFHE}_{\tilde{s}}(0)_2^{\prime})^T \\ \vdots \\ (\overline{TFHE}_{\tilde{s}}(0)_{(k + 1)\ell}^{\prime})^T) \end{pmatrix} + \mu_2 G \right) \\
& = \begin{pmatrix}(\overline{TFHE}_{\tilde{s}}(0)_1 + (\overline{TFHE}_{\tilde{s}}(0)_1^{\prime})^T \\ (\overline{TFHE}_{\tilde{s}}(0)_2 + (\overline{TFHE}_{\tilde{s}}(0)_2^{\prime})^T \\ \vdots \\ (\overline{TFHE}_{\tilde{s}}(0)_{(k + 1)\ell} + \overline{TFHE}_{\tilde{s}}(0)_{(k + 1)\ell}^{\prime})^T) \end{pmatrix} + (\mu_1 + \mu_2) G \\
& = \begin{pmatrix}((\overline{TFHE}_{\tilde{s}}(0)_1^{\prime \prime})^T \\ (\overline{TFHE}_{\tilde{s}}(0)_2^{\prime \prime})^T \\ \vdots \\ (\overline{TFHE}_{\tilde{s}}(0)_{(k + 1)\ell}^{\prime \prime})^T) \end{pmatrix} + (\mu_1 + \mu_2) G
\end{align*}
となり，示されました．
最後の等号は，TFHE方式の暗号文が和で閉じているため，結局平文同士の足し算を暗号化すればよいことを使っています．
今は平文が0のときを考えているので，0と0の和は0であることから，上記のようにまとめられます．
GGSW方式の暗号文同士の内積
上記でも考えましたが，\overline{\mathrm{GGSW}}_{\tilde{s}}(\mu) \in \hat{\mathbb{Z}}_N[X]^{(k + 1) \ell \times (k + 1)} ですので，このままでは暗号文同士の掛け算はできません（行列のサイズが異なるので）．
では，片方で転置を取れば解決するか，と聞かれたらそういうわけにもいきません．
そもそも転置を取って計算した後にできる行列は \hat{\mathbb{Z}}_N[X]^{(k + 1) \ell \times (k + 1) \ell} か \hat{\mathbb{Z}}_N[X]^{(k + 1) \times (k + 1)} の型になっているからです．
そこで，gadget decomposition を使います．一方の暗号文を整数の話に「戻す」ことで，「暗号文の掛け算」を「暗号文へのスカラー倍」で置き換えることで解決します．
\underline{\mathrm{Def(GGSWの \ inner \ product)}}
GGSW 方式の平文 \mu_1, \mu_2 \in \mathbb{Z}[X] を取って，それぞれの暗号文 \tilde{C}_0 = \overline{\mathrm{GGSW}}_{\tilde{s}}(\mu_1) , \tilde{C}_1 = \overline{\mathrm{GGSW}}_{\tilde{s}}(\mu_2) \in \mathbb{Z}[X]^{(k + 1) \ell \times (k + 1)} を考える．
\tilde{C}_1 の i \ (1 \leq i \leq (k + 1)\ell) 番目の行ベクトル \tilde{C}_{1, i} に対して，その gadget decomposition G^{-1}(\tilde{C}_{1, i}) = (g^{-1}(\tilde{C}_{1, i, 1}), g^{-1}(\tilde{C}_{1, i, 2}), \cdots, g^{-1}(\tilde{C}_{1, i, (k + 1)\ell})) \in \mathbb{Z}_N[X]^{(k + 1) \ell} を考える．ただし，1 \leq j \leq (k + 1) \ell で \tilde{C}_{1, i, j} でベクトル \tilde{C}_{1, i} の j 番目の要素を表すことにする．
\tilde{C}_0 と \tilde{C}_1 の inner product \tilde{C}_0 \boxtimes \tilde{C}_1 は次のように定義される:
\displaystyle \begin{align*}
\tilde{C}_0 \boxtimes \tilde{C}_1 = \begin{pmatrix} \tilde{C}_0 \boxtimes \tilde{C}_{1, 1} \\ \tilde{C}_0 \boxtimes \tilde{C}_{1, 2} \\ \vdots \\ \tilde{C}_0 \boxtimes \tilde{C}_{1, (k + 1) \ell} \end{pmatrix} = \begin{pmatrix} (G^{-1}(\tilde{C}_{1, 1})^T \tilde{C}_0)^T \\ (G^{-1}(\tilde{C}_{1, 2})^T \tilde{C}_0)^T \\ \vdots \\ (G^{-1}(\tilde{C}_{1, (k + 1) \ell})^T \tilde{C}_0 )^T \end{pmatrix} \in \hat{\mathbb{Z}}_N[X]^{(k + 1) \ell \times \ell}
\end{align*}
G^{-1}(\tilde{C}_{1, i})^T \tilde{C}_0 について考えると，G^{-1}(\tilde{C}_{1, i}) \in \mathbb{Z}_N[X]^{(k + 1) \ell} で，\tilde{C}_0 \in \mathbb{Z}_N[X]^{(k + 1) \ell \times \ell} ですから，G^{-1}(\tilde{C}_{1, i})^T \tilde{C}_0 \in \mathbb{Z}_N[X]^{\ell} です．
よって，\tilde{C}_0 \boxtimes \tilde{C}_1 の行ベクトルは長さが \ell で，行ベクトルは全体で (k + 1) \ell 個あるため，\tilde{C}_0 \boxtimes \tilde{C}_1 \in \hat{\mathbb{Z}}_N[X]^{(k + 1) \ell \times \ell} です．
\tilde{C}_0, \tilde{C}_1 \in \mathbb{Z}[X]^{(k + 1) \ell \times (k + 1)} に対して，\tilde{C}_0 \boxtimes \tilde{C}_1 \in \mathbb{Z}[X]^{(k + 1) \ell \times (k + 1)} というのは，\boxtimes が「閉じている」演算だということです．
これまでの議論の考察2
ここでは本文の議論をもう１歩踏み込んだ考察をします．踏み込み方は人それぞれだと思うので，興味のない方は飛ばしてくださって構いません．
GGSW方式の暗号文の足し算が可換なのは自明ですが，GGSW方式の暗号文同士の内積が可換かどうか，は非常に気になるテーマです．今回はこれを考察してみましょう．
結論から書くと，可換とは限らないです．
まずは状況設定です．
GGSW 方式の平文 \mu_1, \mu_2 \in \mathbb{Z}[X] を取って，それぞれの暗号文 \tilde{C}_0 = \overline{\mathrm{GGSW}}_{\tilde{s}}(\mu_1) , \tilde{C}_1 = \overline{\mathrm{GGSW}}_{\tilde{s}}(\mu_2) \in \mathbb{Z}[X]^{(k + 1) \ell \times (k + 1)} を考えます．
\tilde{C}_0 の i \ (1 \leq i \leq (k + 1)\ell) 番目の行ベクトル \tilde{C}_{0, i} に対して，その gadget decomposition G^{-1}(\tilde{C}_{0, i}) = (g^{-1}(\tilde{C}_{0, i, 1}), g^{-1}(\tilde{C}_{0, i, 2}), \cdots, g^{-1}(\tilde{C}_{0, i, (k + 1)\ell})) \in \mathbb{Z}_N[X]^{(k + 1) \ell} を考えます．ただし，1 \leq j \leq (k + 1) \ell で \tilde{C}_{0, i, j} でベクトル \tilde{C}_{0, i} の j 番目の要素を表します．
また，\tilde{C}_1 の i \ (1 \leq i \leq (k + 1)\ell) 番目の行ベクトル \tilde{C}_{1, i} に対して，その gadget decomposition G^{-1}(\tilde{C}_{1, i}) = (g^{-1}(\tilde{C}_{1, i, 1}), g^{-1}(\tilde{C}_{1, i, 2}), \cdots, g^{-1}(\tilde{C}_{1, i, (k + 1)\ell})) \in \mathbb{Z}_N[X]^{(k + 1) \ell} を考えます．ただし，1 \leq j \leq (k + 1) \ell で \tilde{C}_{1, i, j} でベクトル \tilde{C}_{1, i} の j 番目の要素を表します．
このとき，考えていることは \tilde{C}_0 \boxtimes \tilde{C}_1 と \tilde{C}_1 \boxtimes \tilde{C}_0 が等しいかどうかです．
互いに行列のサイズが等しいので，i \ (1 \leq i \leq (k + 1) \ell) 行目を比較します．
すると，G^{-1}(\tilde{C}_{1, i})^T \tilde{C}_0 と G^{-1}(\tilde{C}_{0, i})^T \tilde{C}_1 が等しいかどうかを考えれば良いです．
しかし，まともに考えるのはめちゃくちゃ辛いので，G^{-1}(\tilde{C}_{1, 1})^T \tilde{C}_0 の第１成分と G^{-1}(\tilde{C}_{0, 1})^T \tilde{C}_1 の第１成分が等しいかどうかを考えます．
つまり，G^{-1}(\tilde{C}_{1, i})^T \tilde{C}_0 の (1,1) 成分と G^{-1}(\tilde{C}_{0, i})^T \tilde{C}_1 の (1,1) 成分が等しいかどうかを調べます．これらが等しくなかったら，全体として，G^{-1}(\tilde{C}_{1, i})^T \tilde{C}_0 と G^{-1}(\tilde{C}_{0, i})^T \tilde{C}_1 は等しくないからです．
\begin{align*}
& G^{-1}(\tilde{C}_{1, 1})^T \tilde{C}_0 \\
& = G^{-1}(\tilde{a}_{1, 1, 1}, \tilde{a}_{1, 1, 2}, \cdots, \tilde{a}_{1, 1, k}, \tilde{c}_{1, 1})^T \tilde{C}_0 \\
& = (g^{-1}(\tilde{a}_{1, 1, 1}), g^{-1}(\tilde{a}_{1, 1, 2}), \cdots, g^{-1}(\tilde{a}_{1, 1, k}), g^{-1}(\tilde{c}_{1, 1}))^T \tilde{C}_0 \\
\end{align*}
ここで，G^{-1}(\tilde{C}_{1, i})^T \tilde{C}_0 の (1,1) 成分は，g^{-1}(\tilde{a}_{1, 1, 1}) の第1成分と \tilde{C}_0 の (1, 1) 成分を掛け合わせたものとなります．
\tilde{a}_{1, 1, 1} \in \hat{\mathbb{Z}}_N[X] でしたから，
\begin{align*}
\tilde{a}_{1, 1, 1} = a_{1, 1, 1, 0} + a_{1, 1, 1, 1} X + \cdots + a_{1, 1, 1, N - 1} X^{N - 1} \hspace{10pt} a_{1, 1, 1, i} \in \hat{\mathbb{Z}}
\end{align*}
であるため（めちゃくちゃ添え字がうるさい・・・），
\displaystyle \begin{align*}
g^{-1}(\tilde{a}_{1, 1, 1}) = g^{-1}(a_{1, 1, 1, 0}) + g^{-1}(a_{1, 1, 1, 1}) X + \cdots + g^{-1}(a_{1, 1, 1, N - 1}) X^{N - 1} \hspace{10pt} g^{-1}(a_{1, 1, 1, i}) \in \left[ - \frac{B}{2}, \frac{B}{2} - 1 \right]^{\ell} \subset \mathbb{Z}^{\ell}
\end{align*}
となります．よって，g^{-1}(\tilde{a}_{1, 1, 1}) の第1成分は，g^{-1}(\tilde{a}_{1, 1, 1, i}) の第1成分を足し合わせたものです．
g^{-1}(\tilde{a}_{1, 1, 1, i}) は a_{1, 1, 1, i} を B 進展開した際の係数でした．つまり，g^{-1}(\tilde{a}_{1, 1, 1}) の第1成分は，a_{1, 1, 1, i} を B で割った商に等しくなります．それは，\displaystyle \left \lfloor \frac{a_{1, 1, 1, i}}{B} \right \rfloor です．
＊\lfloor \cdot \rfloor については， 第１回「実数から整数への丸め」 を参照してください
以上より，g^{-1}(\tilde{a}_{1, 1, 1}) の第1成分は，\displaystyle \sum_{i = 1}^{N - 1} \left \lfloor \frac{a_{1, 1, 1, i}}{B} \right \rfloor です．また，\tilde{C}_0 の (1, 1) 成分は，\tilde{a}_{0, 1, 1} です．
つまり，G^{-1}(\tilde{C}_{1, 1})^T \tilde{C}_0 の第１成分は，\displaystyle \sum_{i = 1}^{N - 1} \left \lfloor \frac{a_{1, 1, 1, i}}{B} \right \rfloor \tilde{a}_{0, 1, 1} と分かりました．同様に，G^{-1}(\tilde{C}_{0, 1})^T \tilde{C}_1 の第１成分は，\displaystyle \sum_{i = 1}^{N - 1} \left \lfloor \frac{a_{0, 1, 1, i}}{B} \right \rfloor \tilde{a}_{1, 1, 1} です．
具体的に書き表すと，次のようになります:
\displaystyle \begin{align*}
& \sum_{i = 1}^{N - 1} \left \lfloor \frac{a_{1, 1, 1, i}}{B} \right \rfloor \tilde{a}_{0, 1, 1} \\
& = \sum_{i = 1}^{N - 1} \left \lfloor \frac{a_{1, 1, 1, i}}{B} \right \rfloor (a_{0, 1, 1, 0} + a_{0, 1, 1, 1} X + \cdots + a_{0, 1, 1, N - 1} X^{N - 1}) \\
& = \sum_{i = 1}^{N - 1} \left \lfloor \frac{a_{1, 1, 1, i}}{B} \right \rfloor a_{0, 1, 1, 0} + \sum_{i = 1}^{N - 1} \left \lfloor \frac{a_{1, 1, 1, i}}{B} \right \rfloor a_{0, 1, 1, 1} X + \cdots + \sum_{i = 1}^{N - 1} \left \lfloor \frac{a_{1, 1, 1, i}}{B} \right \rfloor a_{0, 1, 1, N - 1} X^{N - 1} \\
& \sum_{i = 1}^{N - 1} \left \lfloor \frac{a_{0, 1, 1, i}}{B} \right \rfloor \tilde{a}_{1, 1, 1} \\
& = \sum_{i = 1}^{N - 1} \left \lfloor \frac{a_{0, 1, 1, i}}{B} \right \rfloor (a_{1, 1, 1, 0} + a_{1, 1, 1, 1} X + \cdots + a_{1, 1, 1, N - 1} X^{N - 1}) \\
& = \sum_{i = 1}^{N - 1} \left \lfloor \frac{a_{0, 1, 1, i}}{B} \right \rfloor a_{1, 1, 1, 0} + \sum_{i = 1}^{N - 1} \left \lfloor \frac{a_{0, 1, 1, i}}{B} \right \rfloor a_{1, 1, 1, 1} X + \cdots + \sum_{i = 1}^{N - 1} \left \lfloor \frac{a_{0, 1, 1, i}}{B} \right \rfloor a_{1, 1, 1, N - 1} X^{N - 1}
\end{align*}
さて，これらが等しいかどうかですが，等しくない例はいくらでも作れそうだなと分かります．
上記は結局多項式なので，各係数が等しいことが必要条件ですが，例えば，その定数項である \displaystyle \sum_{i = 1}^{N - 1} \left \lfloor \frac{a_{1, 1, 1, i}}{B} \right \rfloor a_{0, 1, 1, 0} と \displaystyle \sum_{i = 1}^{N - 1} \left \lfloor \frac{a_{0, 1, 1, i}}{B} \right \rfloor a_{1, 1, 1, 0} を考えてみます．
パラメタ設定を 今回の「GGSW方式のアルゴリズムの具体例」 に合わせると，N = 4, \beta = 2, q = 256 とすると，B = 4 であり，\tilde{a}_{0, 1, 1} = 120 + 33 X + 9 X^2 + 82 X^3, \ \tilde{a}_{1, 1, 1} = 155 + 13 X + 203 X^2 + 95 X^3 とすると，
\displaystyle \begin{align*}
& \sum_{i = 1}^{N - 1} \left \lfloor \frac{a_{1, 1, 1, i}}{B} \right \rfloor a_{0, 1, 1, 0} \\
& = \left \lfloor \frac{155 + 13 + 203 + 95}{4} \right \rfloor 120 \\
& = 117 \cdot 120 = 216 \\
\end{align*}
であり（係数は \mathbb{Z} / q \mathbb{Z} = \mathbb{Z} / 256 \mathbb{Z} で計算），
\displaystyle \begin{align*}
& \sum_{i = 1}^{N - 1} \left \lfloor \frac{a_{0, 1, 1, i}}{B} \right \rfloor a_{1, 1, 1, 0} \\
& = \left \lfloor \frac{120 + 33 + 9 + 82}{4} \right \rfloor 155 \\
& = 61 \cdot 155 = 239 \\
\end{align*}
を得られます．
以上をまとめると，
\displaystyle \sum_{i = 1}^{N - 1} \left \lfloor \frac{a_{1, 1, 1, i}}{B} \right \rfloor a_{0, 1, 1, 0} と \displaystyle \sum_{i = 1}^{N - 1} \left \lfloor \frac{a_{0, 1, 1, i}}{B} \right \rfloor a_{1, 1, 1, 0} が等しいとは限らない
\Rightarrow G^{-1}(\tilde{C}_{1, 1})^T \tilde{C}_0 の第１成分と G^{-1}(\tilde{C}_{0, 1})^T \tilde{C}_1 の第１成分が等しいとは限らない
\Rightarrow G^{-1}(\tilde{C}_{1, 1})^T \tilde{C}_0 と G^{-1}(\tilde{C}_{0, 1})^T \tilde{C}_1 が等しいとは限らない
\Rightarrow G^{-1}(\tilde{C}_{1})^T \tilde{C}_0 と G^{-1}(\tilde{C}_{0})^T \tilde{C}_1 が等しいとは限らない
となります．つまり，\boxtimes は可換とは限らないことが示されました．
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！
Discussion