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

はじめに

みなさんこんにちは。

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

前回は GSW で提案された完全準同型暗号の大まかな仕組みについて説明しました。
今回はその問題点と解決方法について検討していきます。

おさらい - GSW の原型

同じ固有ベクトルを持つ行列が２つあるとき、その２つの行列の和と積は、
固有ベクトルが変わらずに、固有値が和や積になるという性質がありました。

それを利用して、 $Av=\lambda v+e$ と誤差を加えることで LWE 問題として、
暗号文として解読できないようにしました。

問題点：誤差が累積していく

同じ秘密鍵（固有ベクトル）を持つ暗号文 $A$ と $A'$ があるとき、
平文（固有値）は $\lambda$ と $\omega$ としておきます。それぞれの誤差は $e_1$ $e_2$ とします。

$A+A'$ を復号すると
$(A+A')v=Av+A'v=\lambda v+e_1+\omega v+e_2=(\lambda+\omega)v+(e_1+e_2)$ となり、
誤差は $e_1+e_2$ となります。

$A \cdot A'$ を復号すると（途中計算は省略します。元論文を参照してください）、
$\lambda \omega v$ に加わる誤差は、 $v$ の次数を $N$ 、 $e$ の絶対値の最大値を $B$ として、
最大で $(N+1)B^2$ になります。

これはどういうことかというと、例えば多項式の項 $x^m$ を計算しようとすると、
誤差は最大で $(N+1)^{m-1} B^m$ まで大きくなるということです。

誤差の累積は LWE 問題ベースの完全準同型暗号では必ず付きまとう問題で、
過去に様々な解決策が提示されてきましたが、GSW では一風変わった解決策を取ります。

解決策の準備 - ${\rm BitDecomp}$ と ${\rm BitDecomp}^{-1}$

これまで、行列の要素は実数体で考えていましたが、
実数体と準同型である、有限体を要素にもつ行列で考えます。

その時、例えば、位数 13 の有限体であれば、せいぜい 4 bit あれば表現できます。
位数 $q$ の有限体の要素を表すのに必要なビット数は $L=\lfloor \log_2 q \rfloor + 1$ で求められます。
好きな自然数 $k$ 倍の大きさ $N=kL$ を行列やベクトルの次数とします。

$k$ 次元の横方向ベクトル $a' = (a_0, a_1, \cdots, a_{k-1})$ のそれぞれの要素を２進数で書き直す操作を
${\rm BitDecomp}(a')$ と定義します。

例えば、位数 $q=13$ の場合、 $L=\lfloor 3.7 \rfloor + 1 = 4$ となります。 $k$ はとりあえず 3 としましょう。
3 次元横ベクトル $a' = ( 10, 8, 4 )$ を 12 次元横ベクトル
$a = ( 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0 )$ と分解します。
$L=4$ 要素単位で２進数が逆方向に $k=3$ つ並んでいます。

この逆の操作を ${\rm BitDecomp}^{-1}(a)$ とします。

${\rm BitDecomp}$ と ${\rm BitDecomp}^{-1}$ の性質

秘密鍵ベクトル（今回は固有ベクトルではない／縦ベクトル）を、 $k$ 個の 0 か 1 で設定します。
とりあえず $s = (s_0, s_1, \cdots, s_{k-1})^{\mathrm{T}}$ としておきます。

$L$ bit 分の 2 のべき数を $k$ 個並べた縦ベクトルを
$b_{iL+j} = 2^j, i \in \{ 0, \cdots, k-1 \}, j \in \{ 0, \cdots, L-1 \}$ とします。
今回の例だと $b=(1, 2, 4, 8, 1, 2, 4, 8, 1, 2, 4, 8)^{\mathrm{T}}$ となりますね。

$v_{iL+j}=b_{iL+j} \times s_i$ とした $v$ を固有ベクトルとします。

すると、
$a \cdot v = \sum_{i=0}^{k-1} \sum_{j=0}^{L-1} s_i \times a_{iL+j} \times 2^j$
$= \sum_{i=0}^{k-1} s_i \sum_{j=0}^{L-1} a_{iL+j} \times 2^j$
$= \sum_{i=0}^{k-1} s_i \times a'_i = a' \cdot s$
というわけで、 $a \cdot v = a' \cdot s$ および ${\rm BitDecomp}(a') \cdot v = a' \cdot s$ が成り立ちます。

ここで、左辺にのみ $a'={\rm BitDecomp}^{-1}(a)$ を代入すると、
${\rm BitDecomp}({\rm BitDecomp}^{-1}(a)) \cdot v = a' \cdot s$
で、前段落前半の式の右辺が同じなので、 ${\rm BitDecomp}({\rm BitDecomp}^{-1}(a)) \cdot v = a \cdot v$ です。

何を言っているかというと、 ${\rm BitDecomp}({\rm BitDecomp}^{-1}(a))$ という処理を加えても、
$v$ との内積は変わらない。という話になります。

この ${\rm BitDecomp}({\rm BitDecomp}^{-1}(a))$ を、元論文では ${\rm Flatten}(a)$ と書いています。

${\rm Flatten}(a)$ の意味するところ

${\rm BitDecomp}^{-1}(a)$ は、 $a$ の横ベクトルを２進数と解釈して $k$ 個の値にまとめ上げる処理でした。
${\rm BitDecomp}(a')$ は、 $a'$ の横ベクトルを２進数として書き直す処理でした。

つまり、例えば $L=4, k=2$ としたとき、 $a = ( 2, 0, 3, 0, 5, 0, 0, 1 )$ は、
${\rm BitDecomp}^{-1}(a) = ( 14, 13 )$ となり、 ${\rm Flatten}(a) = ( 0, 1, 1, 1, 1, 0, 1, 1 )$ ということです。
２進数として解釈してまとめあげて、再度２進数として書き直す。

この処理を行っても、固有ベクトル $v$ との内積の値は変わらない。
$Av=\lambda v+e$ ならば、 $Av={\rm Flatten}(A)v=\lambda v+e$ なのです。

それなのに、行列の要素はすべて 0 もしくは 1 になります。
これのおかげで嬉しいことがあります。

で、 ${\rm Flatten}(a)$ は何が嬉しいの？

超うれしいです。今回の前半で、誤差の累積の話をしましたが、
乗算の時、 $x^m$ を計算すると誤差は最大で $(N+1)^{m-1} B^m$ となりましたが、
乗算のたびに Flatten を行うことで、 $(N+1)^{m-1} B$ に抑えることができます。

$B$ の階乗が消えましたね。これは行列の要素が 0 もしくは 1 に限定されたおかげです。
$B$ は $e$ の要素の絶対値の最大値なので、 $e$ の要素の絶対値を大きくしても
誤差が指数関数的に増えていくことはなくなるわけです。

前回の内容から、 $\frac{(N+1)^{m-1} B}{v_i}$ が、-0.5～0.5 の間に収まっていることが
復号できる条件なので、極力小さくするため $i$ には $L$ の倍数 - 1 を選びます。
つまり、位数 $q$ を表す２進数の最上位ビットです。これは $k$ 個あるはずなので、
その中からさらに $s_i$ が 1 であるもの、つまり $v_i=2^{L-1}$ を選ぶことにします。