The relationship between breaking the Diffie-Hellman protocol and computing discrete logarithms
The relationship between breaking the Diffie-Hellman protocol and computing discrete logarithms
复制标题
DOI：
10.1137/s0097539796302749
复制
发表时间：
1999-05-26
影响因子：
1.6
通讯作者：
Wolf, S
中科院分区：
文献类型：
--
作者：
Maurer, UM;Wolf, S
证明了关于Diffie-Hellman密钥交换协议安全性的一致和非一致结果。首先，证明了在阶为\G\ = Pi p（i）（ei）的循环群G中，存在一个算法，该算法将G中的离散元的计算减少到破坏G中的Diffie-Hellman协议，并且具有复杂性根max{nu（p（i））}. (log\G\）（O（1）），其中nu（p）表示区间[p - 2 root p + 1; p + 2 root p + 1]中所有数d的最大素因子的集合的最小值。在nu（p）是logp中的多项式这一未被证明但似乎可信的假设下，这种简化意味着Diffie-Hellman问题和离散对数问题在G中是多项式时间等价的。其次，证明了Diffie-Hellman问题和离散对数问题对于其阶属于某些类的群在一致意义上是等价的：存在一个多项式时间约简算法，该算法适用于所有这些群。此外，它表明，打破Diffie-Hellman协议的一个小的，但不可忽略的部分的实例是同样困难的，因为打破它的所有实例。最后，高效的建设群体的算法减少离散对数问题的Diffie-Hellman问题是有效的构造。
Both uniform and nonuniform results concerning the security of the Diffie-Hellman key-exchange protocol are proved. First, it is shown that in a cyclic group G of order \G\ = Pi p(i)(ei), where all the multiple prime factors of \G\ are polynomial in log \G\, there exists an algorithm that reduces the computation of discrete logarithms in G to breaking the Diffie-Hellman protocol in G and has complexity root max{nu(p(i))}.(log\G\)(O(1)), where nu(p) stands for the minimum of the set of largest prime factors of all the numbers d in the interval [p - 2 root p + 1; p + 2 root p + 1]. Under the unproven but plausible assumption that nu(p) is polynomial in log p, this reduction implies that the Diffie-Hellman problem and the discrete logarithm problem are polynomial-time equivalent in G. Second, it is proved that the Diffie-Hellman problem and the discrete logarithm problem are equivalent in a uniform sense for groups whose orders belong to certain classes: there exists a polynomial-time reduction algorithm that works for all those groups. Moreover, it is shown that breaking the Diffie-Hellman protocol for a small but nonnegligible fraction of the instances is equally difficult as breaking it for all instances. Finally, efficient constructions of groups are described for which the algorithm reducing the discrete logarithm problem to the Diffie-Hellman problem is efficiently constructible.