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

はじめに

みなさんこんにちは。

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

前回は TFHE の暗号システムで用いる道具をいくつかご紹介しました。
TFHE では、3つの暗号アルゴリズムを巧みに組み合わせて構成するので、
今回はその3つをご紹介したいと思います。

基本の暗号文 TLWE

\mathbb{T} 上の要素として、一様分布な乱数を N 個集めたベクトル
\vec{a} を用意します。 \{0, 1\} の二値を N 個集めた秘密鍵 \vec{s} を用意します。平均値が平文 \mu
分散が事前に決めた \alpha になるようなガウス分布の乱数を e としたとき、
( \vec{a}, \vec{s} \cdot \vec{a} + e) の組を TLWE 暗号の暗号文の1例とします。

乱数を持ちいて暗号化するため、同一の秘密鍵と平文に対して、
いろいろなバリエーションの暗号文が対応します。

なお、 \phi_s( (\vec{a},b) )=b-\vec{s} \cdot \vec{a}=e は復号する関数として働きます。

元論文では、確率空間全体で定義して議論を進めていますが、
それは誤差成分の分散などを計算したいためであって、
実際の実装ではその分布の中の1サンプルを採集すれば OK です。

さらに、元論文では \phi_s 関数の性質についていろいろ述べられていますが、
特筆しておくべきことは、(\vec{0},\mu) は自明な暗号文(暗号化されていない)で
あることに留意してください。
なぜなら、\phi_s( (\vec{0},\mu) )=\mu-\vec{s} \cdot \vec{0}=\mu だからです。

