この記事は 勝手に秘密計算アドベントカレンダー の5日目の記事です．
下記の論文の解説をメインに行なっていきます．
記事全体として，全4部作を予定しています．今回（初回）は
- 論文の背景やアブスト
- 記法
- 前提知識
の三本立てで書いていきます（論文でいうところの 2.2 Definitions まで）．
突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください
自己紹介
耐量子計算機暗号（特に符号ベース暗号の量子的な安全性）を研究している修士２年です．
普段Qiitaでは量子関連を扱い，
Zennでは，古典関連（耐量子暗号やプログラマブルブートストラップの解説記事）を扱っています（唐突な宣伝）．
プログラマブルブートストラップの原著論文を理解する回 1/4
論文の背景やアブスト
- どういう背景や課題・モチベーションがあって，
- どのようなアイディアのもとで，
- どのような結果が得られたのか
を整理します．
背景・課題
いくつかの異なる鍵でFHE（Fully Homomorphic Encryption）を行う暗号化方式をMKFHE（Multi-Key FHE）方式という．
従来のMKFHE方式では，暗号文のサイズが大きくなる（プロトコルの参加者数（＝鍵の個数）に依存する）問題点があった．
アイディア
- それぞれの公開鍵のみならず，参加者共通の公開鍵も使う
- Key-Switching
（よく分からなかったのでキーワードだけ，読み進めていけば分かるはず・・・全て終わったら加筆しておきます）
結果
プロトコルの参加者数に依存しないMKFHE方式を提案した
それらを元に各章を整理すると，次のようになります:
1章：イントロ
2章：前提知識（MKFHE方式）
3章：ブロックの構成（アイデアで出てきた定義とか）
4章：提案方式（２章と３章を組合せる）
つまり，2章と3章までが「準備段階」で，４章が一番言いたいことになります．
ちなみに全４部作のうち，初回で２章・第２回で３章・残りで４章を扱う予定です（少しずれるかも）．
記法
Qiitaはなんか数式表示があれなので， 別の媒体で書いたもののスクショで紹介します
追記：色々と記号がバッティングしていたので，統一しました
$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）．
では，まず上４つの具体例から見ていきます．
上の補足
上の具体例では暗に $\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の詳細
$\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 方式の具体的な設定などに入って行きます．
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！