RLWE による定数サイズの暗号文を持つ Leveled Multikey FHE④

この記事は [勝手に秘密計算アドベントカレンダー](https://qiita.com/kenmaro/items/3e8a124ce4306fe040dc) の12日目の記事です．

下記の論文の解説をメインに行なっていきます．

[V. Daza, P. Morillo, and S. Rovira: "Leveled Multikey FHE with constant-size ciphertexts from RLWE", Cryptology ePrint Archive, 2022.](https://eprint.iacr.org/2022/447)

記事全体として，全４部作を予定しています．

第１回：[RLWE による定数サイズの暗号文を持つ Leveled Multikey FHE①](https://qiita.com/0917laplace/items/e3bafb2ebf299a9d0d43)
第２回：[RLWE による定数サイズの暗号文を持つ Leveled Multikey FHE②](https://qiita.com/0917laplace/items/2ff2085be85b67b3165a)
第３回：[RLWE による定数サイズの暗号文を持つ Leveled Multikey FHE③](https://qiita.com/0917laplace/items/ebb732a54af327a988f6)

今回（第4回）は

- 提案方式
- 誤差評価

の２本立てで書いていきます．

**突貫で書いてしまった部分もあるので，大いに誤りを含む可能性があります．誤字・脱字レベルでも構いませんので，ご指摘ください．
また，予告なしに内容の加筆や構成の変更を行うことがありますが，読みやすくするためのものですので，ご容赦ください**

# 提案方式
ここは今までのまとめ，ということになります．特別解説しないといけないこともありません．

![Leveled_4_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1298501/1e518bb7-cfec-7fe5-c2dd-6e8e357e9052.png)

![Leveled_4_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1298501/bbac4356-b23d-ed59-afe1-5ca12213dc82.png)


# 誤差評価
最後に各場面での誤差評価を行います，実際に実装しようと思ったら，各パラメタを次の条件を満たすように設計すればOKということになります．
特に最後の定理の $\displaystyle N^{L + 1} \gamma_R^{2 L - 2} B^L E^{L - 1} (d + 32 \gamma_R^3 B E) < \frac{q}{2^{4 L - 1}}$ を満たしてくれれば，relinearzation を考慮した上で暗号文を $L$ 回掛け算しても復号できます（各パラメタの意味は，ステートメントを参照してください）．

暗号文での誤差
すでに一度やっていますが，振り返る意味で（っていうか議論の都合上）もう一度やってみます．

![Leveled_4_3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1298501/86c9d7bc-1e84-161a-6507-1ff265d8c06b.png)


暗号文の足し算での誤差
ほとんど前の議論と同じです．
$L$ を正整数として，暗号文を $2^L$ 回足したときに，また暗号文空間内で定義される誤差を考察します．

![Leveled_4_4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1298501/115e7532-3751-e1ee-e7b9-cdff2738648d.png)


$L = 0$ の場合を許容すると，暗号文を0回足す場合，というのは，前節の「暗号文での誤差」に相当します．実際，$2^{0 + 2} = 4$ ですので，前節での条件を満たしています．



暗号文の掛け算での誤差（relinearization を考慮しない場合）
~~原論文と比較して，全く仮定が足りず議論として破綻している上に，原論文でもかなり読みづらい大問題パート~~
原論文と比較してかなりリメイクしてすっきりした議論にしています（ここに３週間ぐらいかかった()）

まずはLPR方式から

![Leveled_4_5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1298501/ada9eabd-07b5-3b6c-11d9-9be604613c4f.png)

続いてLMFV方式ですが，秘密鍵の部分が変更されるだけなので，そんなに難しくはないです．

![Leveled_4_6.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1298501/5041edc7-144a-ac2b-66cb-fa0af665a650.png)

そして，relinearization に関する誤差について評価します．

![Leveled_4_7.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1298501/1fd9703a-5f01-46e9-a93a-e9a0ea1110fc.png)


暗号文の掛け算での誤差（relinearization を考慮する場合）
最後に relinearization での誤差も考慮した場合の誤差を考察します．基本的に，relinearization を考慮しなかったときの誤差に，relinearization に関する誤差を足し上げればOKです．

なんですが，原論文だと，近似を使っていて，上からの評価と下からの評価が混在してい~~てすごく嫌だっ~~たので，必要条件という形で上からの評価に絞っています．

![Leveled_4_8.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1298501/cdf9c6dc-cc46-527f-e57b-6899b87df089.png)


--------------------------
さて，今回で

[V. Daza, P. Morillo, and S. Rovira: "Leveled Multikey FHE with constant-size ciphertexts from RLWE", Cryptology ePrint Archive, 2022.](https://eprint.iacr.org/2022/447)

の解説記事の連載が終了しました．最後この記事だけで１ヶ月ぐらいかかってしまいましたが，正直なところそれだけ読みづらい論文だと思います．
引用されている論文の仮定を明示しなかったり（そもそも引用先の論文も読みづらい・・・），そこそこ誤植もあるので，少し大変だったように思えます．

ですが，これで multikey による準同型暗号も大筋はだいぶ分かりました．確かにこれをTFHEに応用するというのは自然な発想かなと思います．
今後もこのような論文解説の記事を少しずつ書いていこうと考えています！

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