また、TLWE は加法準同型暗号でもあります。
2つの TLWE 暗号文 (\vec{a},b)(\vec{a'},b') をそのまま足して、
(\vec{a}+\vec{a'},b+b') としたものを \phi_s に入力すると、
\phi_s( (\vec{a}+\vec{a'},b+b') )=(b+b')-\vec{s} \cdot (\vec{a}+\vec{a'})
=(b-\vec{s} \cdot \vec{a})+(b'-\vec{s} \cdot \vec{a'})
=\phi_s( (\vec{a},b) )+\phi_s( (\vec{a'},b') )
となるため、復号すると2つの平文の和が出てきます。
ただし、平文が \mathbb{T} なので、0.6+0.6=1.2 ではなく 0.2 となることに要注意です。
これも重要ですので忘れないようにしていただきたく。

TFHE では、「TLWE 暗号文で加法演算を行って、Gate Bootstrapping を行う。」ということを
繰り返していくことで様々な演算を実現します。

多項式環を用いた TRLWE

環 (ring) で構成したバージョンの TLEW なので、頭文字の R が加わっています。

前回の記事で紹介した \frac{\mathbb{T}[X]}{(X^n+1)} の環の元をランダムに選びます。
実際には、n-1多項式の係数 n 個を \mathbb{T} 上から一様分布な乱数で選出して作ります。
多項式の次数が n-1 なら剰余とか考えなくていいので(X^n+1 で割れないので)、
これを多項式 a(X) とします。

秘密鍵をまた \{0, 1\} の二値から n 個集めて、
秘密鍵多項式 s(X)=s_{n-1} X^{n-1}+s_{n-2} X^{n-2}+\cdots+s_1 X+s_0 を組み立てます。

n 個の乱数 e_i を、平均値が平文 \mu_i になり、分散が \alpha となるガウス分布の乱数として、
これらから多項式 e(X)=e_{n-1} X^{n-1}+e_{n-2} X^{n-2}+\cdots+e_1 X+e_0 を組み立てます。

多項式 s(X) \cdot a(X)+e(X)=f(X)(X^n+1)+b(X) と分解した b(X) を計算して、
(a(X), b(X)) を、TRLWE 暗号の暗号文の1例とします。

こちらも TLWE と同様に乱数を用いて暗号化するため、同一の秘密鍵、平文に対して
無数の暗号文が対応します。

また、TLWE と同様に \phi_s((a(X),b(X)))=b(X)-s(X) \cdot a(X)+g(X)(X^n+1) として、
\phi_s\frac{\mathbb{T}[X]}{(X^n+1)} の元となるように g(X) を定めたものが、復号関数として働きます。

さらに、加法準同型暗号なのも TLWE と同じです。

これは、Gate Bootstrapping の途中で一時的に使うだけですが、
前回説明した、特殊な多項式が有限巡回群をなす、
という性質を利用するため、とても重要な役割を果たします。

Gadget Decomposition

これは暗号のアルゴリズムではないですが、次で説明する TGSW で必要なので先に説明します。

GSW の論文で {\rm BitDecomp} 関数を解説しましたが、それの円周群 \mathbb{T} バージョンです。
TRLWE 暗号文のサンプルで用いている多項式の係数である、円周群の要素は、
0 以上 1 未満の実数なので、小数部分しかありません。
これを二進数表記で、何ビットかずつに分解する操作を、Gadget Decomposition、
{\rm Dec} と定義します。

例えば、小さなサイズで例を書いてみます。
TRLWE 暗号文の多項式の次数を n=2 として、分割の 1 単位を {\rm Bg}=2^2 で、
\ell=3 要素に分解します。この時、各要素は -\frac{\rm Bg}{2} から \frac{\rm Bg}{2} の間に入るようにします。

TRLWE 暗号文は、2 つの多項式の組み合わせでしたので、
これを多項式を要素とする 2 次元のベクトルとみなします。
c=\{0.75X^2+0.125X+0.5,0.25X^2+0.5X+0.375\} と書けます。

これを分解すると円周群上では 0.75=-0.25 なので
c=\{-0.25X^2+0.125X+0.5,0.25X^2+0.5X+(0.25+0.125)\}
=\{0.25 \times (-X^2+2) + 0.25^2 \times 2X + 0.25^3 \times 0, 0.25 \times (X^2+2X+1) + 0.25^2 \times 2 + 0.25^3 \times 0\}
と分解できるため、{\rm Dec}(c)=\{-X^2+2,2X,0,X^2+2X+1,2,0\} となります。

逆に、ベクトルから暗号文に戻す作用素 H も定義します。

今回の例だと、
H=\left(\begin{array}{cc} 0.25 & 0 \\ 0.25^2 & 0 \\ 0.25^3 & 0 \\ 0 & 0.25 \\ 0 & 0.25^2 \\ 0 & 0.25^3 \end{array}\right)
という行列が逆変換の作用素です。
{\rm Dec}(c) \cdot H=c に戻ることが確認できると思います。

今回はキリのいい値を使ったので厳密に戻りますが、実際には下の方のビットは
四捨五入して丸めます。
つまり、TRLWE 暗号文 c に対して、\|c-\vec{v} \cdot H\| が最小化となる \vec{v} を得るのが
Gadget Decomposition となります。

この概念を利用して、次の TGSW 暗号を定義します。

GSW の拡張?TRGSW。

Z_i を、平文ベクトルがすべて 0 の TRLWE 暗号文とします。
つまり、e(X) の係数すべてが平均値 0 となり、分散は \alpha となる多項式でできた
Z=(a(X),b(X)) という暗号文です。

これを 2 \ell 個、生成して、平文 \mu を以下のように暗号化します。
C=\left(\begin{array}{c} Z_1 \\ Z_2 \\ \vdots \\ Z_{2 \ell} \end{array}\right)+\mu \times H
これを、TRGSW 暗号文と定義します。

型が若干あってないような感じがしますが、TLWE 暗号文を多項式を要素とする 2 次元のベクトルと
みなせば、まぁあっていないこともないでしょう。

復号の方法は元論文でも言及されていません。数式的には形式上 {\rm msg}(C) として書き表しますが、
実際に計算することはありません。

これは、Gate Bootstrapping に用いるデータとして、秘密鍵を暗号化しておくために使います。
Bootstrapping Key とも呼びます。なぜ秘密鍵を TGSW で暗号化しておくか、
というのは追々解説します。

まとめ

今回は、TFHE で用いる暗号アルゴリズムを3つ、ご紹介しました。
TFHE では、これらを組み合わせて完全準同型暗号を構成します。
次回はこれらを使って TFHE の構成を見ていきます。

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