定理(エルガマル暗号)の証明 - 暗号理論教室

定理(エルガマル暗号)の証明のアイデア

構成(エルガマル暗号)の公開鍵と暗号文は、

• pk = g^x, c = (g^r, m g^xr).

判定DH仮定より、DH組(g^x,g^r,g^xr)はランダムな群要素の3つ組(g^x,g^r,g^s)と
区別がつかない。

よって、(pk,c)は

• pk' = g^x, c' = (g^r, m g^s).

と区別がつかない。

(pk',c')は完全にmを隠しているので、(pk,c)も（効率的な攻撃者に対しては）mを隠す。

定理(エルガマル暗号)の証明

エルガマル暗号に対する任意の効率的な攻撃者をAとする。
Aの成功確率 ｜ Pr[CPA_A(n) = 1] - 1/2 ｜ がネグリジブルであることを示したい。

Aを用いて判定DH仮定における識別者Dを構成する：

識別者D: par=(q,g), (g₁,g₂,g₃)を入力として、

• pk=(q,g,g₁)を入力としてAを起動する。
  • Aから2つのメッセージからなるチャレンジクエリ(m₀,m₁)を受け取ったら、
    • m₀もm₁も<g>の要素であることを確認する。(そうでなければアボート。)
    • 0または1をランダムに選択し、bとする。
    • c* = (g₂, m_bg₃) をチャレンジクエリに対する応答として返す。
• Aが出力b'で終了したら、b =^? b' の１ビットを出力とする。

[識別者Dの解析]:

• Dへの入力(g₁,g₂,g₃)がランダムな群要素の3つ組(g^x,g^r,g^s)であるとき、
  • c*の第2成分m_bg^sはbと独立なランダムな群要素となる。
  • よって、Pr[b = b'] = 1/2.
• Dへの入力(g₁,g₂,g₃)がDH組(g^x,g^r,g^xr)であるとき、
  • c* = (g^r, m_bg^xr) の分布は正しいエルガマル暗号文のそれと同じ。
  • よって、Pr[b = b'] = Pr[CPA_A(n) = 1].

以上より、Dの識別利得は、

• ｜ Pr[CPA_A(n) = 1] - 1/2 ｜

に等しく、判定DH仮定の下でこれはネグリジブルである。
Q.E.D.

上へ

---