この記事は 勝手に秘密計算アドベントカレンダー の10日目の記事です．
下記の論文の解説をメインに行なっていきます．
記事全体として，全４部作を予定しています．
第１回：RLWE による定数サイズの暗号文を持つ Leveled Multikey FHE①
第２回：RLWE による定数サイズの暗号文を持つ Leveled Multikey FHE②
今回（第３回）は
- CDKS 方式
- relinearization key
の２本立てで書いていきます（論文でいうところの 4.1 Adding homomorphic capabilities まで）．
突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください
CDKS 方式
前回の「Relinearazation」 で参加者 $i, j$ の秘密鍵 $s_i, s_j$ の積が必要で，そのためには CDKS 方式を使うと書きました．
今回はそのCDKS方式を導入します．
復号はあっさり書いていますが，うまく条件をつけると，$c_0, c_2$ から $m$ を復号できます（今回は復号を使わないから書いていないんだと思うんですけど，個人的には書いてほしいですねぇ・・・いや自分で調べろよって感じですが）．
「ここで」以下の条件が人工的だったり，$\approx$ ではなく $=$ だったりしますが，その辺は最後に注を入れています．
証明です．
注です．
relinearization key
早速スクショから．それぞれがどのように relinearization key を作るのか，からです．
$\hat{\mathrm{rlk}}$ を扱いやすい形に変形します．
上記の $\hat{\mathrm{rlk}}$ を使って，3成分の暗号文を2成分の暗号文へと変形します．
めでたしめでたし・・・とは少しいかない話を最後に入れます．
そこで，CDKS 方式での命題を用いることで，この値を求められます．
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！