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

はじめに

みなさんこんにちは。

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

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

基本の暗号文 TLWE

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

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

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

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

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

また、TLWE は加法準同型暗号でもあります。
２つの 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') )$
となるため、復号すると２つの平文の和が出てきます。
ただし、平文が $\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 暗号の暗号文の１例とします。

こちらも 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 暗号文と定義します。