初めに
前回紹介したlifted ElGamal暗号文同士は、ペアリングという演算を使うと「掛け算」、特に暗号文ベクトルの内積を計算できます。
ここではペアリングとASIA CCS2018で発表した掛け算方法を紹介します。
ペアリング
G_1, G_2を楕円曲線の点集合による位数rの加法巡回群、G_Tを有限体の1のべき乗根の集合からなる位数rの乗法群とします。G_1の生成元をP, G_2の生成元をQとします。
P=\Set{0,P,2P,\dots,(r-1)P},
Q=\Set{0,Q,2Q,\dots,(r-1)Q}.
ペアリングe:G_1 \times G_2 \rightarrow G_Tとは、g:=e(P,Q)がG_Tの生成元で、任意の整数a, bに対して
となる写像です。
順を追って説明しましょう。ペアリングを使うと楕円曲線の2個の点を決めると、ある1のべき乗の値が定まります。
当初は楕円曲線G_1とG_2は同じものが使われていましたが、近年は効率化やセキュリティ上の理由から異なる楕円曲線を使うことが多いです。
g=e(P,Q)とすると、Pを2倍、3倍すれば、e(2P,Q)=g^2, e(3P,Q)=g^3とgの2乗、3乗となります。
Qについても同じです。e(P,2Q)=g^2, e(P,3Q)=g^3. マイナスは逆元になります。e(-P,Q)=e(P,-Q)=g^{-1}.
G_1とG_2の生成元P, Qのペアリング値g:=e(P,Q)がG_Tの生成元なので、G_T=\Set{1,g,g^2, \dots, g^{r-1}}となります。
a, b倍する操作は点の間で移動できます。
e(aP, bQ)=e(P, abQ)=e(abP, Q) = g^{ab}.
この性質をペアリングの双線型性といい、非常に重要な性質です。aやbの値を知らなくてもこの等式が成り立つからです。
前回楕円曲線暗号の安全性 DLPとCDHとDDHで紹介したように、CDH仮定があると、aP, bPからabPは計算できません。しかし、ペアリングを使うとaP, bQからe(abP, Q)=g^{ab}なら計算できます。
もちろん、bPじゃなくてbQだったり、abPそのものではなくg^{ab}だったりするのですが、これを利用して面白い性質を持った暗号が多数提案されています。
L2準同型暗号
L2のLはleveledで、乗算が1回できるという意味です。
G_i(i=1,2)に関するlifted ElGamal暗号の秘密鍵s_iと公開鍵s_1 Pとs_2 Q、およびそれぞれの暗号文c_i:=Enc_i(m_i;t_i)を用意します。
\begin{align*}
c_1&=(S_1,T_1)=(m_1 P + t_1 (s_1 P), t_1 P),\\
c_2&=(S_2,T_2)=(m_2 Q+t_2 (s_2 Q), t_2 Q).
\end{align*}
c_1とc_2の積c_1 c_2を暗号文のそれぞれの要素同士のペアリングを並べたものとして定義しましょう。
c_1 c_2 := (e(S_1,S_2), e(S_1,T_2),e(T_1,S_2), e(T_1,T_2)).
足し算と違って暗号文が大きくなってしまいました。そのため一度しか掛け算できません。c_1 c_2 = (u_1, u_2, u_3, u_4)としてそれぞれの成分の計算を進めます。
g^aは指数部分が小さくなってしまうのでpow(g,a)と書くことにします。
\begin{align*}
u_1&=e(S_1,T_1)=e((m_1 + s_1 t_1) P, (m_2+ s_2 t_2)Q)=pow(g, (m_1 + s_1 t_1)(m_2 + s_2 t_2)),\\
u_2&=e(S_1,T_2)=e((m_1 + s_1 t_1) P, t_2Q)=pow(g, (m_1 + s_1 t_1)t_2),\\
u_3&=e(T_1,S_2)=e(t_1P, (m_2+s_2 t_2)Q)=pow(g, (m_2+s_2 t_2)t_1),\\
u_4&=e(T_1,T_2)=e(t_1 P, t_2 Q)=pow(g, t_1 t_2).
\end{align*}
ごちゃごちゃしていますが、復号するために乱数を除去するためにX=(u_1 u_4^{s_1 s_2})/(u_2^{s_2} u_1^{s_1})を計算すると
\begin{align*}
X&=pow(g, (m_1 + s_1 t_1)(m_2 + s_2 t_2)+s_1 s_2 t_1 t_2 - (m_1 + s_1 t_1)s_2 t_2 - (m_2+s_2 t_2)s_1 t_1),\\
&=pow(g, m_1 m_2)=g^{m_1 m_2}.
\end{align*}
となります。したがってm_1 m_2がgに関するDLPが解ける程度の大きさならDLP(g,X)=m_1 m_2と元の平文の積を得られます。つまり
Dec(\Set{s_1,s_2}, (u_1,u_2,u_3,u_4)):=DLP(g, (u_1 u_4^{s_1 s_2})/(u_2^{s_2} u_1^{s_1})).
暗号文ベクトルの内積
x=(x_1, \dots, x_n), y=(y_1, \dots, y_n)を整数のベクトルとし、c_i=Enc_1(x_i), c'_i=Enc_2(y_i)をG_1, G_2のlifted ElGamal暗号文とします。すると、前節の方法でc_i c'_iという暗号文の積を計算できます。
あとはこの暗号文の積を「足す」だけです。暗号文は(u_1,u_2,u_3,u_4)\in {G_T}^4の形です。暗号文同士の加算は要素ごとの積として定義します。
暗号文の積の復号が要素の掛け算（とべき乗）の形なので、暗号文同士を加算してもその形が保たれて、加法準同型性が保たれます。
するとc_1 c'_1 + \cdots c_n c'_nを計算でき、復号すれば\sum_i x_i y_iとベクトルxとyの内積を得られます。
まとめ
ペアリングを用いてlifted ElGamal暗号文同士の乗算方法を紹介しました。これにより一度だけ乗算可能な公開鍵暗号を構成でき、暗号文ベクトルの内積も計算できます。
前回紹介したWasmによる実装she-wasmがあるので興味ある方はごらんください。
Discussion