决策 Diffie-Hellman DDH 和 CDH

密码学中的 Diffie-Hellman 问题有几种变体：计算问题 (CDH) 和决策问题 (DDH)。这篇文章将解释两者，并举例说明前者如何困难而后者如何简单。

迪菲-赫尔曼问题
Diffie-Hellman 问题是针对阿贝尔群制定的。我们想到的主要群是非零整数以大素数 p为模的乘法群。但我们从更普遍的角度开始，因为迪菲-赫尔曼问题对于某些群体来说比其他群体更难，正如我们将在下面看到的。

设 g 为群的生成元。当我们将群运算想象为乘法时，这意味着群中的每个元素都是 g的幂。

计算迪菲-赫尔曼问题
设 a 和 b 是两个整数。给定 g a 和 g b，CDH 问题是计算 g ab。请注意，指数是 ab 而不是 a + b。后者很简单：只需将 g a和 g b相乘即可。

为了计算 g ab 我们需要知道 a 或 b，但我们没有给出。求解任一指数都是离散对数问题，这对于某些组来说是不切实际的。

可以想象，有一种方法可以在不解决离散对数问题的情况下解决CDH，但是，此时，对CDH最有效的攻击是计算离散对数。

迪菲-赫尔曼密钥交换
Diffie-Hellman 密钥交换取决于 CDH 是一个难题的假设。

假设 Alice 和 Bob 都同意生成器 g，并分别选择私钥 a 和 b 。Alice 发送 Bob  g a  ，Bob 发送 Alice  g b。这不会泄露他们的私钥，因为离散对数问题（据信是）很难。现在，双方都计算 g ab 并将其用作共享密钥。Alice  通过 g b的a 次方 计算g ab，Bob  通过 g a的b 次方 计算g ab。

如果有人拦截了 Alice 和 Bob 之间的交换，他们将拥有 g a和 g b 并想要计算 g ab。这就是CDH。

当处理以大素数 p为模的整数时，如果 p -1 具有大因子，例如当 p  – 1 = 2 q 对于素数 q时，CDH 会很困难。如果 p -1 只有很小的因子，即如果 p -1 是“平滑的”，那么离散对数问题可以通过 Silver-Pohlig-Hellman 算法来处理 [1]。如果 p 很大并且 p -1 具有很大的质因数，据我们目前所知，CDH 是困难的。

决策迪菲-赫尔曼问题
DDH 问题也从 g a 和 g b的知识开始。但是，它不是要求计算 g ab，而是询问 对于随机选择的 c  ，是否可以以 优于 0.5 的概率区分g ab 和 g c 。

显然，DDH 比 CDH 弱，因为如果我们能够解决 CDH，我们就可以确定地知道 DDH 问题的答案。尽管如此，DDH 问题被认为对某些群体来说是困难的，例如某些椭圆曲线，但对其他群体来说则不然，如下所示。

乘法群 Mod  p的 DDH
假设我们正在处理以素数p为模的非零整数乘法群 。使用勒让德符号（即使对于非常大的数字也可以进行计算），您可以确定 g a 是否是平方 mod  p，当且仅当 a 为偶数时才会发生这种情况。因此，通过计算g a  mod  p的勒让德符号 ，我们知道a的奇偶性 。同理，我们可以求出b的奇偶性 。因此，我们知道 ab的奇偶性。如果 ab 是奇数但 g c 是平方 mod  p，我们知道 DDH 问题的答案是否定的。类似地，如果 ab 是偶数但 g c 不是平方 mod  p，我们也知道 DDH 问题的答案是否定的。

由于一半的正整数 mod  p 是平方，因此我们可以通过上面的奇偶校验参数在一半的情况下确定地回答 DDH 问题。如果我们的平价论证没有结论，我们就必须猜测。所以，总的来说，我们能够以 0.75 的概率正确回答 DDH 问题。