完全準同型暗号の論文を読む - TFHE 編 (5)

はじめに

みなさんこんにちは。

VIPPOOL でエンジニアをやっています、星月です。

前回は、駆け足で TFHE の全体像を見ました。
今回からは、bootstrapping の手順を１つずつきちんと見ていこうと思います。

bootstrapping key の組み立て

TLWE 暗号文に使う秘密鍵 $\vec{s}$ （ $n$ 次とします）とは別に、
bootstrapping に使うために $\vec{s}$ を暗号化するための鍵、
$\vec{s'}$ を二進数で選びます。このベクトルの次数は、あとで出てくる
テストベクタ多項式 $T(X)$ の次数とそろえる必要があります。

そして、 $\vec{s}$ の各要素ごとに、TRGSW の暗号文を作ります。

まず、Gadget Decomposition から元に戻す作用素を $H$ としました。
$\vec{s'}$ で復号すると $\phi_{s'}(Z_j)=0$ となる TRLWE 暗号文を $2 \ell$ 個だけ作成します。
そうして TRGSW 暗号文の構成通り、
${\rm BK}_i=\left(\begin{array}{c} Z_1 \\ Z_2 \\ \vdots \\ Z_{2 \ell} \end{array}\right) +s_i \cdot H$
とします。この TRGSW 暗号文を $n$ 個用意したセットを bootstrapping key と呼びます。

${\rm BlindRotate}$ に必要な道具、 ${\rm CMux}$

先ほど作った TRGSW 暗号文 ${\rm BK}_i$ と TRLWE 暗号文 $d$ の外積を、
${\rm BK}_i \times d={\rm Dec}(d) \cdot {\rm BK}_i$ と定義します。

Gadget Decomposition は、 $\|d-\vec{v} \cdot H\|$ を最小化する $\vec{v}$ だったので、
$\vec{v}={\rm Dec}(d)$ と誤差 $(\epsilon_a(X),\epsilon_b(X))$ を用いて、
$\vec{v} \cdot H = d + (\epsilon_a(X),\epsilon_b(X))$ と書けます。

すると、
${\rm BK}_i \times d={\rm Dec}(d) \cdot {\rm BK}_i$
$=\vec{v} \cdot \left(\begin{array}{c} Z_1 \\ Z_2 \\ \vdots \\ Z_{2 \ell} \end{array}\right)+s_i \times \vec{v} \cdot H$
となり、左半分は内積を計算し、右半分は先ほどの式を代入すると、
$=\sum_{j=1}^{2 \ell} v_j \times Z_j+s_i \times (d + (\epsilon_a(X),\epsilon_b(X)))$
$=\sum_{j=1}^{2 \ell} v_j \times Z_j+s_i \times d + s_i \times (\epsilon_a(X),\epsilon_b(X))$
となり、３つの暗号文、
$c_1=\sum_{j=1}^{2 \ell} v_j \times Z_j$
$c_2=s_i \times d$
$c_3=s_i \times (\epsilon_a(X),\epsilon_b(X))$
の和を計算したことと同じになります。

TRLWE 暗号も加法準同型の性質を持つため、暗号文同士の和を取ると、
平文同士の和を取ったことになります。

このうち、 $c_1$ は $Z_j$ を何倍かして足したものなので、
平文 $\phi_{s'}(c_1)$ の期待値は 0 になります。

また $c_3$ を復号した $\phi_{s'}(c_3)$ は、
平文の絶対値の大きさをシステムパラメータで制約できるため、
この後の演算も含めて十分に小さくなるように設定します。

そうすると、 $\phi_{s'}({\rm BK}_i \times d)=\phi_{s'}(s_i \times d)$ となりますが、
$s_i$ が 0 であっても 1 であっても、計算結果は３つの暗号文の和になっているため、
単純な比較では $s_i$ がどちらなのか判別がつかないところが重要なポイントです。

さて、ここまでできればあとは簡単な話で、２つの平文 $\mu_0$ $\mu_1$ に対応する
TRLWE 暗号文 $d_0$ $d_1$ があるとして、 $d=d_1-d_0$ と代入して、
最後に $d_0$ を加算すれば、 ${\rm CMux}$ の完成です。

${\rm CMux}({\rm BK}_i,d_1,d_0)={\rm BK}_i \times (d_1-d_0)+d_0={\rm Dec}(d_1-d_0) \cdot {\rm BK}_i+d_0$

何をしているかというと、 $s_i$ が 0 なら $\mu_0$ 、1 なら $\mu_1$ の暗号文を、
復号することなく選択します。C 言語風に書けば $s_i?\mu_1:\mu_0$ です。

$\mu_0$ もしくは $\mu_1$ の暗号文を計算はできるけれども、どちらを選択したのかわからない。
それが ${\rm CMux}$ 関数です。 ${\rm BlindRotate}$ のコアとなる重要なパーツです。

${\rm BlindRotate}$ を計算する

前回説明した通り、平文 $\Phi$ を秘密鍵 $\vec{s}$ で暗号化された TLWE 暗号文 $c$ があるとします。

$X$ をかけ続けると位数 $2N$ の有限巡回群をなす、 $N$ 次の多項式、
$F(X)=\mu X^{N-1}+\mu X^{N-2}+\cdots+\mu X+\mu$
に $X^{\frac{N}{2}}$ を掛けた多項式をテストベクタ $T(X)=F(X) \cdot X^{\frac{N}{2}}$ とします。
なお、 $\mu=\frac{1}{8}$ とします。

$c=(\vec{a},b)$ として、 $\vec{a}$ の各要素と $b$ を $2N$ 倍してから四捨五入します。
そうして作った暗号文 $c'=(\vec{a'},b')$ を復号すると、
$\Phi'=\phi_s(c') \approx 2N \times \phi_s(c)=2N\Phi$ となります。
この時の誤差も後できちんと考慮する必要がありますが、
$N$ が大きくなるほど誤差は小さくなります。

テストベクタ $T(X)$ を平文とする自明な TRLWE 暗号文 $(0,T(X))$ を用意して、
$A_0=X^{-b'} \times (0, T(X))=(0,X^{-b'} \times T(X))$ とします。

