楕円lifted ElGamal暗号の加法準同型性とWasmによる実装例

初めに

前回、楕円曲線を使った公開鍵暗号楕円ElGamal暗号を紹介しました。
この方式は暗号化したい数値をそのまま使えず、楕円曲線の点に埋め込む必要がありました。lifted ElGamal暗号はその問題を改善する方法の一つです。
その方式とlifted ElGamal暗号が持つ加法性について紹介し、WebAssembly(Wasm)によるサンプルを試します。

楕円ElGamal暗号の復習

$P$を楕円曲線の点、$G$を$P$を生成元とする位数$r$の加法巡回群とします。$G=\Set{0, P, 2P, \dots, (r-1)P}.$

$0$以上$r$未満の整数の集合$[0, r)$からランダムに整数$s$を一つとり、秘密鍵とします。$Q:=sP$が公開鍵です。
$G$の要素$M$を暗号化するには、$t ← [0, r)$をランダムにとり、公開鍵$Q$を使って$Enc(Q, M):=(M+tQ,tP)$とします。
暗号文$c:=(S,T)$に対して秘密鍵$s$を使って$Dec(s,c):=S-sT$で復号します。

楕円lifted ElGamal暗号

説明の前に一つ記号を導入します。$G$の点$xP$が与えられたときに$x \in [0, r)$を求める操作を$DLP(P, xP)=x$と書くことにします。DLPは離散対数問題を解く操作です。

楕円lifted ElGamal暗号の鍵生成はElGamal暗号と同じです。
$s← [0, r)$が秘密鍵で$Q:=sP$が公開鍵。

整数$m$を暗号化するには、$M:=mP$として楕円曲線の点を作り、それをElGamal暗号化します。つまり、$t ← [0, r)$をランダムにとり

$$Enc(Q, m):=(mP+tQ, tP).$$

暗号文$c=(S, T)$の復号は$dec(s, c):=S-sT$でElGamal暗号文を復号したあと、結果を$P$に関してDLPで解きます。

$$Dec(s, c):=DLP(P, dec(s, c)).$$

楕円lifted ElGamal暗号の妥当性

$m$を暗号化して作った暗号文$c$を復号したら元に戻ることを確認します。
$M:=mP$をElGamal暗号で暗号化して、復号するので$M$に戻ります。最後に$DLP(P, M)=DLP(P, mP)=m$とDLPを解いて元に戻ります。

まずはここで疑問に思うでしょう。暗号の安全性のためにDLP困難な群を使っているのに、復号時にDLPを解くのはナンセンスでは？
それは当然の疑問なのですが、$m$が32ビット程度の整数値なら力業でDLPを解いても実用的な速度が得られます。DLPが解ける範囲なら使えるのです。詳細はまたの機会に紹介します。乱数$t$は大きな値なので$DLP(P, tP)$は解けず、安全性はElGamal暗号と同じです。
楕円lifted ElGamal暗号は復号可能な平文の範囲が狭い、復号時に小さなDLPを解かなければならないという制約があるのですが、その代わりに興味深い性質を持っています。

加法準同型

$m_1$, $m_2$を（最大32ビット程度の）平文、$c_i:=Enc(Q, m_i;t_i)=(S_i,T_i)$を対応する暗号文としましょう。ここで暗号時に利用した乱数$t_i$を明示しています。公開鍵$Q$を省略して$Enc(m;t)$と書くこともあります。
暗号文$c_1$と$c_2$の足し算を、要素ごとに（$G$の演算として）足すという意味で定義します。

$$c:=c_1+c_2:=(S_1+S_2,T_1+T_2) \cdots \text{（※）}.$$

このようにして作った$c=(S, T)$を観察します。$S_i=m_i P + t_i Q$, $T_i=t_i P$なので

$$\begin{align*} S&=(m_1 P + t_1Q) + (m_2 P + t_2Q) = (m_1 + m_2)P + (t_1+t_2)Q,\\ T&=t_1 P + t_2 P = (t_1+t_2)P. \end{align*}$$

$t:=t_1+t_2$とすると$c=((m_1+m_2)P+t Q, tP) = Enc(m_1+m_2;t).$ つまり

$$Enc(m_1;t_1)+Enc(m_2;t_2)=Enc(m_1+m_2;t_1+t_2).$$

$m_1$の暗号文と$m_2$の暗号文を（※）の意味で足すと、$m_1+m_2$の暗号文になるのです。復号しなくても暗号文同士の加算ができたのです。
更に$c=(S,T)$に対して$-c:=(-S,-T)$とすると$c+(-c)=(0, 0)$となり、これは平文0を乱数0で暗号化した暗号文$Enc(0;0)$です。
したがって、暗号文の空間は（※）を加算、$(0,0)$を単位元とする加法群となります（厳密には乱数だけが異なる暗号文は同一視する必要がある→「おまけ」参照）。
このような性質を加法準同型といいます。乱数$t$も省略すると

