はじめに
本記事ではCKKS方式の準同型暗号を題材にEncode, Decode, Encrypt, Decrypt に関する各種証明まで行いました。
コメント、ご指摘歓迎いたします。
事前知識
準同型暗号とは
平文$m_1, m_2$, 暗号化関数$E(\cdot)$に対して、
E(m_1)\oplus E(m_2)=E(m_1\oplus m_2)
が成り立つ暗号を演算$\oplus$に関する準同型暗号といいます。$\oplus$は、例えば加算や乗算などがあります。
格子暗号とは
格子暗号とは格子問題の困難性に基づく暗号です。耐量子暗号として近年注目が集まっています。格子問題はいろいろありますが、最も有名なのは最短ベクトル問題（SVP）でしょう。
| SVP：$n$個の基底が与えられたときに、それらの基底が張る格子点のうち原点に最も近い点（原点除く）を求めよ。 |
|---|
CKKS方式の準同型暗号
CKKS方式の準同型暗号は論文[1]で提案された暗号手法です。特徴はいくつかありますが、その1つとして複素数の暗号化が挙げられます。近年ニューラルネットワークベースのAI技術の発展、普及によりサーバ上にAIを搭載してサーバ上で学習、推論を行うケースが増えてきました。一方で、サーバが攻撃されると学習データやモデルパラメータを盗まれてしまう危険性が存在します。そこで、学習推論を暗号文のまま行うことができればサーバに平文のデータを置かなくて済むため、セキュリティ上のリスク回避につながります。
暗号化フレームワーク
文字の定義
フレームワークで使用する文字を以下のように定義します。
\begin{align}
&J=\sqrt{-1} \\
&N\in 2*\mathbb{N} \\
&\xi=e^{\frac{\pi}{N}J} \\
&A=\{A_{ij}=\xi^{(2i-1)(j-1)}\}\in\mathbb{C}^{N\times N} \\
&z\in\mathbb{C}^{\frac{N}{2}}
\end{align}
$J$は虚数単位です。$N$は平文の次元を2倍した値です。$A$はヴァンデルモンド行列（あるいはその転置）です。
Encode
入力: $z=(z_1,...,z_{\frac{N}{2}})\in\mathbb{C}^{\frac{N}{2}}$
出力: $p(x)\in\mathbb{Z}[x]/(x^N+1)$
- $z'\leftarrow\triangle_{scale}(z_1,...,z_{\frac{N}{2}},\overline{z_{\frac{N}{2}}},...,\overline{z_1})$
- $b_j\leftarrow(A_{1j},...,A_{Nj})$
- $r\leftarrow(\lfloor\frac{<z',b_1>}{<b_1,b_1>}\rceil,...,\lfloor\frac{<z',b_N>}{<b_N,b_N>}\rceil)$ ※$\frac{<z',b_i>}{<b_i,b_i>}\in\mathbb{R}$であることの証明は後述
- $p(x)\leftarrow<r,(1,x,...,x^{N-1})>$
- $p(x)$を出力.
Decode
入力: $p(x)\in\mathbb{Z}[x]/(x^N+1)$
出力: $z_{out}\in\mathbb{C}^{\frac{N}{2}}$
- $z_{out}\leftarrow(p(\xi),p(\xi^3),...,p(\xi^{N-1}))$
- $z_{out}$を出力.
keygen
公開鍵: $pk=(p_1,p_2)=([-a\cdot s+e]_{q_L},a)$
秘密鍵: $sk=s\in Z^{(3)}[x]/(x^N+1)$
Encrypt
入力: $\mu\in\mathbb{Z}[x]/(x^N+1)$
出力: $c=(c_1,c_2)$
暗号文:
c=(c_1,c_2)=([v\cdot p_1+e_1+\mu]_{q_L},[v\cdot p_2+e_2]_{q_L})
Decrypt
入力: $c=(c_1,c_2)$
出力: $\mu'\in\mathbb{Z}[x]/(x^N+1)$
復号文: $\mu'=[c_1+c_2\cdot s]_{q_l}$
準同型性の確認
加法性の確認
任意の暗号文$c_a=(c_{a1}, c_{a2}), c_b=(c_{b1}, c_{b2})$に対して,
\begin{align}
& \text{Decrypt}(sk, c_a)+\text{Decrypt}(sk, c_b) \\
&=[c_{a1}+c_{a2}s]_{ql}+[c_{b1}+c_{b2}s]_{q_l} \\
&=[(c_{a1}+c_{b1})+(c_{a2}+c_{b2})s]_{q_l} \\
&=\text{Decrypt}(sk, c_a+c_b) \\
\end{align}
が成り立つ. このことからCKKSは暗号文のまま足し算ができる.
乗法性の確認
任意の暗号文$c_a=(c_{a1}, c_{a2}), c_b=(c_{b1}, c_{b2})$に対して,
\begin{align}
& \text{Decrypt}(sk, c_a)\cdot\text{Decrypt}(sk, c_b) \\
&=[c_{a1}+c_{a2}s]_{ql}\cdot[c_{b1}+c_{b2}s]_{q_l} \\
&=[c_{a1}c_{b1}+(c_{a1}c_{b2}+c_{b1}c_{a2})s+c_{a2}c_{b2}s^2]_{q_l} \\
&=[d_0+d_1s+d_2s^2]_{q_l}
\end{align}
が成り立つ. ここで, $d_0=c_{a1}c_{b1}, d_1=c_{a1}c_{b2}+c_{b1}c_{a2}, d_2=c_{a2}c_{b2}$とする. このままだと$s$の次数が大きくなってしまう.
これを解決する方法の1つに再線形化という手法がある. $\text{Decrypt}(sk, P)=d_2s^2$を満たす$P$を用意し, $d'=(d_0', d_1')=(d_0, d_1)+P$とおくと,
\begin{align}
& \text{Decrypt}(sk, d'=(d_0', d_1')) \\
&=\text{Decrypt}(sk, (d_0, d_1))+\text{Decrypt}(sk, P) \\
&=[d_0+d_1s]_{q_l}+[d_2s^2]_{q_l} \\
&=[d_0+d_1s+d_2s^2]_{q_l}
\end{align}
となり, $\text{Decrypt}(sk, c_a)\cdot\text{Decrypt}(sk, c_b)$と同じ結果が得られるので, 暗号文のまま掛け算が可能であるといえる.
$P$の求め方について, $evk=(-a_0s+e_0+ps^2, a_0)(\text{mod} pq)$とおき,
P=\lfloor p^{-1}\cdot d_2\cdot evk\rceil(\text{mod} q)
とする求め方がある。
証明
各種記号は前述のとおりです。
<z',bi>/<bi,bi>が実数であることの証明
| 命題. $\frac{<z',bi>}{<bi,bi>}\in\mathbb{R}$ |
|---|
（証明）
与式を変形すると
\begin{align}
& \frac{<z',bi>}{<bi,bi>} \\
&=\frac{\triangle_{scale}}{N}\sum_{i=1}^N \{z_1\overline{A_{1i}}+...+z_{\frac{N}{2}}\overline{A_{\frac{N}{2}i}}+\overline{z_{\frac{N}{2}}}\overline{A_{(\frac{N}{2}+1)i}}+...+\overline{z_1}\overline{A_{Ni}}\} \\
&=\frac{\triangle_{scale}}{N}\sum_{i=1}^N \{z_1\overline{A_{1i}}+...+z_{\frac{N}{2}}\overline{A_{\frac{N}{2}i}}+\overline{z_{\frac{N}{2}}}A_{\frac{N}{2}i}+...+\overline{z_1}A_{1i}\} (\because \overline{A_{ji}}=A_{(N-j+1)i}) \\
&=\frac{\triangle_{scale}}{N}\sum_{i=1}^N \{(z_1\overline{A_{1i}}+\overline{z_1}A_{1i})+...+(z_{\frac{N}{2}}\overline{A_{\frac{N}{2}i}}+\overline{z_{\frac{N}{2}}}A_{\frac{N}{2}i})\} \\
&=\frac{2\triangle_{scale}}{N}\sum_{i=1}^N \{Re(z_1\overline{A_{1i}})+...+Re(z_{\frac{N}{2}}\overline{A_{\frac{N}{2}i}})\} \\
&\in\mathbb{R}
\end{align}
となり, 題意が成り立つ. $\blacksquare$
Decode(Encode(z))≈z の証明
補題1
| 補題1. $1\leq k_1\leq N, 1\leq k_2\leq Nのとき, \sum_{i=1}^{N}A_{k_1i}A_{k_2i}=N(k_1+k_2=N+1), 0(k_1+k_2\neq N+1)$ |
|---|
（証明）
与式を変形すると
\sum_{i=1}^{N}A_{k_1i}A_{k_2i}=\sum_{i=1}^{N}\xi^{(2k_1+2k_2-2)(i-1)}
これは$k_1+k_2=N+1$のとき$N$になる. 以降ではそうでない時を考える.
$\xi^{(2k_1+2k_2-2)(i-1)}, i=1,...,N$について, 周期を$N'$とおく. $\xi^{(2k_1+2k_2-2)(i-1)}, i=1,...,N'$について, これらは互いに異なる1の$N'$乗根であるから, 方程式$z^{N'}=1$の解である. よって, 解と係数の関係によりその総和$\sum_{i=1}^{N'}\xi^{(2k_1+2k_2-2)(i-1)}$は0となり, $\sum_{i=1}^{N}\xi^{(2k_1+2k_2-2)(i-1)}=\frac{N}{N'}\sum_{i=1}^{N'}\xi^{(2k_1+2k_2-2)(i-1)}=0$となる.
以上より題意が成り立つ. $\blacksquare$
補題2
| 補題2. $p(A_{k2})\approx\triangle_{scale}z_k$ |
|---|
（証明）
左辺を整理すると
\begin{align}
& p(A_{k2}) \\
&=\sum_{i=1}^N \lfloor\frac{<z',b_i>}{<b_i,b_i>}\rceil A_{k2}^{i-1} \\
&\approx\sum_{i=1}^N \frac{<z',b_i>}{<b_i,b_i>}A_{k2}^{i-1} \\
&=\sum_{i=1}^N \frac{<z',b_i>}{<b_i,b_i>}A_{ki} \\
&=\frac{\triangle_{scale}}{N}\sum_{i=1}^N \{z_1\overline{A_{1i}}+...+z_{\frac{N}{2}}\overline{A_{\frac{N}{2}i}}+\overline{z_{\frac{N}{2}}}\overline{A_{(\frac{N}{2}+1)i}}+...+\overline{z_1}\overline{A_{Ni}}\}A_{ki} \\
&=\frac{\triangle_{scale}}{N}\sum_{i=1}^N \{z_1A_{Ni}+...+z_{\frac{N}{2}}A_{(\frac{N}{2}+1)i}+\overline{z_{\frac{N}{2}}}A_{\frac{N}{2}i}+...+\overline{z_1}A_{1i}\}A_{ki} (\because \overline{A_{ji}}=A_{(N-j+1)i}) \\
&=\frac{\triangle_{scale}}{N}\{z_1\sum_{i=1}^N A_{Ni}A_{ki}+...+z_{\frac{N}{2}}\sum_{i=1}^N A_{(\frac{N}{2}+1)i}A_{ki}+\overline{z_{\frac{N}{2}}}\sum_{i=1}^N A_{\frac{N}{2}i}A_{ki}+...+\overline{z_1}\sum_{i=1}^N A_{1i}A_{ki}\} \\
&=\frac{\triangle_{scale}}{N} z_k\sum_{i=1}^N A_{(N-k+1)i}A_{ki} (\because 補題1より)\\
&=\frac{\triangle_{scale}}{N} z_kN \\
&=\triangle_{scale}z_k
\end{align}
となり, 題意が成り立つ. $\blacksquare$
本題
| 命題. $Decode(Encode(z))\approx z$ |
|---|
（証明）
左辺を整理すると
\begin{align}
& Decode(Encode(z)) \\
&=Decode(p(x)) \\
&=\triangle_{scale}^{-1}(p(A_{12}),p(A_{22}),...,p(A_{\frac{N}{2}2})) \\
&\approx\triangle_{scale}^{-1}(\triangle_{scale}z_1,\triangle_{scale}z_2,...,\triangle_{scale}z_{\frac{N}{2}}) (\because 補題2より) \\
&=(z_1,...,z_{\frac{N}{2}}) \\
&=z
\end{align}
となり, 題意が成り立つ. $\blacksquare$
Decrypt(Encrypt(μ))≈μ の証明
| 命題. $Decrypt(Encrypt(\mu))\approx\mu$ |
|---|
（証明）
$e'=v\cdot e+e_1+e_2\cdot s$とおくと, $v,e,e_1,e_2,s$は$\mu$と比べて小さいため, その積和である$e'$も$\mu$と比べて小さい. よって, $\mu+e'\approx\mu$.
したがって,
\begin{align}
& \text{Decrypt}(sk, \text{Encrypt}(pk, \mu)) \\
&=[c_1+c_2\cdot s]_{q_l} \\
&=[[v\cdot p_1+e_1+\mu]_{q_L}+[v\cdot p_2+e_2]_{q_L}\cdot s]_{q_l} \\
&=[[v\cdot[-a\cdot s+e]_{q_L}+e_1+\mu]_{q_L}+[v\cdot a+e_2]_{q_L}\cdot s]_{q_l} \\
&=[[[v\cdot[-a\cdot s+e]_{q_L}+e_1+\mu]_{q_L}+[v\cdot a+e_2]_{q_L}\cdot s]_{q_L}]_{q_l} \\
&=[[v\cdot(-a\cdot s+e)+e_1+\mu+(v\cdot a+e_2)\cdot s]_{q_L}]_{q_l} \\
&=[[v\cdot e+e_1+\mu+e_2\cdot s]_{q_L}]_{q_l} \\
&=[v\cdot e+e_1+\mu+e_2\cdot s]_{q_l} (\because q_lはq_Lの約数)\\
&=\mu+e' \\
&\approx\mu
\end{align}
となり, 題意が示された. $\blacksquare$
参考・引用
[1] Jung Hee Cheon, Andrey Kim, Miran Kim, Yong Soo Song:
Homomorphic Encryption for Arithmetic of Approximate Numbers. ASIACRYPT (1) 2017: 409-437
[2] https://zenn.dev/herumi/articles/ckks-enc-dec
[3] https://eaglys.co.jp/developers-blog/trends/report1/