今回は
M. Joye: ``TFHE Public-Key Encryption Revisited'', Cryptography ePrint Archive, 2023/603, 2023.
をざっくりと解説します．そこまで内容に踏み込まなくてもいいという方向けであり，もう少し理論の深いところまで知りたい方向けには別で連載記事を作ります．
ということで早速内容に入ります．
概要
TFHE暗号方式は今まで共通鍵暗号方式しか知られていなかったが，公開鍵暗号方式版を提案した
構成
第１章：共通鍵版TFHE暗号方式の復習
第２章：公開鍵版TFHE暗号方式の提案（簡単な場合）
第３章：公開鍵版TFHE暗号方式の提案（一般の場合）
第４章：複数の平文の暗号化
第５章：変種の提案
第２・３章は何が「簡単」・「一般」かというと，秘密鍵のサイズ $n$ について，第２章では $n$ が２べきの場合，第３章では $n$ が一般の円分多項式の次数の場合を考えています．
＊この辺の拡張の仕方は M. Joye, M. Walter: "Liberating TFHE: Programmable Bootstrapping with General Quotient Polynomials", Cryptology ePrint Archive, 2022. もご参考に
＊実は↑の解説記事を書いています（隙あらば宣伝） 【ePrint解説】Liberating TFHE 1/4
しかし第３章で提案される一般の場合の暗号方式は第２章の自明な拡張であり，第３章での議論は息の長いものであるため，このePrintを理解するには第２章が分かれば十分かと思います．
よって，本記事では第２章のみざっくりと解説をします．
＊後で連載する記事では今回触れられなかったもの含めて全ての範囲を扱います
第２章
reverse negative wrapped convolution
$n$ を正整数として，$u = (u_1, \cdots, u_n), v = (v_1, \cdots, v_n) \in \mathbb{Z}^n$ とするとき，$u$ と $v$ の reverse negative wrapped convolution とは，ベクトル $w = u \circledast^n v = (u \circledast_1 v, \cdots, u \circledast_n v)$ のことである．ただし，$1 \leq i \leq n$ に対して，$u \circledast_i v = \sum_{j = 1}^i u_j v_{n + j - i} - \sum_{j = i + 1}^{n} u_j v_{j - i}$ とする．
＊ePrintでは，$w = u \circledast v$ と記載されていますが，$\circledast$ は $u$ と $v$ のサイズに依存するため，それを明示するべく $\circledast^n$ としています
一見するとややこしく見える定義ですが，こういう操作では絵を描くと一発です
↑は $u \circledast_i v$ のイメージ図で，赤線が前半の $\sum$ の部分で青線が後半の $\sum$ の部分を表しています．こうしてみると，
$i$ が増えると，前半の $\sum$ の $j$ の範囲が大きくなるから段々赤線の部分が左に寄ってきて（赤線の本数が増える），そのぶん青線の本数が減る
逆に$i$ が減ると，前半の $\sum$ の $j$ の範囲が小さくなるから段々赤線の部分が右に寄ってきて（赤線の本数が減る），そのぶん青線の本数が増える
ことが読み取れます
このイメージがあれば，添え字がどうとか間違えることはかなり減るかなと思います
＊実はこの章のLemma 1もePrintでは数式でごちゃごちゃ示しています（それはそれで大切）が，↑のような絵で全て示すことができます（詳しいことは詳細な記事で）
このイメージを持って具体例を見ていきます．
$u = (1, 2, 3), v = (4, 5, 6)$ のとき，
$u \circledast_1 v = (u_1 v_3) - (u_2 v_1 + u_3 v_2) = - 17$
$u \circledast_2 v = (u_1 v_2 + u_2 v_3) - (u_3 v_1) = 5$
$u \circledast_3 v = (u_1 v_1 + u_2 v_2 + u_3 v_3) = 32$
ですから，$u \circledast^3 v = (- 17, 5, 32)$ となります．
提案方式
KeyGen, Encrypt, Decrypt の３つのアルゴリズムから成ります
KeyGen
まず $\kappa$ を security parameter としておきます．
KeyGen$(1^{\kappa}) \mapsto (pp = (n, \sigma, t, q), pk = (a, b), sk = s)$
- $n$ : ２べき
- $t, q, \Delta$ : 正整数で $q$ は $t$ で割り切れ，$\Delta = q / t$
- $\chi_1, \chi_2$ : 平均0，分散$\sigma^2$の誤差分布
- $s = (s_1, \cdots, s_n) \overset{$}{\longleftarrow}${ 0, 1 }$^n$ : 秘密鍵
- $a = (a_1, \cdots, a_n) \overset{$}{\longleftarrow} (\mathbb{Z} / q \mathbb{Z})^n$
- $e = (e_1, \cdots, e_n) \overset{$}{\longleftarrow} \chi_1^n$
- $b = a \circledast^n s + e$
Encrypt
$m \overset{$}{\longleftarrow}${$0, 1, \cdots, t - 1$} を平文とします．
Encrypt$_{pk}(m) \mapsto c = (a^{\prime}, b^{\prime})$
- $r = (r_1, \cdots, r_n) \overset{$}{\longleftarrow}${$0, 1$}$^n$
- $e_1 = (e_{1, 1}, \cdots, e_{1, n}) \overset{$}{\longleftarrow} \chi_1^n$
- $e_2 \overset{$}{\longleftarrow} \chi_2$
- $a^{\prime} = a \circledast^n r + e_1$
- $b^{\prime} = \langle b, r \rangle + \Delta \cdot m + e_2$
- $c = (a^{\prime}, b^{\prime})$
Decrypt
Decrypt$_{sk}(c) \mapsto m^{\prime}$
- $m^{\prime} \leftarrow \lceil (b^{\prime} - \langle a^{\prime}, s \rangle \ \mathrm{mod} \ q) / \Delta\rfloor \ \mathrm{mod} \ t$
そして次の定理が成り立ちます（証明略）:
$E = e_2 + \langle e, r \rangle - \langle e_1, s \rangle$ とするとき，$E < \Delta / 2$ であれば，Decrypt${sk}($Encrypt${pk}(m)) = m$ が成り立つ．
まとめ
今回は公開鍵版TFHE暗号方式をざっくりと見ました．大きな方針は共通鍵のときと変わらないですね．
reverse negative wrapped convolution の性質や最後の定理の証明は端折ったりしましたが，いずれ理論的なことに関する解説記事も出せたらなと思っています．
今回の内容はここまでです．ここまでご覧になってくださった方々ありがとうございます！