计算 Diffie–Hellman 假设

形式陈述 ​

设 $\mathsf{GrpGen}$ 是概率多项式时间群生成算法，输入 $1^{\lambda }$ 后输出可高效运算的有限循环群公理库循环群Cyclic group由单个元素的整数次幂生成的群。描述 $(G,q,g)$，其中本页取 $G=⟨g⟩$ 为 $q$ 阶群。编码、群运算、相等性测试和从 ${\mathbb{Z}}_q$ 采样指数都必须相对 $\lambda$ 高效，且 $q=q(\lambda )$ 随安全参数增长；固定一个小群上的经验困难不构成渐近假设。

计算 Diffie–Hellman 实验定义为

$$\begin{array}{rl}(G,q,g)& \leftarrow \mathsf{GrpGen}(1^{\lambda }),\\ a,b& \leftarrow {\mathbb{Z}}_q,\\ Z& \leftarrow A(G,q,g,g^a,g^b),\end{array}$$

当且仅当 $Z=g^{ab}$ 时实验输出 $1$。对手 $A$ 的成功函数为

$${\mathrm{Succ}}_{\mathsf{GrpGen},A}^{\mathsf{CDH}}(\lambda )=\text{Pr}[Z=g^{ab}],$$

概率覆盖群参数生成、指数和对手的全部随机币。CDH 假设断言：对每个 PPT 对手 $A$，该成功概率都是 $\lambda$ 的可忽略函数。这里没有均匀隐藏位，也没有天然的 $1/2$ 猜测基线，因此用直接成功概率而非区分优势；若某个变体扣除猜测基线，必须另行声明。

问题的目标是群元素 $g^{ab}$，不是指数乘积 $abmodq$。若能高效求离散对数，就能从 $g^a$ 恢复 $a$，进而计算 $(g^b{)}^a=g^{ab}$，所以离散对数可解会使 CDH 可解。由此只能得到“CDH 困难蕴含离散对数困难”；目前对一般群族没有从 CDH 求解器恢复离散对数的通用反向归约，二者不能写成等价假设。

CDH 还应与判定版本分开。DDH公理库判定 Diffie–Hellman 假设Decisional Diffie–Hellman assumption · DDH assumption随机 Diffie–Hellman 三元组与以独立随机群元素结尾的三元组对高效判别器不可区分。询问第三个群元素是否等于 $g^{ab}$，而 CDH 要求实际产出共享元素。Gap-CDH 等变体会额外给对手一个 DDH 判定 oracle，再假设计算目标仍困难；增加该接口得到的是另一项更强建模承诺，不属于基础 CDH 实验。

直觉 ​

公开的 $g^a$ 和 $g^b$ 分别把两个指数藏进群元素。知道 $a$ 的一方可以把 $g^b$ 再乘幂，知道 $b$ 的一方也能对 $g^a$ 做同样操作；旁观者虽然看见两份公开值，却被要求直接合成那个“交叉项” $g^{ab}$。CDH 把这一步是否高效可行独立成计算问题，而不把密钥协商的认证、派生或消息流程混进假设。

它是一项关于群族与攻击模型的平均情形假设。随机指数、生成算法产生的参数、允许的预处理和算法资源共同决定实例分布；“尚无已知攻击”只是采用假设的证据，不是定义本身。

例子与边界 ​

经典 Diffie–Hellman 协议正好产生 CDH 实例。Alice 发布 $A_0=g^a$，Bob 发布 $B_0=g^b$，双方分别计算 $B_0^a$ 与 $A_0^b$，都得到 $g^{ab}$。被动窃听者若能赢得上述 CDH 实验，就能恢复这个原始共享群元素；实际协议还需 KDF 把它与 transcript、身份和用途绑定，CDH 本身并不声明派生密钥均匀或协议已认证。

群验证是模型落地时的边界。若攻击者可以提交不在规定素数阶子群中的元素，或群含有未处理的小阶因子，诚实方的幂运算可能泄露私有指数模小因子的值。标准 CDH 实验只给随机合法群元素，不能自动覆盖恶意参数、无效曲线点或小子群查询；具体协议必须验证群描述和成员资格，或在安全模型中显式加入这些能力。

小数值演示只能验证代数正确性，不能作为安全证据。群阶必须随 $\lambda$ 增长并按已知经典、量子算法选择参数；Shor 算法能在量子多项式时间内求有限循环群离散对数，因此经典群上的 CDH 假设不抵抗具备通用量子计算能力的对手，除非攻击模型明确仍限制为经典 PPT。

成功计算部分信息也不等于赢得 CDH。某些协议需要共享元素的某个 bit、哈希值或相关谓词保持隐藏，那会引出 hard-core、hashed DH 或专门的密钥不可区分假设；不能只凭“完整元素难求”无条件推出所有派生信息都安全。

推论与应用 ​

CDH 是分析Diffie–Hellman 密钥交换公理库Diffie–Hellman 密钥交换Diffie–Hellman key exchange双方公开交换群幂并在离散对数型假设下导出共享秘密的协议。、某些签名与身份协议时常见的底层困难假设。归约若把破坏协议的对手变成 CDH 求解器，必须同时报告运行时间、群操作数、查询次数与成功概率损失，才能把抽象的计算安全公理库计算安全Computational security仅要求任何资源受限攻击者的成功优势足够小的安全概念。结论落实到参数选择。

CDH 只保证一个计算任务困难，不直接给出密钥不可区分、IND-CPA 加密或主动攻击安全。需要“共享值看起来像随机群元素”的构造通常采用 DDH 或 hashed-DH 类假设；需要身份认证时还要签名、MAC 或认证密钥交换结构。把这些上层性质与 CDH 分开，能准确看出每项协议结论究竟消耗了哪一项假设。

参考资料

• Whitfield Diffie and Martin E. Hellman, “New Directions in Cryptography,” IEEE Transactions on Information Theory 22(6), 1976。
• Dan Boneh and Victor Shoup, A Graduate Course in Applied Cryptography, version 0.6, 2023，Diffie–Hellman problems and reductions。
• Victor Shoup, “Lower Bounds for Discrete Logarithms and Related Problems,” EUROCRYPT 1997，generic-group perspective on discrete-logarithm problems。