DDH假设指的是区分元组 ( g , g x , g y , g x y ) (g,g^x,g^y,g^{xy}) (g,gx,gy,gxy)和 ( g , g x , g y , g z ) (g,g^x,g^y,g^z) (g,gx,gy,gz)是困难的，具体定义如下：

设 G G G是阶为大素数 q q q的群， g g g是 G G G的生成元， x , y , z ← R Z q x,y,z← _RZ_q x,y,z←R​Zq​，则以下两个分布:

是计算上不可区分的，则称DDH假设。

具体地说，一个敌手A，A区分R和D的优势： 其中κ是安全参数。

可以通过一个随机函数的例子来解释：

假设有三个角色：挑战者，真随机源头，随机数生成算法。 其过程为： 真随机源产生一个真随机数R， 随机函数通过一个算法生成一个随机数R’， 将R和R’同时发送给挑战者，让挑战者区分哪个是真随机源产生的随机数，哪个是随机函数产生的随机数。如果挑战者能够区分两者，则我们说挑战成功。

区分计算不可区分和统计不可区分的关键点在于挑战者的能力。 如果挑战者的能力是无限的，无限能力的挑战者都不能挑战成功那么他就是统计不可区分； 如果挑战者的能力是多项式的，多项式能力的挑战者不能挑战成功那么他就是计算不可区分的。

随机数中间有很多的统计特性。随着挑战者的能力不断增大，其能够分析的R和R’的统计特性就不断增多:

如果一个挑战者C的能力是：只能够统计0,1的个数。那么当R‘全为1的时候，挑战者能够区分R’和R。当R’为01010101…，01交替出现的时候，那么挑战者C就无法区分R和R‘。

当挑战者的能力到达多项式时，他分析了在此时他的能力下R和R’所有的统计特性，依然无法挑战成功，那么我们就说这是计算不可区分的。（为什么是多项式，因为一般情况下，我们认为超过多项式时间复杂度的算法计算机就没法处理了。）

当挑战者的能力是无限时，也就是说挑战者分析了R和R’所有的统计特性，依然无法挑战成功，那么这个时候，从统计学上（或者说概率分布）来看，那么R和R’就是一回事了，因此叫统计不可区分。

参考： https://blog.csdn.net/weixin_44029550/article/details/111387705 https://zhuanlan.zhihu.com/p/145175617