根据我的理解，由于离散对数（DL）问题被认为很难，因此CDH也是如此。

/>由于CDH被认为很困难，所以DDH也是如此。

在Wikipedia上有关DDH的文章中，它提到DDH被认为比CDH更有力。这是什么意思？

#1 楼

问题：


对数离散问题：给定$ y $，找到$ x $，使$ g ^ x = y $。
计算Diffie-Hellman问题：给定$ y_1 = g ^ {x_1} $和$ y_2 = g ^ {x_2} $（但不包括$ x_1 $和$ x_2 $），则找到$ y = g ^ {x_1·x_2} $。
决策Diffie-Hellman问题：给定$ y_1，y_2，y_3 $，确定它们的形式为$ y_1 = g ^ {x_1} $，$ y_2 = g ^ {x_2} $和$ y_3 = g ^ {x_1· x_2} $代表某些$ x_1，x_2 $（您不必查找）。假设它们有50％的概率确实是这种形式，并且只是随机选择了50％的概率，而您必须以比50％更好的概率猜测正确。


所有这三个这些定义在任何（乘法编写）组中，在某些组中很难定义，而在其他组中则比较容易。 （实际上，我们实际上并不需要一个组，一个带有生成器$ g $的半组就足够了。但是在组中它更有趣。）

哪个更难？
<现在，如果您有一台机器（程序，oracle）可以（有效地）解决某些组中的离散对数问题，则可以轻松地构造计算Diffie-Hellman问题（在同一组中）的求解器：


仅从$ y_2 $计算$ x_2 $并计算$ y =（y_1）^ {x_2} $。

没有已知的（通用）方法另一个方向。

如果您有计算Diffie-Hellman问题的求解器，还可以决定决策Diffie-Hellman问题：


只计算将$ y $转换为$ y_1 $和$ y_2 $，并检查$ y = y_3 $。

没有另一个方向的（通用有效）已知方法。

这意味着DDH至少与CDH一样容易（甚至更容易），而CDH至少与DL一样容易。或者，反过来，DL至少与CDH一样硬，而CDH至少与DDH一样硬。其中“硬”定义为“对合理的用户不可行”。


如果DDH较硬，则CDH也必须较硬（但不一定相反）。
如果CDH较硬，则DL必须较硬（但不一定相反）。

因此，DDH的硬度是一个比CDH的硬度更强的假设（在较少的组中有效），而CDH的硬度仍然比DL的硬度强。

正如Thomas Pornin在注释中，有一些椭圆曲线组，其中DDH容易，但CDH和DL很难（假定），并且在基于配对的加密中使用。这是一个很好的指示（尽管还没有证据），说明DL和CDH问题确实比DDH更加困难。

评论

$ \ begingroup $
为了完整起见，基于配对的加密方法是使用特制的椭圆曲线，其中假设DL和CDH困难，而DDH则容易。因此，我们有一些很合理的理由认为CDH严格比DDH难（或者至少我们强烈希望如此）。
$ \ endgroup $
–托马斯·波宁（Thomas Pornin）
2011-12-25 23:27
$ \ begingroup $
@Thomas Pornin您提到的“合理原因”和“热望”都只涉及那些特定的（即配备配对的）群体，是吗？换句话说，在更通用的（例如，标准椭圆曲线）组中，CDH和DDH可能仍然完全相同。
$ \ endgroup $
– BD107
20年1月12日在23:52
$ \ begingroup $
@ BD107没有“更通用的组”之类的东西。如果它们在“一个通用组”中是等效的，则表示从一个通用组到另一个通用组（即，它不使用特定的组结构知识）。如果存在，则适用于所有组。因为我们假设这不存在（请参阅Thomas的示例），所以它们在一般上并不等效。但是，它们在某些特殊组中可能是等效的。
$ \ endgroup $
–PaŭloEbermann
20年1月15日在23:14
$ \ begingroup $
我明白了。因此，换句话说，CDH和DDH在所有组中都很容易，但在所有组中都很难做到（如配对情况所示）。那是对的吗？
$ \ endgroup $
– BD107
20年1月16日在21:01

#2 楼

这意味着，如果您具有对CDH的oracle访问权限，则可以解决DDH，但我们不知道是否存在减少的方法。

从技术上讲，假设$ \ mathsf {CDH} $是一个Oracle，它在给定$（g ^ x，g ^ y）$的情况下找到$ g ^ {xy} $，然后对于DDH实例，例如说$（a，b，c）$，如果$ \ mathsf {CDH} $的输出等于$ c $，则可以用$（a，b）$供给$ \ mathsf {CDH} $并输出$ 1 $，否则输出$ 0 $。给定类似的oracle $ \ mathsf {DDH} $，没有这样的归约法可以解决CDH。

我在数学的堆栈交换中发现了CDH和Discrete Log之间的难题类似的问题类型和答案更为全面。您可能会发现其中的参考更为有用。

#3 楼

除了贾拉杰（Jalaj）的正确答案，我还想对您的其中一项陈述提出异议：

“根据我的理解，由于离散日志（DL）问题被认为很困难，因此CDH也是如此”

实际上并非如此。现在，如果您可以解决DL问题，那么CDH问题就很容易了（因此CDH问题并不比DL问题难。）但是，没有其他方法可知。给定一个可以解决CDH问题的预言家，没有已知的方法可以使用它来解决DL问题。因此，CDH假设比DL假设具有更强的假设。

现在，在实践中，对于乘法组$ Z ^ * / p $，解决CDH问题的唯一已知方法是：尝试重新分配其中一个秘密指数（通过解决DL问题）；但是，可能还有其他方法可以解决CDH问题，而这是没人想到的。

评论

$ \ begingroup $
实际上，Maurer和Wolf在打破Diffie-Hellman协议与计算离散对数之间的关系中证明了两者的等价性，这是基于对组顺序的一些假设而得出的。
$ \ endgroup $
–贾拉杰
2011-12-16 21:11


$ \ begingroup $
@Jalaj：如果您浏览摘要，它仅适用于“ | G |的所有多个质数都是log | G |的多项式”的组。通常，对于精选的$ p $值而言，这是不正确的。
$ \ endgroup $
–雨披
2014年1月24日在16:51

#4 楼

本文描述了有助于将离散对数问题简化为计算Diffie-Hellman问题的理论助推器。


由于从离散对数到Diffie-Hellman的多项式时间缩减的“圣杯”似乎还有很长的路要走，因此研究一下哪些类型的附加特征可以弥补这一差距很有趣。 。有多种方法可以缓解该问题：一种可以只求一个次指数时间，而不能求多项式时间。可以使离散对数求解器访问强大的Oracle，例如单素非p或anyprime-but-p离散对数求解器，回答是或不是的oracle或oracle。整数并且可以假设某些数论猜想，换句话说，可以用启发式复杂度分析来满足。


这些参考文献追踪了其他重要的工作。