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

はじめに

みなさんこんにちは。

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

前回は、TFHE で用いる暗号アルゴリズムを３つ紹介しました。
また、その途中で Gadget Decomposition というものについても触れました。

今回は、これらを用いてどんな風に完全準同型暗号を構成するのかを、
お話していこうと思います。

最終的に作りたいもの

前回解説した TLWE は、\mathbb{T} を平文として持ちます。
つまり、0 以上 1 未満の実数が平文となるわけです。

そこで、0 と 0 以外の数（便宜上 \mu と呼びます）のどちらかを
暗号化した暗号文同士の演算、NAND を実現します。

NAND とは、論理回路で出てくる NAND 回路と同じ演算で、
\mu と \mu を入力とした時だけ 0 となり、それ以外では \mu となる演算です。

なぜ NAND かというと、\{{\rm NAND}\} という感じに NAND だけを含む集合は、
「完備集合」と呼ばれており、「どんな演算も実現可能」な演算の集合だからです。

もちろん、加算も乗算も、NAND 演算だけの組み合わせで実現可能です。
これで完全準同型暗号を構成します。

TLWE 暗号文同士の NAND 演算

\mu は 0 と区別できれば何でもいいのですが、この後の設計上の都合から、
\mu=\frac{1}{4} とします。TLWE は平文に誤差を含むため、
その最大誤差を \pm \frac{1}{16} とします。

すると、前回説明した通り、TLWE は加法準同型暗号なので、引き算もできます。
そして自明な暗号文（暗号化されていない）として \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}

というわけで、\pm \frac{1}{4} の範囲の平文を \pm \frac{1}{16} に、\frac{1}{2} \pm \frac{1}{4} の範囲の平文を \frac{1}{4} \pm \frac{1}{16} に、
つまり元の入力の値域に戻すことができれば、出力をさらに別の NAND 演算の入力とし、
無制限に何度でも NAND 演算ができるようになります。
（平文は \mathbb{T} なので、0 と 1 がつながっていることに注意！）

このように、誤差を小さくする操作を bootstrapping と呼び、
「こんなものあったらいいね！」という構想自体は完全準同型暗号の研究の初期からあり、
様々な手法がかなり古くから提案されてきました。
しかし、bootstrapping に必要なデータが 1GB ほどになったり、計算量が多すぎて、
なかなか実用には程遠い……と思われていました。

それを劇的に改善したのが、TFHE という位置づけになります。
具体的には、bootstrapping に必要なデータが 16MB、
処理時間は 1 コア CPU で 13ms と論文にあります。

TFHE の bootstrapping

TFHE では、\pm \frac{1}{4} の範囲の平文を \pm \frac{1}{16} に、\frac{1}{2} \pm \frac{1}{4} の範囲の平文を \frac{1}{4} \pm \frac{1}{16} にするために、
３段階の処理を行います。

詳細な処理手順については次回以降、順番に解説しますが、まずは全体の流れを把握するため、
多少強引ですが、「こんな便利な関数があったら」という感じで話を進めます。

第一段階：{\rm BlindRotate}

多項式環の剰余環の話をしたときに、
F(X)=\mu X^{n-1}+\mu X^{n-2}+\cdots+\mu X+\mu
という多項式は、X をかける操作を続けると、位数 2n の有限巡回群をなす、
というお話をしました。

元論文中ではこれにさらに X^{\frac{n}{2}} を掛けた多項式 T(X)=F(X) \cdot X^{\frac{n}{2}} を
「テストベクタ」と呼んでいます。なお、\mu=\frac{1}{8} としておきます。
これで後でつじつまが合います。

で、入力される TLWE 暗号文は先ほど c としたので、
その秘密鍵、\vec{s} の要素をそれぞれ別の秘密鍵 \vec{s'} を用いて、
TRGSW で暗号化した暗号文を予め用意しておきます。

c=(\vec{a},b) なので、各要素を 2n 倍して四捨五入して整数化した c'=(\vec{a'},b') を作ると、
\phi_s(c') \approx 2n \times \phi_s(c) となります。これは \phi_s が線形性という性質を
持っているからですが、平たく言えば、大体 2n 倍の値で計算すれば、
出力も大体 2n 倍になるよね、って感じの話です。

そして、テストベクタ T(X) を平文とする自明な TRLWE 暗号文 t=(0,T(X)) から、
X^{-\phi_s(c')} を乗算した TRLWE 暗号文を「復号することなく」計算する魔法のような関数、
c_r={\rm BlindRotate}(t,c') を計算します。この中身は次回解説します。

すると、その TRLWE 暗号文 c_r を復号して出てくる多項式 \phi_{s'}(c_r) を見ると、
下位の項から数えて \frac{n}{2}-\phi_s(c') 個の項は、係数が -\mu となり、
負になった場合、さらに上の項から順に係数が -\mu になります。

ということは、この TRLWE 暗号文を復号して、平文の定数項を見ると、
\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 となります。

この平文の定数項、都合がいいですね。というわけで、自明な TRLWE 暗号文 (0,\mu) を加えて、
定数項を 0 もしくは 2\mu=\frac{1}{4} にしてから次の段階へ進みます。

第二段階：{\rm SampleExtract}

TRLWE 暗号文 c_r の平文多項式の定数項が、都合よく 0 か \frac{1}{4} になりました。
なので、これまた「復号することなく」、定数項を平文とする TLWE 暗号文に変換します。

これを、c_s={\rm SampleExtract}(c_r) と呼びます。これも次回以降説明します。

第三段階：公開関数的な鍵スイッチング（Public Functional Key Switching)

元の TLWE 暗号文 c は秘密鍵 \vec{s} で暗号化されていますが、
{\rm SampleExtract} で出てくる TLWE 暗号文 c_s は、
\vec{s} を TRGSW で暗号化した時に使った鍵、\vec{s'} で暗号化されています。

そこで、平文を変えることなく、鍵だけ差し替えます。
これも、復号することなく行います。

論文では「秘匿されていない関数を適用しつつ、鍵スイッチングを行う手法」として、
定義されています。実際にはその関数としては恒等変換（f(x)=x）を用いると、
平文を変えずに鍵が異なる暗号文を得ることができます。

ここまで処理を行うと、元と同じ秘密鍵 \vec{s} で暗号化された TLWE 暗号文に戻っており、
平文は \pm \frac{1}{4} の範囲なら 0 に、\frac{1}{2} \pm \frac{1}{4} の範囲なら \frac{1}{4} になっています。
また、誤差の最大値は c に依存せず、システムパラメータによって固定された値になるため、
誤差の最大値が \pm \frac{1}{16} となるようにシステムパラメータを設定します。

これで、何度でも NAND 演算ができるようになり、
加算も乗算も、それどころかすべての演算が可能になるのです。

まとめ

今回は、少し長めになりましたが、TFHE の構成の全体像をまとめました。
次回以降は、各段階で使用した道具について順番に見ていきます。

今回はここまで。
ご質問、ご意見等ありましたらお気軽にリプライください。