初めに

この記事は準同型暗号の最前線1（入門編）、準同型暗号の最前線2（原理編）の続きです。
このページでは提案したL2準同型暗号の安全性の根拠の話をします。やや難しめです。

DDH仮定

電子投票のところで、各自の1票（0か1）を暗号化して集計する話をしました。
もちろん暗号文$Enc(0)$や$Enc(1)$を見て、それが0や1を暗号化したものであると見破られてしまっては困ります。どういう条件が成り立てば見破られないと考えられるでしょうか。

暗号化の方法を復習しながら考えてみましょう。
まず、楕円曲線の点（歯車の一つ）$P$を固定しました。これは皆が知っている公開パラメータです。
次にランダムに整数$s$をとり、$Q=sP$を公開しました（$s$が秘密鍵で$Q$が公開鍵です）。
暗号化は$m$を0か1として、乱数$r$をとり、
$Enc(m) = (mP + rQ, rP)$
としました。

$m = 0$を暗号化したときは$(rsP, rP)$で、$m = 1$を暗号化したときは$(P + rsP, rP)$です。

暗号文から$m$を推測しようとする人は、公開情報$P$, $sP$を知っていて、$(rsP, rP)$か$(P + rsP, rP)$かを見破ろうとするわけです。

つまり$P$, $sP$, $rP$（暗号文の第2成分）が与えられたときに、残り（暗号文の第1成分）が$rsP$か$P + rsP$のどちらの形をしているか区別できたら勝ちとなります。

定式化すると次の問題になります（$r$, $s$を$a$, $b$に置き換えた）：

「$P$, $aP$, $bP$と$cP$が与えられたとき$c=ab$かそうでないかを判定せよ」

もし$c=ab$と判定できたら暗号文が0を暗号化したもの、そうでなければそれ以外と分かります。
この問題をDDH問題（decision Diffie-Hellman）問題、DDH問題が困難なとき「DDH仮定を満たす」という言い方をします。
今回は楕円曲線（Elliptic Curve）の話なのでEC-DDHということもあります。

DHとDDH

最近のHTTPSでは「ECDHが使われている」ということを聞いたことがあるかもしれません。
ECDHとは楕円曲線のDiffie-Hellman鍵共有を指します。「$P$, $aP$, $bP$が与えられたときに$abP$を求めよ」という問題（DH問題）が難しいことを根拠に鍵交換します。具体的に$abP$を求めるのでCDH（computational DH）ということもあります。

$P$, $aP$, $bP$から$abP$を求められたら、残りの$cP$が$abP$に等しいかはみれば分かるので、DH問題が解ければDDH問題は解けます。
対偶をとると、DDH仮定を満たす（=DDH問題が解けない）なら、DH仮定を満たします（=DH問題が解けない）。

安全性の証明ではDDH仮定の方が使いやすいのでこちらよく使われます。ElGamal暗号はDDH仮定の下で安全である（今安全性の定義をしていないのでなんですが）と証明できます。

SXDH

今回提案方式のL2準同型暗号では2個の楕円曲線とそのペアリングを使っています。提案方式の安全性証明には、ペアリングに使われる2個の楕円曲線のDDH問題を利用しました。すなわち$P$が一つ目の楕円曲線の点、$Q$が二つ目の楕円曲線の点としたとき、

「$P$, $aP$, $bP$と$cP$が与えられたとき$c=ab$かそうでないか、または
「$Q$, $sQ$, $tQ$と$uQ$が与えられたとき$u=st$かそうでないか判定せよ。」

という問題です。
この問題はSXDH(Symmetric eXternal DH)問題と呼ばれます。この問題が困難であるというSXDH仮定は比較的新しい仮定（2005年～）です。今のところこの問題は難しいだろうと思われています。

なお、「$P$, $aP$, $bP$, $cP$, $Q$, $aQ$, $bQ$, $cQ$が与えられたときに$c=ab$かそうでないかを判定せよ」ではないことに注意してください。
なぜならペアリングの性質から
$e(aP, bQ) = ab e(P, Q)$
$e(P, cQ) = c e(P, Q)$
なので（注意：右辺は加法表記してます）、両者を比較すると$c = ab$かどうかはすぐ判定できてしまうからです。

提案方式はSXDH仮定の下で安全であると示されます。

回路プライバシー

最後に、準同型暗号特有の性質である回路プライバシー（circuit privacy）という概念を紹介しましょう。

準同型暗号は、Aが暗号化してBに暗号文を渡し、Bが何か演算をして結果をAに返す使われ方が多いです。
そのとき、AがBに対して平文を秘匿したいだけでなく、BがAに対してどのような計算をしたか秘匿したい場面があります。
たとえばAが暗号文$c_1$, $c_2$, ...を作ってBに渡し、Bが計算して$d$を返したときに、Aが「$d$は$c_5$と$c_{20}$を足したものである」と分かっては困る場合です（もちろん暗号文を復号して自明に分かる場合を除きます）。

すなわち直接作られた暗号文と、暗号文から何か処理をして得られた暗号文の区別ができて欲しくないのです。この性質を回路プライバシーといいます。ある暗号文がどういう回路で計算されたかが隠されているという意味です。

今回提案したL2準同型暗号は一度掛け算すると暗号文の大きさが変わってしまうので掛け算したという情報は隠せないのですが、それ以外の演算の回路プライバシーを満たすようにできます。
実際にはSXDH仮定の下で、$Enc(0)$を足したり$Enc(1)$を掛けたりすると元の暗号文と同じか判別できなくなります。

$c = Enc(x)$に対して$c' := c + Enc(0) = Enc(x + 0) = Enc(x)$を作ると$c$と同じ平文の暗号文だが$c$と$c'$を見て、平文が同じだと判別できないだけでなく$c$から$c'$を作ったかも分からないということです。

まとめ

従来のElGamal暗号の安全性の根拠となるDDHを紹介しました。
私たちが提案したL2準同型暗号はDDHを2個くっつけたようなSXDH仮定を根拠に安全性を示しています。
また暗号文の計算に使われた計算式の情報を隠す回路プライバシーという概念を紹介しました。