はじめに
みなさんこんにちは。
VIPPOOL でエンジニアをやっています、星月です。
前回は、TFHE bootstrapping の第二段階、 を用いて TLWE 暗号文を計算しました。
しかし、入力されたデータと鍵が異なります。それを修正するのが今回の記事となります。
ていうかなんでそもそも違う鍵を使ったの?
ならここで話は終わっていたのですが、
残念ながらそうはいきません。TLWE と TRGSW ではビット長と暗号強度に
差があるからです。ある程度揃えるためには、違う長さの鍵を使うしかありません。
というわけで、 ということで頑張りましょう。
TFHE bootstrapping の最後のステップです。
キースイッチングキー
NAND 演算に使う TLWE 暗号文の鍵 は 次のベクトルです。
これを使って、bootstrapping key を作成したときの 次のベクトルの鍵、
を暗号化します。
ちょっとコツがあって、 ... と、 の要素、
0 から 1 の実数を二進数で表現した時の各桁にずらした値として
暗号化します。秘密鍵は先ほどお話しした通り です。
この時の「桁数」 はシステムパラメータとして、最終的な誤差に影響を与えるため、
設計時には調整が必要です。
試しに 鍵で復号すると、
こんな感じになります。
これを、キースイッチングキーと呼びます。
公開関数的な鍵スイッチング(Public Functional Key Switching)
さて、前回の計算結果である TLWE 暗号文 は で暗号化された、
もしくは の値です。
の要素数は、 と同じく 個です。
これを1つずつそれぞれ、 bit の固定小数に変換します。
すると、この形式で書けます。
この段階で誤差が増えますが、以前と同様、システムパラメータで絶対値の最大値を制約できます。
で、鍵スイッチングの本体、以下の暗号文を計算します。
何をしているのか、復号してみるとわかります。
しれっと 関数が中に入っていきますが、線形性という性質があるので問題ないです。
で、 の項は自明な暗号文なので になり、前章で試しに復号した結果を代入すると、
で、 は に対して定数なのでくくりだして、
先ほど固定小数に分解したときの式を代入します。
というわけで、 となり、
めでたく鍵の切り替えができました。
実用には必要ないので、公開関数の適用については割愛します。
計算結果について
この段階で、TLWE 暗号文 は、bootstrapping の入力とした
TLWE 暗号文 と同じ秘密鍵で暗号化されており、
が の場合は は 、
それ以外、つまり が の場合、 は
となっています。
そして、平文に乗っている誤差は、TLWE 暗号文の整数化で加わる誤差と、CMux で加わる誤差、
公開鍵スイッチングで固定小数化した時の誤差など、
すべてシステムパラメータで制約できるものなので、
全部ひっくるめて誤差が となるように調整します。
すると、以前説明した通り、自明な暗号文として から2つの暗号文を引く、
つまり を計算すると、その平文は以下のようになります。
この を TFHE bootstrapping に入力すれば、何度でも NAND 演算ができます。
これで、完全準同型暗号の完成です。
NAND 以外の論理演算
最初に説明した通り、 は完備集合なので、これだけあればどんな演算も
できるのですが、他の論理演算もできれば便利だし計算量も減るので、
元論文ではいくつか提示されています。
これは誤差が増えないため bootstrapping は不要です。
など。実際どういう値になるのかはみなさまでご確認ください。
まとめ
今回は TFHE bootstrapping の最後のステップ、公開鍵スイッチングについて解説して、
完全準同型暗号を完成させました。
TFHE 元論文には、他にもいろいろなテクニックが書かれているため、
読んでみると面白いですよ。量はすごくたくさんありますが。
ということで、今回の連載はこれで終了にしたいと思います。
みなさん、お付き合いいただき、ありがとうございました。
ご質問、ご意見等ありましたらお気軽にリプライください。
それではまた。