以降、 ${\rm BK}_i$ を用いて、順番に $A_i={\rm CMux}({\rm BK}_i,X^{a'_i} A_{i-1},A_{i-1})$ を計算します。

すると、 $s_i$ が 0 の時はそのまま、つまり $X^0$ が、1 の時は $X^{a'_i}$ が順番に乗算されていくので、
$\phi_{s'}(A_0)=X^{-b'} T(X)$
$\phi_{s'}(A_1)=X^{s_1 a'_1 - b'} T(X)$
$\phi_{s'}(A_2)=X^{s_2 a'_2 + s_1 a'_1 - b'} T(X)$
と繰り返すと、
$\phi_{s'}(A_n)=X^{\sum_{i=1}^n s_i \times a'_i - b'} T(X)$
となり、 $X$ の肩に乗っているのは、復号関数 $\phi_s(c')$ と等しいので
$\phi_{s'}(A_n)=X^{-\phi_s(c')} T(X)$
となります。

要するに、 $A_n$ は、 $T(X)$ に $X^{-1}$ を $\Phi'$ 回乗算した多項式の暗号文となります。

この時、平文の多項式の定数項だけ見ると、
$\phi_s(c')$ が $\frac{N}{2}$ 以上、 $\frac{3N}{2}$ 未満の場合、つまり $\phi_s(c)$ が $\frac{1}{2} \pm \frac{1}{4}$ の場合、定数項は $\mu$ となり、
それ以外、つまり $\phi_s(c)$ が $\pm \frac{1}{4}$ の場合、定数項が $-\mu$ となるのは
前回説明した通りです。