って聞かれたときに答えられなかったので，これを機に整理してみます．

この記事は勝手に秘密計算アドベントカレンダーの３日目の記事です．

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

P.-E. Clet, O. Stan, and M. Zuber: "BFV, CKKS, TFHE: Which One is the Best for a Secure Neural Network Evaluation in the Cloud?", In: International Conference on Applied Cryptography and Network Security. Springer, Cham, 2021. p. 279-300.

記事全体として，全３部作を予定しています．今回（初回）は論文の内容にはほとんど入らずに，

BFV, CKKS, TFHE とは
BFV, CKKS, TFHE の暗号化の違い

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

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

自己紹介

耐量子計算機暗号（特に符号ベース暗号の量子的な安全性）を研究している修士２年です．

普段Qiitaでは量子関連を扱い，

量子アルゴリズム①　Shorの素因数分解アルゴリズム

Quantum Blockchain のサーベイ

Silqに触れる

Zennでは，古典関連（耐量子暗号やプログラマブルブートストラップの解説記事）を扱っています（唐突な宣伝）．

McEliece暗号

プログラマブルブートストラップの原著論文を理解する回　1/4

イデアル格子暗号入門を深く理解する　1/3

QR-UOV 理解ログ　1/7

BFV, CKKS, TFHE とは

これらは，格子暗号をベースとする準同型暗号方式のことです．
格子暗号ベースの準同型暗号の歴史などに関しては (完全)準同型暗号の最前線1（入門編）が詳しいです．

それぞれの原論文

BFV
Brakerski, Z.: Fully homomorphic encryption without modulus switching from classical gapsvp. In: Safavi-Naini, R., Canetti, R. (eds.) Advances in Cryptology – CRYPTO 2012.
pp. 868–886. Springer Berlin Heidelberg, Berlin, Heidelberg (2012).

Fan, J., Vercauteren, F.: Somewhat practical fully homomorphic encryption (2012).

CKKS
Cheon, J., Kim, A., Kim, M., Song, Y.: Homomorphic encryption for arithmetic of approximate numbers. In: International Conference on the Theory and Application of Cryptology and Information Security. pp. 409–437 (11 2017).

TFHE
Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: Tfhe: Fast fully homomorphic encryption over the torus. Journal of Cryptology 33 (04 2019).

BFV, CKKS, TFHE の暗号化の違い

論文の内容に入らない，とか書いたのですが，実はここは論文の3.4節を参考にしています．

共通部分から整理します．
まず，全て暗号化方式なので，KeyGen, Encrypt, Decrypt の３つのアルゴリズムの組みから成り立ちます．

更に，それぞれのアルゴリズムの「フレームワーク」が同じです．具体的には，$n$ をセキュリティパラメタとしたとき，

KeyGen（$n \mapsto (s, (p_1, p_2))$）

秘密鍵（$s$）：ある環からランダムに取る
公開鍵（$p_1, p_2$）：ある環からランダムに $a$ とノイズ $e$ を取って，$a, s, e$ を使った演算結果を $p_1$，$a$ を $p_2$ とする

＊TFHEのみ $p_1, p_2$ が逆ですが，この辺は順不同

Encrypt（$(\mu, p_1, p_2) \mapsto (c_1, c_2)$）

Decrypt（$(c_1, c_2, s) \mapsto \mu^{\prime}$）
$c_1, c_2, s$ を使った演算結果を $\mu^{\prime}$ とする（これが Encrypt での $\mu$ と一致しないと困る）

となります（上で出てくる演算は，その環の中での演算のこと）．
もちろん，「ある環」や「演算結果」の部分は方式によって異なりますが，所詮はその程度の違いであり，本質的には３つとも同じ暗号化方式と見ることができます．

暗号化のフレームワークが同じ，ということは背景にあるNP困難な問題も同じ，ということです．実際に，RLWE問題というNP困難な問題を安全性の根拠としています．

すると，異なる部分は，上の「ある環」や「演算結果」と書いた部分と分かるのではないでしょうか．

以下では，それぞれの詳しいことを見ていきます（~~Qiitaはなんか数式表示があれなので，~~ 別の媒体で書いたもののスクショで）．

まず，BFVからです．

細かい補足

例えば，$[-(a \cdot s + e)]_q$ なんかは，$a, e \in \mathbb{Z}^{(q)}[X] / (X^N + 1)$ かつ $s \in \mathbb{Z}^{(p)}[X] / (X^N + 1) \subset \mathbb{Z}^{(q)}[X] / (X^N + 1)$ なので，$-(a \cdot s + e) \in \mathbb{Z}^{(q)}[X] / (X^N + 1)$ ですから，わざわざ $[-(a \cdot s + e)]_q$ とする意味はありません．正直こう書くよりどこの環での演算かを書く（例えば $-(a \cdot s + e)$ in $\mathbb{Z}^{(q)}[X] / (X^N + 1)$ みたいな感じ）方がはっきりして分かりやすい気がしますが，そういう風習なんですかね．

演算の入り方について

CKKS, TFHE でも同じような演算（多項式環の剰余環）が入っています．

$a, s, e$ は全て $Z^{(q)}[X]/(X^N+1)$ で定義されています．つまり，$a, s, e$ は係数が $Z^{(q)}$ で定義されていて次数が $N-1$ 以下の多項式です．

＊ $s$ のみ $Z^{(p)}[X]/(X^N+1)$ ですが，$q$ は $2p$ で割り切れる，という条件から $p < q$ なので，$Z^{(p)}$ の範囲を $Z^{(q)}$ に拡張して考えています

