判定 Diffie–Hellman 假设

形式陈述 ​

令 $\mathsf{GrpGen}(1^{\lambda })$ 输出可高效运算的素数阶循环群 $(G,q,g)$，其中 $G=⟨g⟩$，群描述和元素编码均公开。定义两个由同一安全参数公理库安全参数Security parameter共同索引密码算法族、资源规模与失败概率的渐近尺度。索引的分布：

$$\begin{array}{rl}{\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{array}$$

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

$${\mathrm{Adv}}_{\mathsf{GrpGen},A}^{\mathsf{DDH}}(\lambda )=|\text{Pr}[A({\mathcal{D}}_0(\lambda ))=1]-\text{Pr}[A({\mathcal{D}}_1(\lambda ))=1]|.$$

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

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

能解CDH公理库计算 Diffie–Hellman 假设Computational Diffie–Hellman assumption · CDH assumption在参数化循环群族中，由随机群幂高效计算共享群元素 g^(ab) 的成功概率可忽略。即可判定 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,m{h}^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 把群上的代数困难转成分布不可区分公理库不可区分性Computational indistinguishability任意高效判别器区分两个分布族的优势都是可忽略量。语言，常用于证明 ElGamal、匿名化协议、承诺与伪随机构造的计算安全。一个归约应给出从方案判别器到 DDH 判别器的接口模拟和优势等式或损失，而不能只说方案“基于 DH”。

假设的适用性高度依赖群选择。需要配对功能的协议往往在某个源群中接受 DDH 容易，并改用 SXDH、XDH 或其他群别假设；普通 DH 系统则倾向选择没有已知高效 DDH 测试的素数阶群。每种替代假设都必须重新写清群、对手能力、实验分布和优势，不能把缩写视为可互换标签。

参考资料

• 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。