判定 Diffie–Hellman 假设

形式陈述

令 $\mathsf{GrpGen}(1^\lambda)$ 输出可高效运算的素数阶循环群 $(G,q,g)$ ，其中 $G=\langle g\rangle$ ，安全参数 $1^\lambda$ 、群描述和元素编码均公开。定义两个由同一安全参数索引的分布：

\begin{aligned} \mathcal D_0(\lambda)&=(G,q,g,g^a,g^b,g^{ab}),\\ \mathcal D_1(\lambda)&=(G,q,g,g^a,g^b,g^c), \end{aligned}

其中每次先采样 $(G,q,g)\leftarrow\mathsf{GrpGen}(1^\lambda)$ ，再独立均匀采样 $a,b,c\leftarrow\mathbb Z_q$ ；指数运算都按 $q$ 取模。对 PPT 判别器 $A$ ，采用接受概率差归一化的 DDH 优势为

\operatorname{Adv}^{\mathsf{DDH}}_{\mathsf{GrpGen},A}(\lambda) =\left| \Pr[A(1^\lambda,\mathcal D_0(\lambda))=1] -\Pr[A(1^\lambda,\mathcal D_1(\lambda))=1] \right|.

概率包含群生成、全部指数和 $A$ 的随机性。DDH 假设断言对每个 PPT $A$ ，该优势随 $\lambda$ 可忽略。等价地，可以均匀选择隐藏位 $\beta$ 并发送 $\mathcal D_\beta$ ；若优势写成 $|2\Pr[\beta'=\beta]-1|$ ，数值与上式相同，而写成 $|\Pr[\beta'=\beta]-1/2|$ 会少一个因子 $2$ 。

第三项 $g^c$ 是独立均匀群元素，不是随机 bit，也不是从群表示中随便挑一串。合法元素采样、子群成员资格和参数生成都是分布定义的一部分。若协议工作在复合阶群、椭圆曲线的特定子群或非对称配对群中，必须对那个准确群族重新陈述假设。

能解CDH即可判定 DDH：由 $(g^a,g^b)$ 算出 $g^{ab}$ ，再与第三项比较。因此，若 CDH 容易则 DDH 也容易；取逆否命题，DDH 困难蕴含 CDH 困难。反向不成立于一般模型：CDH 可能仍难，而某种额外结构已经足以识别 DH tuple。

直觉

CDH 问“能否造出交叉项”，DDH 问“给出的第三项是不是交叉项”。判定任务通常更弱：攻击者无需知道 $a$ 、 $b$ 或算出目标，只要找到任何可重复的关系测试即可。DDH 假设要求真实三元组在高效观察者眼中像三个独立随机幂。

这种“像随机”的结论只针对指定群中的 tuple 分布。它不是说 $g^{ab}$ 在知道指数的一方看来仍神秘，也不是说群表示的每个 bit 都统计均匀；它说的是没有高效算法能在两个完整实验之间取得非可忽略的归一化区分优势。

例子与边界

ElGamal 的标准 IND-CPA 证明说明 DDH 如何服务于加密。公钥为 $h=g^x$ ，随机数为 $r$ 时，密文包含 $(g^r,mh^r)$ 。若 $(g^x,g^r,g^{xr})$ 与 $(g^x,g^r,g^c)$ 不可区分，就可以在混合游戏中把掩码 $h^r$ 替换成独立随机群元素；乘上固定消息 $m$ 后仍均匀，于是隐藏挑战消息。这里需要判定不可区分性，单凭“攻击者算不出 $g^{xr}$ ”并不足以完成这一步替换。

双线性配对展示 DDH 可失败的群。若存在高效非退化映射 $e:G\times G\to G_T$ ，并满足 $e(g^u,g^v)=e(g,g)^{uv}$ ，那么可检查

e(g^a,g^b)\stackrel{?}=e(g,g^{ab}).

真实 tuple 恒通过，独立随机第三项只以约 $1/q$ 的概率通过，因此 DDH 很容易；这并未自动给出 $g^{ab}$ 本身，CDH 仍可能被认为困难。配对密码正是利用了这处分离。

“某条椭圆曲线上的 DDH”也不够精确。同一曲线可能含多个子群，外部配对、扭曲映射或可高效计算的字符会改变判定难度。若实现不验证收到的点属于预期素数阶子群，攻击者面对的便不是定义中的分布，理论假设无法替代参数与成员验证。

DDH 是经典 PPT 假设。允许量子对手时，Shor 算法可恢复指数并以压倒性优势判定 tuple；允许预处理、辅助输入或多实例相关采样时，也应在实验中明确这些能力，而不是默认由单实例定义覆盖。

推论与应用

DDH 把群上的代数困难转成分布不可区分语言，常用于证明 ElGamal、匿名化协议、承诺与伪随机构造的计算安全。一个归约应给出从方案判别器到 DDH 判别器的接口模拟和优势等式或损失，而不能只说方案“基于 DH”。

假设的适用性高度依赖群选择。上面的对称配对使源群 DDH 容易，而KZG 多项式承诺恰好使用这种配对来检查商多项式的乘法关系，其逐点求值绑定可归约到给定公开幂表的 $d$ -SDH 问题。配对能检验指数关系，与攻击者能否构造出指定的源群元素，是两个不同问题。

在非对称配对 $e:G_1\times G_2\to G_T$ 中，输入被分到两个源群，不能直接照搬上述同群 DDH 测试。SXDH 断言 DDH 在两个源群中都困难；XDH 则要求指定源群中的 DDH 困难。因而“接受某个源群 DDH 容易”不能笼统归于 SXDH。每种假设都须写清群、对手可用的映射与公开辅助元素，才能判断它是否支持所需归约。

参考资料

Dan Boneh, “The Decision Diffie–Hellman Problem,” ANTS III, LNCS 1423, 1998。
Dan Boneh and Victor Shoup, A Graduate Course in Applied Cryptography, version 0.6, 2023，DDH and ElGamal security。
Antoine Joux, “A One Round Protocol for Tripartite Diffie–Hellman,” ANTS IV, 2000，bilinear maps and decisional structure。

形式陈述 ​

反向链接

形式陈述