$$Enc(m_1)+Enc(m_2)=Enc(m_1+m_2).$$

Wasmによる実装例

数式ばかりでは飽きるのでlifted ElGmal暗号を利用できるshe-wasmで試してみましょう（npmパッケージもあります）。
ブラウザだけで試すには、デモページ「暗号化したまま計算できる暗号技術」を開き、[F12]キーを押して開発ツールの[コンソール]を開きます。

秘密鍵と公開鍵の生成

まず

const sk = new she.SecretKey()
sk.setByCSPRNG()

で秘密鍵を初期化します。
そして、

const pk = sk.getPublicKey()

で対応する公開鍵を得ます。
中身はserializeToHexStrで確認できます（値は毎回変わります）。

>sk.serializeToHexStr()
"d5d417372745699f99558aafcd05b6c7c1416c05c17f693c5e3f95a6a29be102014cd1f0bdf8793edec3b9b243c5cc8a26533cd37dfa5159711f991a1058521b"
>pk.serializeToHexStr()
"a63f0a93a1a7d060209133eff5a470c3ec4ee10351752cb4dbf2a38185ca291e621003da80e166783c641925e852fa4cd267ea4019a608b02e09dcdb00b7941887b74b9d90b88eccfbf1396f195e3719b12d61ce5aab19b358dee6a51b6a5f96"

暗号化と復号

公開鍵pkで暗号化します。G1という巡回群に対する楕円lifted ElGamal暗号なので

c1 = pk.encG1(12)

です（デモなので小さな値しか扱えません）。中身はsk, pkと同様にserializeToHexStr()を使います。

c1.serializeToHexStr()
"95eef57f92641fd158036d98b91d2980b1e0ad226bf8fdfa8e9b6ce8c3a98b8fb4799bfef56782ca398e1bc3b3fdb8c4a06426eeb716b3b5b58ee524cbdfeb08"

秘密鍵`skで復号します。

sk.dec(c1)
12

元の値に戻りました。

暗号文の加算

もう1個暗号文を作ります。

c2 = pk.encG1(9)

暗号文c1とc2を足しましょう。

c = she.add(c1, c2)

復号します。

>sk.dec(c)
21

結果は12+9=21になり、加法準同型性を確認できました。詳しい使い方はshe-APIにあるので興味ある方はご覧ください。

まとめ

楕円lifted ElGamal暗号と、その加法準同型暗号性を紹介しました。暗号文同士の足し算ができると、それだけでもいろいろな応用が考えられています。また紹介しましょう。

おまけ（平文空間と暗号文空間の対応）

平文空間と暗号文空間の対応を少し詳しく説明します。

平文空間は0以上r未満の整数全体$X=[0, r)$です。
任意の$c=(S, T) \in Y:=G \times G$は何かの暗号文になっています。
なぜなら $tP=T$ となる $t \in [0, r)$ が1個だけ存在します。ここでDLPは具体的に解けなくても構いません。「1個だけ存在する」という事実が重要です。
次に、$m$を変数とする方程式 $mP+tQ=S$ を考えると $m=DLP(P, S-tQ)$ という解を1個だけ持ちます。このとき$Enc(m;t)=(mP+tQ,tP)=(S, T)$です。つまり$Y$のどの要素も何かの暗号文となっており、暗号文の空間は$Y$に一致します。

次に暗号文空間$Y$の中で、暗号文$c$に対して復号したら同じ値になる暗号文の集合を$[c]$と書くことにします。$[c]=\Set{c' | Dec(c')=Dec(c)}$です。$Dec(c)=m$として、

$$c=Enc(m;t)=(mP+t Q, t P)=(mP,0)+(tQ, tP)=Enc(m;0)+Enc(0;t)$$

と式変形します。これは「$m$の乱数$t$による暗号文$c$」=「$m$の乱数0による暗号文」+「0の乱数$t$による暗号文」となっていることを示します。
$Enc(0;t)$は乱数の種類、つまり$r$個あります。まとめると$[c]=[Enc(m;0)]$は$r$個の要素を持つ集合。$Y$を「復号したら同じ値になる暗号文の集合」の集合に分割したものを$Y/～$と書きます。これは$r$個あります。
暗号文同士を足したら、元の平文の和の暗号文になる準同型性は$Y/～$でも成り立ちます。

$$Enc : X=[0, r) \ni m \mapsto [Enc(m;0)] \in Y/～$$

は$r$個の要素から$r$個の要素への写像で、1対1の対応であり、準同型性も成り立ちます。このとき$X$と$Y/～$は加法群として同型といいます。