DDH assumption

• decisional Diffie–Hellman (DDH) assumption: 計算困難性仮定の一つ

記号については ElGamal暗号 > scheme 参照

DDH問題

• $x,y\leftarrow U(\cdots ,|G|-1)$
  • 確率変数 $X_0=(G,|G|,g,g^x,g^y,g^{xy})$
• $z\leftarrow U(\cdot )$
  • $X_1=(G,|G|,g,g^x,g^y,g^z)$

$X_0$ と $X_1$ を識別出来るか?

DDH仮定

DDH問題で攻撃者のadvantageがnegl
($\frac{1}{2}$ とほぼ変わらない)