DDH仮定

jacobi記号 supersingular_curve ペアリング

ある群 Gの g, a, bを持ってきて、

g^{ab}は g^a, g^bを知っていたとしてもランダムな値に見える、という仮定

ところでDDH仮定は Z_p^* では成り立たない。なぜなら g^a, g^bのそれぞれに対してjacobi記号をとって積をとって、 g^{ab}のjacobi記号と比べることで区別できる場合があるから（1/2くらいの確率でこれがあたる？）

また、楕円曲線DDHで、mod p素数で位数が log^2(p)程度に小さい Gをとってきた時にも仮定が崩れることがわかっている（ supersingular curveなど）。この問題はペアリングで次のように解けてしまうから

G, aG, bG, cGがあって、 cG = abGかどうかを調べる。

e(aG, bG) = e(G, G)^{ab}

e(G, cG) = e(G, G)^c

なので cG = abGなら上記は一致する