目次
- (完全)準同型暗号の最前線1（入門編)
- (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #1 TLWE
- (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #2 TRLWE & SampleExtarctIndex←イマココ
- (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #3 TRGSW & CMUX
- (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #4 Blind Rotate
- (完全)準同型暗号の最前線２（原理編）: TFHEの原理 #5 Identity Key Switching
初めに
有限要素法のことを考えていたら光陰矢の如しになっている近頃です。今回はTRLWEの話をします。基本的には次回のTRGSWが一番難しいので、今回まではそのための準備という塩梅ですね。
全体の中での位置づけ
赤くなっているところに相当することを説明する。
TRLWEとは
Torus Ring Learning With Errorの略。つまり、Torus版のRing版LWEというような意味。ここでいうRingというのは多項式環のことなので、まずはその話からする。
多項式環とは
剰余環を多項式に拡張したもの。通常、単に剰余環といったら整数を整数で割った余りが成すものを指す(個人の主観で数学系の人には怒られるかも)が、多項式環は多項式を多項式で割った余りが成す環のことをいう。TFHEでは$N$を2の冪として、$X$の多項式を$X^N+1$で割った余りが成す環だけを考える。理論的には絶対に$X^N+1$という法を取らなければいけないわけではないが、因数分解ができないこと(できてしまうと脆弱になるのだがその話は理論編で)、剰余演算が容易にできること、高速フーリエ変換やNTT(数論変換)との相性が良い(講義資料か過去に書いた記事を参照してほしい)ことからこれが使われている。
多項式環の具体例
TFHEでは実際には$N=1024$とかが使われるのですが、具体例としては$N=2$を使うこととしましょう。多項式環の元となる多項式の最大次数は$N-1$なので今は1次の多項式が元になります。TRLWEではTorusを係数とする多項式が出てきます。例えば$0.3X-0.1$みたいな多項式です。係数がTorusなので足し算は定義できて$(0.3X-0.1)+(0.9X+0.4)=0.2X+0.3$のようになります。しかし、Torus係数多項式同士の積はやはり定義されません。
そこでもう一つ出てくるのが整数係数の多項式です。つまり$3X+1$みたいなやつです。整数係数多項式をTorus係数多項式と掛け算することは可能です。つまり、$(3X+1)(0.3X-0.1)=0.9X^2-0.1\equiv 0 \bmod X^2+1$みたいな計算です。整数係数多項式同士の演算は使わないので整数係数の方は必ずしも$X^N+1$を法とする多項式環の上で定義する必要はあるません。ただ、実際に行う演算はTorus係数多項式との多項式環での乗算だけをするので最高次数は$N-1$次までで十分です。
TRLWEの具体的構成(平文がTorus係数多項式の場合)
暗号の安全性を決めるパラメータは２つで$N∈\mathbb{Z}^+,α_{bk}∈\mathbb{R}^+$。
$a[X]∈ \mathbb{T}_N[X], e[X],b[X]∈ \mathbb{T}_N[X], s[X]∈ \mathbb{B}_N[X],m[X]∈ \mathbb{T}_N[X]$とする。$m[X]$が平文、$a[X]←U_{\mathbb{T}N[X]}$,$e[X]←\mathcal{D}_{\mathbb{T}_N[X],α_{bk}}$,$s[X]←U_{\mathbb{B}_N[X]}$とする。
そうすると、TRLWEの暗号文は$b[X]=a[X]⋅ s[X]+ m[X] +e[X]$として、$(a[X],b[X])$という$N-1$次の多項式が2つ並んだベクトルである。$b[X]-a[X]⋅s[X]=m[X]+e[X]$になるので、この$e[X]$をどうにかして削除する方法を加えると$m[X]$がとれて復号できる。
やはりTRLWEも$N,\alpha_{bk}$を大きくすればするほど安全($α_{bk}$は大きくしすぎると暗号文が壊れる)なのだがその話は理論編で。
TRLWEの加法準同型性
TLWEとTRLWEはよく似ているので加法準同型性も同じように成り立つ。２つの暗号文$(a[X]_1,b[X]_1),(a[X]_2,b[X]_2)$を考え、その和を$(a[X]_1+a[X]_2,b[X]_1+b[X]_2)$とすると、$b_1[X]+b_2[X]-(a_1[X]+a_2[X])⋅s[X]=m_1[X]+m
_2[X]+e_1[X]+e_2[X]$になる。$m_1+m_2$が出てくるので加法準同型になっていることが分かる。
TRLWEの特徴
TRLWEの特徴として、同じ安全性(というのは現代の暗号学ではそういう評価になってしまうというだけで将来的には変わりうるが)・同じデータならTLWEよりTRLWEの方が暗号文のサイズが小さいことが挙げられる。TLWEでは暗号文一つにつき１つのTorus値しか持てないが、TRLWEではTorus多項式の係数は$N$個あるので$N$個のTorusを1つの暗号文で持てる。
また、TRLWEでは1つの暗号文の加算で$N$個のTorus値の加算を同時に計算できることになる。これはプロセッサの命令で言うところのSIMDのような演算(数学っぽくベクトルの加算といってもいいが)であり、多少制約はつくものの(異なる次数の係数同士の足し算は簡単にはできない)TLWEより高速に加算ができることになる。
これらの性質に加え、TFHEではそもそもTRLWEが持つ多項式環としての構造も利用する。こうしたTLWEよりも豊かな性質を持つことから(安全性評価に疑問符が残っているにもかかわらず)格子暗号ベースの準同型暗号ではTRLWEを用いていることが多い。
TRLWEの具体的構成(平文がバイナリ係数多項式の場合)
実際に使う暗号文の平文はバイナリを係数とする多項式であるので、その場合TRLWEの構成を示す。これもTLWEと似た形である。
$m[X] ∈ \mathbb{B}[X]と置き直し、μ=1/8\in\mathbb{T}$とする。$(μ(2⋅ m[X]-1[X])∈\mathbb{T}_N[X])$である。
- TRLWEの暗号文は$b[X]=a[X]⋅ s[X]+μ(2⋅ m[X]-1[X])+e[X]$
- 復号は$(1+\mathit{sgn}(b[X]-a[X]⋅ s[X]))/2$である。($\mathit{sgn}$は符号関数で各係数に作用)
SampleExtractIndex
Sample Extract IndexはTRLWEをTLWElvl1に変換する関数のことである。TLWElvl1と前回喋ったTLWE(lvl0)の違いは$\mathbb{a}$の長さが$n$か$N$かだけである。
この関数を導くためにまずは$b[X]-a[X]⋅s[X]$を係数ごとに書き下す。3つ目の∑で中の掛け算にマイナスがついてるのは$X^N+1$を法とする多項式環の上で計算しているためであることに注意。
$$b[X]-a[X]⋅s[X] = ∑^{N-1}_{k=0} [b_k-(∑_{i+j=k,0≤i,j≤N-1}a_i⋅s_j)-(∑_{i+j=N+k,0≤i,j≤N-1}-a_i⋅s_j)]X^k$$
これをみると$k$次の係数だけ復号できればよいのであれば総和の$k$を固定した場合を考えることで
$$b_k-(∑_{i+j=k,0≤i,j≤N-1}a_i⋅s_j)-(∑_{i+j=N+k,0≤i,j≤N-1}-a_i⋅s_j)$$
だけが計算できれば良いことがわかる。この式はTLWEの$b-\mathbf{a}\cdot\mathbf{s}$と非常によく似ているので、文字をうまく置き直してやることでTLWElvl1にすることができる。
具体的には求めるTLWElvl1を$(\mathbf{a}',b')$と表現するとし、TRLWEの秘密鍵$s[X]$の係数を並べたベクトル$\mathbf{s}'$として、
$$b_k-(∑_{i+j=k,0≤i,j≤N-1}a_i⋅s_j)-(∑_{i+j=N+k,0≤i,j≤N-1}-a_i⋅s_j) = b'-\mathbf{a}'\cdot\mathbf{s}'$$
となるように$(\mathbb{a}',b')$の値を決めれば良い。そうすれば$(\mathbf{a}',b')$は$\mathbf{s}'$を秘密鍵とするTLWElvl1となる。
$(\mathbb{a}',b')$の値の決め方を上の式に基づいて書き下すと、
$$
\begin{align}
b'&=b_k\\
a'_i&=\begin{cases}
a_{k-i}\ \mathrm{if}\ i≤k\\
-a_{N+k-i}\ \mathrm{otherwise}
\end{cases}
\end{align}
$$
のようになる。
これがSample Extract Indexである。
次回
次回は一番の鬼門(掛け算に相当する演算を導入するので当たり前ですが)であるTRGSWなので気が重い感じはありますが年始までに書けたらいいなぁと思っています。