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

はじめに

みなさんこんにちは。

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

前回は TFHE bootstrapping の第一段階、 ${\rm BlindRotate}$ で、
定数項として都合のいい値を持つ多項式を平文とする TRLWE 暗号文を作成しました。

今回はここから、定数項だけ取り出して TLWE 暗号文に変換します。

TRLWE 暗号文の復号を観察する

任意の TRLWE 暗号文は、次数を $N$ として、
$A(X)=\sum_{i=1}^N a_i X^{i-1}$
$B(X)=\sum_{i=1}^N b_i X^{i-1}$
と多項式を置いて、
$c=(A(X),B(X))$
という形で表現できます。

さて、これを秘密鍵 $\vec{s'}$ で復号してみましょう。
秘密鍵の多項式を $S'(X)=\sum_{i=1}^N s'_i X^{i-1}$ とおいて、
$\phi_{s'}(c)=B(X) - S'(X) \cdot A(X)$
$=\sum_{i=1}^N b_i X^{i-1} - \sum_{i=1}^N \sum_{j=1}^N a_i s'_j X^{(i+j-2)}$
と展開できます。

掛け算のひっ算をするとき、真ん中の段は平行四辺形になりますよね。
なので、真ん中で分割します。
$=\sum_{i=1}^N b_i X^{i-1} - \sum_{i=1}^N \sum_{j=i-1}^{N+i-2} a_i s'_{j-i+2} X^j$
$=\sum_{i=1}^N b_i X^{i-1} - \sum_{i=1}^N \sum_{j=i-1}^{N-1} a_i s'_{j-i+2} X^j - \sum_{i=1}^N \sum_{j=N}^{N+i-2} a_i s'_{j-i+2} X^j$
$=\sum_{j=1}^N b_j X^{j-1} - \sum_{j=0}^{N-1} \sum_{i=1}^{j+1} a_i s'_{j-i+2} X^j - \sum_{j=N}^{2N-2} \sum_{i=j-N+2}^N a_i s'_{j-i+2} X^j$
$=\sum_{j=0}^{N-1} b_{j+1} X^j - \sum_{j=0}^{N-1} \sum_{i=0}^{j} a_{i+1} s'_{j-i+1} X^j - \sum_{j=0}^{N-2} \sum_{i=j-N+1}^{-1} a_{i+N+1} s'_{j-i+1} X^{j+N}$
$=\sum_{j=0}^{N-2} b_{j+1} X^j + b_N X^{N-1} - \sum_{j=0}^{N-2} \sum_{i=0}^{j} a_{i+1} s'_{j-i+1} X^j - \sum_{i=0}^{N-1} a_{i+1} s'_{N-i} X^{N-1} - \sum_{j=0}^{N-2} \sum_{i=j-N+1}^{-1} a_{i+N+1} s'_{j-i+1} X^{j+N}$
$=\sum_{j=0}^{N-2} (b_{j+1} X^j - \sum_{i=0}^{j} a_{i+1} s'_{j-i+1} X^j - \sum_{i=j-N+1}^{-1} a_{i+N+1} s'_{j-i+1} X^{j+N}) + b_N X^{N-1} - \sum_{i=0}^{N-1} a_{i+1} s'_{N-i} X^{N-1}$

ここで、多項式環の剰余環だったので、 $(X^N+1)$ で割った余りを求めます。
$=\sum_{j=0}^{N-2} (b_{j+1} X^j - \sum_{i=0}^{j} a_{i+1} s'_{j-i+1} X^j + \sum_{i=j-N+1}^{-1} a_{i+N+1} s'_{j-i+1} X^j) + b_N X^{N-1} - \sum_{i=0}^{N-1} a_{i+1} s'_{N-i} X^{N-1}$
$=\sum_{j=0}^{N-2} (b_{j+1} - \sum_{i=0}^{j} a_{i+1} s'_{j-i+1} + \sum_{i=j-N+1}^{-1} a_{i+N+1} s'_{j-i+1}) X^j + (b_N - \sum_{i=0}^{N-1} a_{i+1} s'_{N-i}) X^{N-1}$

さらに、 $a'_i=\left\{ \begin{array}{ll} a_i & (i \geq 1) \\ -a_{i+N} & (otherwise) \end{array} \right.$ と置くと、
$=\sum_{j=0}^{N-2} (b_{j+1} - \sum_{i=0}^{j} a'_{i+1} s'_{j-i+1} - \sum_{i=j-N+1}^{-1} a'_{i+1} s'_{j-i+1}) X^j + (b_N - \sum_{i=0}^{N-1} a'_{i+1} s'_{N-i}) X^{N-1}$
$=\sum_{j=0}^{N-2} (b_{j+1} - \sum_{i=j-N+1}^{j} a'_{i+1} s'_{j-i+1}) X^j + (b_N - \sum_{i=0}^{N-1} a_{i+1} s'_{N-i}) X^{N-1}$
$=\sum_{j=0}^{N-2} (b_{j+1} - \sum_{i=0}^{N-1} a'_{i+j-N+2} s'_{N-i}) X^j + (b_N - \sum_{i=0}^{N-1} a_{i+1} s'_{N-i}) X^{N-1}$
$=\sum_{j=0}^{N-1} (b_{j+1} - \sum_{i=0}^{N-1} a'_{i+j-N+2} s'_{N-i}) X^j$

これで、平文の多項式の各項の係数が求まりました。
$\phi_{s'}(c)=\sum_{j=0}^{N-1} (b_{j+1} - \sum_{i=0}^{N-1} a'_{i+j-N+2} s'_{N-i}) X^j$

で、欲しかったのは定数項の係数なので、 $j=0$ の時の係数を取り出します。
$b_1 - \sum_{i=0}^{N-1} a'_{i-N+2} s'_{N-i}$

$a''_i=a'_{-i+2}$ とおけば、
$b_1 - \sum_{i=0}^{N-1} a''_{N-i} s'_{N-i}$
$=b_1 - \sum_{i=0}^{N-1} a''_i s'_i=b_1-\vec{s'} \cdot \vec{a''}=\phi_{s'}(\vec{a''},b_1)$

という感じで TLWE 暗号の復号関数に変形できます。

つまり、前回の出力結果 $c_r=(A(X),B(X))$ から、係数を
$a''_i=\left\{ \begin{array}{ll} a_1 & (i = 1) \\ -a_{-i+N+2} & (otherwise) \end{array} \right.$ と取り出せば、
$(\vec{a''},b_1)$ が、元の TRLWE 暗号文に対応する平文多項式の、
定数項と同じ値を平文として持つ新しい TLWE 暗号文となるわけです。

これを ${\rm SampleExtract}$ と元論文では呼んでいます。

この段階で、 $-\mu$ もしくは $\mu$ の暗号文が得られているので、
$\mu$ の自明な暗号文 $(0,\mu)$ を加えて、 $c_s=(\vec{a''},b_1)+(0,\mu)$
をこのステップの出力とします。すると、平文は $0$ もしくは $\frac{1}{4}$ となります。