完全準同型暗号の論文を読む - 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}
こんな感じになります。

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

公開鍵スイッチング

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

これを1つずつそれぞれ、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'_ij に対して定数なのでくくりだして、
=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} から2つの暗号文を引く、
つまり 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))

など。実際どういう値になるのかはみなさまでご確認ください。

まとめ

今回は TFHE bootstrapping の最後のステップ、公開鍵スイッチングについて解説して、
完全準同型暗号を完成させました。

TFHE 元論文には、他にもいろいろなテクニックが書かれているため、
読んでみると面白いですよ。量はすごくたくさんありますが。

ということで、今回の連載はこれで終了にしたいと思います。

みなさん、お付き合いいただき、ありがとうございました。
ご質問、ご意見等ありましたらお気軽にリプライください。
それではまた。