CDH 问题

定义

$$D{H}_g(h_1,h_2)=g^{in{d}_g{h}_1\cdot in{d}_g{h}_2}$$

如果对于任意的 PPT 敌手 A，知道 $G,q,g,h_1,h_2$ 的情况下，计算 $D{H}_g(h_1,h_2)$ 都是困难的，即：

$$Pr[A(G,q,g,g^x,g^y)=g^{xy}]\le negl(n)$$

则称 CDH 和 G 相关是困难的