「$\mathbb{Z}^{(q)}[X] / (X^N + 1)$ 内で演算を行う」とは，$Z^{(q)}[X]/(X^N+1)$ は和と積で閉じているので， $-(as+e)$ はその和と積で演算を行う，という意味です．

$Z^{(q)}[X]/(X^N+1)$ の任意の元を $g, h$ として，$Z^{(q)}[X]/(X^N+1)$ の和と積についての詳細です:
$Z^{(q)}[X]/(X^N+1)$ の和（$+$で書きます）
1 : $g + h$ を $Z[X]$ で行う（つまり，「通常の」多項式の足し算を行う）
2 : 1 で得られた多項式の各係数に対して，mod $q$ で $Z^{(q)}$ の範囲になるように調整する

$Z^{(q)}[X]/(X^N+1)$ の積（$\cdot$で書きます）
1 : $g \cdot h$ を $Z[X]$ で行う（つまり，「通常の」多項式の掛け算を行う）
2 : 1 で得られた多項式の各係数に対して，mod $q$ で $Z^{(q)}$ の範囲になるように調整し，各次数に対して，$X^N = 1$ で次数が $N-1$ 以下になるように調整する
3 : 2で得られた多項式に対して，同じ次数の係数は足し合わせて，mod $q$ で $Z^{(q)}$ の範囲になるように調整する

以上の演算で，$Z^{(q)}[X]/(X^N+1)$ は和と積で閉じてます．

簡単な具体例ですが，$q = 12, N = 4$ として，$g = 5 X^2 + 2, h = 4 X^2 - X + 5$ とします．$Z^{(12)} = { -5, -4, … , 5, 6 }$ です．
和
$g + h = 9 X^2 - X + 7 in Z[X]$ で，
各係数を mod $12$ で $Z^{(12)}$ の範囲になるように調整すると，$-3 X^2 - X - 5$ となります．
つまり，$Z^{(12)}[X]/(X^N+1)$ 内で $g + h = -3 X^2 - X - 5$ です．

積
$g \cdot h = 20 X^4 - 5 X^3 + 33 X^2 - 2 X + 10 in Z[X]$ で，
各係数を mod $12$ で $Z^{(12)}$ の範囲になるように調整すると，$-4 X^4 - 5 X^3 - 3 X^2 - 2 X - 2$ となり，$X^4 = 1$ から，$-5 X^3 - 3 X^2 - 2 X - 6$ で，
更に各係数を mod $12$ で $Z^{(12)}$ の範囲になるように調整すると，$-5 X^3 - 3 X^2 - 2 X + 6$ です．
つまり，$Z^{(12)}[X]/(X^N+1)$ 内で $g \cdot h = -5 X^3 - 3 X^2 - 2 X + 6$ です．

3.4に記載の定義そのものと比べると，余分な条件もついている（$q$ は $2 p$ で割り切れる，とか）のですが，これは↓の議論との整合性を取るためです．

上で言う整合性の補足

BFVの原論文（特にFV）を見ると，$q$ は $2 p$ で割り切れる，という条件はなくて，$\frac{q}{p}$ の部分が $\lfloor \frac{q}{p} \rfloor$ になっている（$\lfloor \cdot \rfloor$ は切り捨て関数）のですが，これだと正当性を満たさないような気がします．「$q$ は $2 p$ で割り切れる」を加えると確実にOKなので，今回はそのようにしています．

そして，BFVの正当性です．（BFVに限らず）以下では $[[a]_q + [b]_q]_q = [a + b]_q$ を多用しています．

~~仮定含めて色々修正しましたが，正当性ぐらいはすぐに確認できるような定義をしてもらいたいものですね・・・．~~

続いて，CKKSです．

見た感じBFVとそこまで大きく変わらないですね．

CKKSの正当性です（~~BFVでがんばったので，この辺から議論が雑に~~）．

「○○が小さい」の補足

この意味は，「○○の無限ノルムがある定数で上から抑えられる」という意味です．無限ノルムというのは，簡単にいうと，多項式であれば各係数のmaxのことです． BFVの場合であれば $\frac{q}{2p}$ という条件を加えていました． CKKSだとどんな感じの値になるのか気になるところです．

議論が雑に，っていうのは上の議論だと，$s \in \mathbb{Z}^{(3)}[X]$ のありがたみ（つまり，各係数の絶対値が1以下）が分からないっていうことです．

最後にTFHEを一気に見ます．

ここはめちゃくちゃ修正しました．論文のままだと，Torusの掛け算を行なっていますが，Torus の掛け算は定義できるが上手くいかないので，ぶっちゃけ致命的です．
＊「上手くいかない」とは「well-defined ではない」という意味です，大雑把には，定義した「掛け算」による演算結果が一意とは限らない，というイメージです（だから，考えないことが多い）

Torusについて

ここでいうTorusとは1次元Torusのことです．かといって $S^1$ の話をしたいわけではなく，大雑把には「0以上1未満の集合で足し算とスカラー倍で閉じている」と思えば良いかと（掛け算は↑で書いたように考えない）．例えば，上の定義では $a \cdot s$ などを行なっていますが，これは $s \in \mathbb{B}^n, a \in \mathbb{T}^n$ であり，Torus内の掛け算ではなく，スカラー倍（しかも0か1）を行なっているので，ちゃんとOKです．

Torusについて詳しく知りたい方はプログラマブルブートストラップの原著論文を理解する回　1/4 を（唐突な宣伝）．

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