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

はじめに

みなさんこんにちは。

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

前回は、TFHE bootstrapping の第二段階、 ${\rm SampleExtract}$ を用いて TLWE 暗号文を計算しました。
しかし、入力されたデータと鍵が異なります。それを修正するのが今回の記事となります。

ていうかなんでそもそも違う鍵を使ったの？

$\vec{s}=\vec{s'}$ ならここで話は終わっていたのですが、
残念ながらそうはいきません。TLWE と TRGSW ではビット長と暗号強度に
差があるからです。ある程度揃えるためには、違う長さの鍵を使うしかありません。

というわけで、 $\vec{s} \neq \vec{s'}$ ということで頑張りましょう。
TFHE bootstrapping の最後のステップです。

キースイッチングキー

NAND 演算に使う TLWE 暗号文の鍵 $\vec{s}$ は $n$ 次のベクトルです。
これを使って、bootstrapping key を作成したときの $N$ 次のベクトルの鍵、
$\vec{s'}$ を暗号化します。

ちょっとコツがあって、 $s'_i \times 2^{-1}$ $s'_i \times 2^{-2}$ $s'_i \times 2^{-3}$ ... と、 $\mathbb{T}$ の要素、
0 から 1 の実数を二進数で表現した時の各桁にずらした値として
暗号化します。秘密鍵は先ほどお話しした通り $\vec{s}$ です。

この時の「桁数」 $t$ はシステムパラメータとして、最終的な誤差に影響を与えるため、
設計時には調整が必要です。

試しに $\vec{s}$ 鍵で復号すると、
$\phi_s({\rm KS}_{i,j})=s'_i \times 2^{-j}$
こんな感じになります。

これを、キースイッチングキーと呼びます。

公開関数的な鍵スイッチング（Public Functional Key Switching)

さて、前回の計算結果である TLWE 暗号文 $c_s=(\vec{a},b)$ は $\vec{s'}$ で暗号化された、
$0$ もしくは $\frac{1}{4}$ の値です。
$\vec{a}$ の要素数は、 $\vec{s'}$ と同じく $N$ 個です。

これを１つずつそれぞれ、 $t$ bit の固定小数に変換します。
すると、この形式で書けます。 $a_i \approx \sum_{j=1}^t a_{i,j} \times 2^{-j}$
この段階で誤差が増えますが、以前と同様、システムパラメータで絶対値の最大値を制約できます。

で、鍵スイッチングの本体、以下の暗号文を計算します。
$c_o=(\vec{0},b)-\sum_{i=1}^{N} \sum_{j=1}^t a_{i,j} \times {\rm KS}_{i,j}$

何をしているのか、復号してみるとわかります。
$\phi_s(c_o)=\phi_s( (\vec{0},b) )-\sum_{i=1}^{N} \sum_{j=1}^t a_{i,j} \times \phi_s({\rm KS}_{i,j})$
しれっと $\phi$ 関数が中に入っていきますが、線形性という性質があるので問題ないです。
で、 $b$ の項は自明な暗号文なので $b$ になり、前章で試しに復号した結果を代入すると、
$\phi_s(c_o)=b-\sum_{i=1}^{N} \sum_{j=1}^t a_{i,j} \times s'_i \times 2^{-j}$
$=b-\sum_{i=1}^{N} \sum_{j=1}^t s'_i \times a_{i,j} \times 2^{-j}$
で、 $s'_i$ は $j$ に対して定数なのでくくりだして、
$=b-\sum_{i=1}^{N} s'_i \sum_{j=1}^t a_{i,j} \times 2^{-j}$
先ほど固定小数に分解したときの式を代入します。
$\approx b-\sum_{i=1}^{N} s'_i \times a_i = \phi_{s'}( (\vec{a},b) )=\phi_{s'}(c_s)$

というわけで、 $\phi_s(c_o) \approx \phi_{s'}(c_s)$ となり、
めでたく鍵の切り替えができました。

実用には必要ないので、公開関数の適用については割愛します。

計算結果について

この段階で、TLWE 暗号文 $c_o$ は、bootstrapping の入力とした
TLWE 暗号文 $c$ と同じ秘密鍵で暗号化されており、
$\phi_s(c)$ が $\frac{1}{2} \pm \frac{1}{4}$ の場合は $\phi_s(c_o)$ は $\frac{1}{4}$ 、
それ以外、つまり $\phi_s(c)$ が $\pm \frac{1}{4}$ の場合、 $\phi_s(c_o)$ は $0$
となっています。

そして、平文に乗っている誤差は、TLWE 暗号文の整数化で加わる誤差と、CMux で加わる誤差、
公開鍵スイッチングで固定小数化した時の誤差など、
すべてシステムパラメータで制約できるものなので、
全部ひっくるめて誤差が $\pm \frac{1}{16}$ となるように調整します。

すると、以前説明した通り、自明な暗号文として $\frac{5}{8}$ から２つの暗号文を引く、
つまり $c=(\vec{0},\frac{5}{8})-c_1-c_2$ を計算すると、その平文は以下のようになります。

$\phi_s(c_1)$	$\phi_s(c_2)$	$\phi_s(c)$
$\pm \frac{1}{16}$	$\pm \frac{1}{16}$	$\frac{5 \pm 1}{8}$
$\frac{1}{4} \pm \frac{1}{16}$	$\pm \frac{1}{16}$	$\frac{3 \pm 1}{8}$
$\pm \frac{1}{16}$	$\frac{1}{4} \pm \frac{1}{16}$	$\frac{3 \pm 1}{8}$
$\frac{1}{4} \pm \frac{1}{16}$	$\frac{1}{4} \pm \frac{1}{16}$	$\frac{1 \pm 1}{8}$

この $c$ を TFHE bootstrapping に入力すれば、何度でも NAND 演算ができます。

これで、完全準同型暗号の完成です。

NAND 以外の論理演算

最初に説明した通り、 $\{{\rm NAND}\}$ は完備集合なので、これだけあればどんな演算も
できるのですが、他の論理演算もできれば便利だし計算量も減るので、
元論文ではいくつか提示されています。

${\rm NOT}(c)=(0,\frac{1}{4})-c$ これは誤差が増えないため bootstrapping は不要です。
${\rm AND}(c_1,c_2)={\rm bootstrapping}( (0,-\frac{1}{8})+c_1+c_2)$
${\rm OR}(c_1,c_2)={\rm bootstrapping}( (0,\frac{1}{8})+c_1+c_2)$
${\rm XOR}(c_1,c_2)={\rm bootstrapping}(2 \times (c_1-c_2))$