$q$ が3以上の奇数であることは，後で効いてきます．
上で出てくる $|| \cdot ||$ は無限ノルムと呼ばれるノルムであり，ノルムの定義から $0 \neq r, r^{\prime}$ のとき，$|| r || \neq 0$ かつ $|| r^{\prime} || \neq 0$ が分かります．

無限ノルムについて，詳しいことはプログラマブルブートストラップの原著論文を理解する回　3/4 に記載していますので，もしよろしければ（唐突な宣伝）．

また，floor function （切り捨て関数） $\lfloor \cdot \rfloor$ と ceiling function （切り上げ関数） $\lceil \cdot \rceil$ について，詳しいことはプログラマブルブートストラップの原著論文を理解する回　1/4 に記載していますので，もしよろしければ（唐突な宣伝 part2）．

では，まず上４つの具体例から見ていきます．

上の補足

下記の既約や円分多項式については，上の具体例の前にリンクをつけた「プログラマブルブートストラップの原著論文を理解する回　1/4」に詳細をつけているので，もしよろしければ（唐突な宣伝Part3）．

上の具体例では暗に $\mathbb{F}_3$ 上で $X^4 + 1$ が既約であることを使っています（可約な多項式で割ると全体にならない）．念のため確認します．

まず，$\alpha \in \mathbb{F}_3$ で $\alpha^4 + 1 = 0$ なる $\alpha$ は存在しません．よって，因数定理から $X^4 + 1$ が1次の多項式で割り切れることはありません．
$a, b, c, d \in \mathbb{F}_3$ で，$X^4 + 1 = (X^2 + a X + b)(X^2 + c X + d)$ のように分解できたとして，右辺を展開して指数を見比べると，$a + c = 0, b + ac + d = 0, ad + bc = 0, bd = 1$ です．$a + c = 0$ から $(a, c) = (0, 0), (1, 2), (2, 1)$ で $bd = 1$ から $(b, d) = (1, 1), (2, 2)$ が候補になります．これらに対して，$b + ac + d = 0, ad + bc = 0$ なる $(a, b, c, d)$ の組を探せば良いのですが，そのような組は存在しません（頑張って６通り確かめてください）．よって，因数定理から $X^4 + 1$ が2次の多項式で割り切れることもありません．
$X^4 + 1$ が3次の多項式で割り切れるなら，1次の多項式でも割り切れるはずなので，これは不適．
以上より，$X^4 + 1$ は $\mathbb{F}_3$ 上で既約なので，$n = 4, q = 3$ とすると，$R_q$ は $\mathbb{F}_3$ 係数で3次以下の多項式全体の集合（特に体）になります．

ちなみに $\mathbb{Z}$ 上で $X^4 + 1$ は8次の円分多項式なので，こちらも既約です．よって，$R$ は整数係数で3次以下の多項式全体の集合（特に体）になります．

続いて，$\gamma_R$ についてですが，このように定義したときに $\gamma_R$ が存在するのか（右辺が有限の値になるのか）は気になるところです．

Powersof2 と BitDecomp は一見すると分かりづらいかもしれません．これらの関数は Gentryの論文由来のはずです．

まず，Powersof2 からです．$q$ を２べきでない自然数（今は３以上の奇数）とするとき，$\lceil \log_2 q \rceil = \lfloor \log_2 q \rfloor + 1$ が成り立つことに注意すると，Powersof2 の値域の指数部分に $\lceil \log_2 q \rceil$ が出てきて，0番目から始まる最後のインデックスが $\lfloor \log_2 q \rfloor$ になることが分かるかと思います．

続いて BitDecomp です．

$q$ は $\lceil \log_2 q \rceil$ bit なので，$q$ を2進展開すると，$2^0$から$2^{\lfloor \log_2 q \rfloor}$ までを組合せた総和で表せます．よって，右辺の要素のインデックスは0から $\lfloor \log_2 q \rfloor$ です．

＊ちなみに論文だと，左辺の $\sum$ で $i$ は $\lceil \log_2 q \rceil$ まで走っていますが，$\lfloor \log_2 q \rfloor$ までで十分です（というより誤植）

前提知識

まずは，今回の暗号方式の安全性の根拠となる決定性（決定的？）RLWE問題を紹介します．

このように分布を識別する形の定義もありますが，次のように定義することもあります（暗号化方式とダイレクトに関係しているので，次回以降はこちらの形が扱いやすいはず）．

どちらもNP困難な問題です．
これらの問題が難しいのことの直感的な説明は，プログラマブルブートストラップの原著論文を理解する回　2/4 の折りたたみを参照してください（唐突な(ry）．

続いて，今回使う MKFHE 方式（複数の鍵を使った準同型暗号方式）のフレームワークを紹介します．

＊FHE encryption scheme って Fully Homomorphic Encryption encryption scheme なんですが，これでいいんですかね？MKFHE scheme で統一するつもりですが・・・

Decryptの詳細

Decrypt の合成の部分をしっかり書くなら，次のようになります:

$\mathrm{Decrypt}(sk = (sk_1, \cdots, sk_n), ct) = \mathrm{FinDec}(\mathrm{PartDec}(sk_1, ct), \cdots, \mathrm{PartDec}(sk_n, ct))$

Eval は，暗号文空間内で任意の演算が定義されていることを保証しています（が，平文空間と暗号文空間の演算の整合性の言及まではしていないので，これそのものが準同型性ではありません）．
ちなみに Eval で，なんで公開鍵を引数に取る必要があるのかは分かっていないので，どなたかご存じの方がいらっしゃいましたら，ご教示願います・・・．

MKFHE 方式の正当性を紹介します．正当性と言っているのですが，要するに準同型性です．

なんか正当性と言ったら，普通は，平文を暗号化して復号すると元に戻る，ことを指すような気がするのですが，それは1変数としての準同型性に含まれている，という意味で，準同型性を正当性と言っているのですかね？

関数 $f$ が negligible であることの定義をご存じの方は，overwhelming probability は確率が $1 - f(x)$ で表せるとき $f$ が negligible であることを言います．

最後に MKFHE 方式のコンパクト性について紹介します．

鍵の個数に暗号文のサイズが依存しない，と最初に言っていたので，おそらくそれを示すために，コンパクト性を導入したのかなって感じです．

次回から，MKFHE 方式の具体的な設定などに入って行きます．

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