この記事は 勝手に秘密計算アドベントカレンダー の7日目の記事です．
下記の論文の解説をメインに行なっていきます．
記事全体として，全４部作を予定しています．
第１回：RLWE による定数サイズの暗号文を持つ Leveled Multikey FHE①
今回（第２回）は
- MKFHE 方式の仮定
- LPR方式（単一の鍵での暗号化方式）
- LMFV方式（複数の鍵での暗号化方式）
- Relinearization
の４本立てで書いていきます（論文でいうところの 3.3 Relinearization まで）．
今回の話は，イデアル格子暗号の話を知っていると，イメージしやすい部分が多いと思います（特にRelinearization）．
＊「イデアル格子暗号」については，連載記事を書いたので，ぜひそちらも（唐突な宣伝）
イデアル格子暗号入門を深く理解する 1/3
突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください
MKFHE 方式の仮定
今回の MKFHE 方式では，次の３つを仮定します．
- circular security
- CRS model
- Semi-honest model
まず，MKFHE では，複数の（$N$ 個とします）秘密鍵がありますが，これは$N$ 人の参加者（パーティ）でやり取りを行う，とイメージしてください．
circular security とは，$N$ 人でやり取りをする「状態」を $N$ 個の頂点を持つグラフとみなします（逆に，$N$ 個の頂点があって，辺で結ばれているところが通信を行う，と考えた方が分かりやすいかも，有向グラフですし）．特にこのグラフが巡回グラフであっても，安全（semantically secure）のとき，circular security を満たす，と言います（全然自信ないので，間違っていたらご指摘お願いします・・・）．
参照（circular security の原論文）： Jan Camenisch and Anna Lysyanskaya: "An efficient system for non-transferable anonymous credentials with optional anonymity revocation", In EUROCRYPT ’01, volume 2045 of LNCS, pages 93–118, 2001.
次に CRS model とは，始めに参加者全員に共通の値 $a \in R_q$ を配布するモデルです．
最後に semi-honest model とは，全ての参加者はプロトコルに従って行動するモデルです．一見すると当たり前のように見えますが，他の参加者の情報について推測などを行うことはOKです．
参照：佐久間 淳: "データ解析におけるプライバシー保護"，講談社，2016
＊以前に書評記事を書いたので，ぜひそちらも（唐突な宣伝）
書籍『データ解析におけるプライバシー保護』の紹介
LPR 方式
次のLPR方式は，１つの鍵での暗号化方式ですが，この方式を土台にして，複数の鍵での暗号化方式を考えます．
この暗号化方式の安全性の根拠となるのが，前回の決定性RLWE問題 です．
LPR 方式の正当性を確認します（今回の山場）．
ノイズの範囲を指定する必要があり，合っているのか分からんのですが，理論上は問題ないし，本論文の4.3に似たような式があるので大丈夫なはず．
LPR 方式では，加法準同型性（平文空間も暗号文空間も足し算に関して整合性が取れている）を満たします．ちょっと（かなり）雑な議論ですが，↑でやったことと同じことをすればOKです．
一見すると，$ct, ct^{\prime}$ に $e$ の情報は含まれていませんが，$b$ （公開鍵の要素なので今は固定）に含まれることに注意してください．
LMFV 方式
上記の LPR 方式を複数の参加者バージョンへ拡張します．
参加者全員の公開鍵をまとめたものを新たに公開鍵（global な公開鍵）として，復号するときも全員で複合します．
LMFV 方式では，LPR 方式と同様に加法準同型性が成り立ちます（というか，成り立ってくれないと困る）．
乗法（掛け算）に関する準同型性は成り立っていないのですが，その問題を次の章で解決します．
Relinearization
これは Key Switching の方が馴染みのある方がいらっしゃるかもしれません．
LMFV 方式の2つの暗号文 $ct = (ct_1, ct_2), ct^{\prime} = (ct_1^{\prime}, ct_2^{\prime}) \in R_q^2$ を取ります．これらの平文をそれぞれ $m, m^{\prime}$ とします．また，秘密鍵を $\displaystyle s^{+} = \sum_{i = 1}^N s_i$ で固定します．
このとき，掛け算に関する準同型性を期待するなら，$ct \cdot ct^{\prime} = (ct_1 \cdot ct_1^{\prime}, ct_2 \cdot ct_2^{\prime})$ を復号すると，$m m^{\prime}$ になってほしいのですが，残念ながらこれは必ずしも成り立ちません．
しかし，掛け算に関する準同型性がほしい，と考えたときに，次のことを考えます:
そもそも平文が $m$ と成分が1つしかないのに，暗号文 $ct = (ct_1, ct_2)$ と成分が2つ出てくるのはなぜかと考えると，秘密鍵 $sk$ の情報が出てくる成分（$ct_1$）と出てこない成分（$ct_2$）があるからです．
ナイーブに考えると，暗号文の掛け算を行なって「それができた場合」，$sk^2$ の情報が出てくる成分と$sk$ の情報が出てくる成分と $sk$ の情報が出てこない成分と３つ出てくるはずです．
なんですが，それだと掛け算を行うたびに暗号文の成分が増えてしまい，厄介極まりないです．
そこで，秘密鍵 $sk$ から「良い感じな」別の鍵（relinearization key，スイッチ鍵とも）を作って，その鍵の元で掛け算を考えることで，暗号文の成分を２つに抑えつつ，暗号文の掛け算を実現します．
また，その際に $sk^2$ の情報が必要となります．いわゆる $(s^{+})^2$ ですね．
これを展開すると，自身の鍵の二乗 $s_i^2$ と自分と他者の鍵の積 $s_i s_j$ の２つが出てきます．
すると，$s_i s_j$ をどう扱えば良いかが問題になりますが，それを次回 CDKS 方式というものを導入することで，解決します．
Qiitaに直接書いてみたのですが，特に2段落2行目の $s^{+}$ の定義の見栄えが良くない・・・
以下では，$s_{+}, s_{+}^2$ があれば，LMFV方式での暗号文の掛け算を復号して対応する平文の掛け算に戻せることを示します．
「ここで」以下の条件は人工的に見えますが，証明をうまく行うための工夫です．
証明を載せます．
「ここで」以下の条件は最後の最後で効いてきます．この辺のこと全然書いてないんだよなぁ・・・
ちなみに $q \equiv 4 \ \mathrm{mod} \ 1$ の場合は次のようになります．
ちょっと現実的ではないかなぁと思い，今回は省略しました．
$q$の選び方で思ったこと
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！