初めに
今回は準同型暗号CKKSの暗号化・復号と、加算・乗算方法を説明します。
記事一覧は準同型暗号CKKSその1 多項式環
主な記号の復習
-
M : 4以上の2のべきの形の整数, N:=M/2
-
[\cdot] : 整数への丸め（多項式ならその係数）
-
R:=ℤ[X]/(X^N+1) : 整数係数の多項式をX^N+1で割った余りの多項式全体
整数nに対してR_nを、Rの多項式の係数をnで割った余りとする多項式全体とします。R_n:=(ℤ/nℤ)[X]/(X^N+1).
パラメータと乱数
CKKSでは様々なパラメータが登場します。
-
L : 乗算回数の上限
-
p, q_0 : 適当な整数
-
q_l:=p^l q_0 for 0 < l \le L. : lは暗号文のレベルを表す。とりあえず今回は固定としてください。
Lは暗号文の乗算を何回できるかを示すパラメータです。
pやq_0は扱う暗号文の精度に関するパラメータです。
これらのパラメータは大きいほどよくなりますが、暗号文などが大きくなります。
Mは安全性を示すセキュリティパラメータとq_lによって決まります。実際には1024, 2048, 4096などが使われます。
秘密鍵や暗号化に使う乱数がいろいろ登場します。これも様々なパラメータや分布によって決まるのですが、煩雑なのでここではばっさり省略します。
集合Sからランダムに要素aを一つ選ぶことをa ← Sと書きます。
鍵生成とR-LWE仮定
\Set{-1,0,1}の中からN個ランダムに選んでそれを係数とする多項式をs \in R_{q_L}とします。これが秘密鍵です。
a ← R_{q_L}と、係数が小さい乱数のN次多項式eを選びます。b:=-as+e \in R_{q_L}とします。(b, a) \in (R_{q_L})^2が公開鍵です。
もし、乱数eが無ければa, bが公開されているので方程式b=-asは容易に解けて秘密鍵sが求まります。しかし乱数eがあると適切なサイズのパラメータの元ではsを求めるのが困難であると考えられています。
大雑把に言うと、そのような仮定をR-LWE(ring learning with errors)仮定といい、CKKSはR-LWE仮定の元で安全とされています。
暗号化
m \in Rを平文、pk:=(b,a)を公開鍵とします。
vを\Set{-1,0,1}の中からランダムに選んで係数とした多項式、e_0, e_1を小さい係数のランダム多項式とします。
Enc(m):=v \cdot pk + (m + e_0, e_1) \in (R_{q_L})^2が暗号文です。ここで(R_{q_L})^2の掛け算や足し算は要素ごとにします。つまり
Enc(m)=v(b, a)+(m+e_0, e_1)=(vb + m+e_0, va + e_1).
やはりR-LWE仮定により、aとva+e_1からvは求められず、したがってvb+m+e_0とbからmは分かりません。
復号
レベルlの暗号文c:=(c_0, c_1) \in (R_{q_l})^2に対して秘密鍵sを使ってDec(c):=c_0 + c_1 s \in R_{q_l}とします。
c=Enc(m)のとき、Dec(c)=m \bmod{q_l}を確認しましょう。構成方法からb=-as+e, c_0=vb + m+e_0, c_1=va+e_1なので
Dec(c)=(v(-as+e) + m+e_0)+(va+e_1)s=m+(ve+e_0+e_1s).
ここでv, e, e_0, e_1, sはどれも小さい係数なので(ve+e_0+e_1s)も小さい係数の多項式です。
したがって、Dec(c) \approx mとなり大体復号できました。このようにCKKSは誤差を伴う近似暗号です。
暗号文の加算
m, m' \in Rの暗号文c:=Enc(m)=(c_0,c_1), c':=Enc(m')=(c'_0,c'_1)について、c+c'を要素ごとの加算で定義します。
c+c':=(c_0+c'_0,c_1+c'_1)
すると
\begin{align*}
c+c'&=(v \cdot pk + (m + e_0,e_1))+(v' \cdot pk + (m' + e'_0,e'_1))\\
&=(v+v')pk + ((m+m')+(e_0+e'_0), (v+v')a + (e_1+e'_1))\\
&=v'' pk + ((m+m')+e''_0, e''_1).
\end{align*}
ただしv'':=v+v', e''_0:=e_0+e'_0, e''_1:=e_1+e'_1. これらが小さい乱数なので、c+c'はm+m'の暗号文に近いです。したがって、
これは暗号文の加算ができていることを意味します。
暗号文の乗算
前節の記号を用いて2個の暗号文c, c' \in (R_{q_l})^2の乗算を次の方法で定義します。
cc':=(c''_0, c''_1, c''_2) := (c_0 c'_0, c_0 c'_1 + c_1 c'_0, c_1 c'_1) \in (R_{q_l})^3.
乗算後の暗号文はR_{q_l}の要素3個になりました。復号するにはDec(cc'):=c''_0+c''_1 s + c''_2 s^2を使います。乗算前の暗号文の復号はc_0+c_1 sだったのに比べて項が1個増えています。
これがmm'に近いことを確認しましょう。
Dec(cc')=(c_0 c'_0) + (c_0 c'_1 + c_1 c'_0)s + (c_1 c'_1)s^2=(c_0+c_1 s)(c'_0 + c'_1 s).
c_0+c_1 s = Dec(c) \approx m, c'_0 + c'_1 s=Dec(c') \approx m'なのでDec(cc') \approx mm'となります。
ただし、誤差は加算のときよりもずっと大きくなっているので注意が必要です。このあたりの精密な評価は論文を参照ください。
ペアリングと内積計算可能なL2準同型暗号で紹介した暗号も暗号文同士を掛け算すると暗号文の構造が大きくなってしまいました。残念ながらあちらはサイズを小さくできなかったのですが、CKKSは評価鍵というものを導入すると小さくできます。
評価鍵と乗算暗号文サイズの縮小
評価鍵evkを定義するために、新しく整数Pというパラメータを導入します。
a' ← R_{P q_L}, e'を小さい乱数、b':=(-a's + e' + P s^2) \bmod{P q_L}として、evk:=(b', a') \in (R_{P q_L})^2とします。公開鍵pkと同じくR-LWE仮定によりb'から秘密鍵sは求められません。
前節で作った乗算後の暗号文(c_0, c_1, c_2)に対して(d_0, d_1):=(c_0, c_1) + [P^{-1} c_2 evk] \bmod{q_l}とします。以下mod q_lで考えると
\begin{align*}
d_0 &= c_0 + [P^{-1} c_2 (-a's + e' + P s^2)]=c_0 + c_2 s^2 + [P^{-1} c_2 (-a's+e')].\\
d_1 &=c_1 + [P^{-1} c_2 a'].
\end{align*}
d_0がc_0+c_2 s^2と残りの形になっていることに注意してください。このようにして作った暗号文(d_0, d_1)を復号してみましょう。
Dec((d_0, d_1))=d_0 + d_1 s = (c_0 + c_1 s+c_2 s^2) +[P^{-1}c_2(-a's+e')] + [P^{-1} c_2 a']s.
右辺前半c_0+c_1 s + c_2 s^2は前節のDec(cc')と同じなのでmm'に近い値です。後半の値は整数丸めをしなければ(P^{-1}c_2(-a's+e')) + (P^{-1} c_2 a')s=P^{-1}c_2 e'なので、Pをc_2の係数に比べて大きくとると丸めによる誤差を含めても小さい値です。よって、Dec((d_0, d_1)) \approx mm'.
改めて、c:=(c_0, c_1)=Enc(m), c':=(c'_0, c'_1)=Enc(m')としたとき、
\begin{align*}
c''_0&:=c_0 c'_0,\\
c''_1&:=c_0 c'_1 + c_1 c'_0,\\
c''_2&:=c_1 c'_1,\\
(d_0,d_1)&:=(c''_0, c''_1)+[P^{-1}c''_2 evk] \bmod{q_l}
\end{align*}
として暗号文同士の乗算をc c':=(d_0,d_1)で定義します。
なお、CKKSの平文空間とエンコード・デコードで説明したようにC^{N/2}の元をエンコードするときにスケール因子Δ倍しています。
したがって、乗算後はΔ^2が掛かっていることに注意してください。
リスケール
レベルlの暗号文c:=(c_0,c_1) \in (R_{q_l})^2をレベルl' < lに変換します。リスケールすると演算精度を制御しつつ暗号文サイズを小さくできます。スケール因子Δとは違うものなので注意してください。
c'_i:=[c_i/p^{l-l'}]と各要素をp^{l-l'}で割って整数に丸めるだけです。Rs_{l→l'}(c):=(c'_0,c'_1) \in (R_{q_l'})^2がリスケーリングです。
まとめ
CKKSの暗号化と復号処理を紹介し、暗号文同士の加算と乗算も解説しました。
乗算すると暗号文が要素3個になるのですが、評価鍵を用いて元の要素2個の暗号文に変換できます。
Discussion