Title :
Diffie-Hellman, decision Diffie-Hellman, and discrete logarithms
Author :
Maurer, Ueli ; Wolf, Stefan
Author_Institution :
Dept. of Comput. Sci., Eidgenossische Tech. Hochschule, Zurich, Switzerland
Abstract :
Let G be a cyclic group of order n. With respect to polynomial-time non-uniform generic reductions, the Diffie-Hellman problem and the discrete logarithm problem are equivalent in G if and only if n contains no multiple large prime factors. The Diffie-Hellman decision problem is equivalent to the Diffie-Hellman problem in G if and only if all prime factors of n are small
Keywords :
computational complexity; decision theory; group theory; information theory; Diffie-Hellman decision problem; Diffie-Hellman problem; cyclic group; decision Diffie-Hellman problem; discrete logarithm problem; polynomial-time nonuniform generic reductions; prime factors; Computer science; Cryptography; DH-HEMTs; Polynomials; Protocols;
Conference_Titel :
Information Theory, 1998. Proceedings. 1998 IEEE International Symposium on
Conference_Location :
Cambridge, MA
Print_ISBN :
0-7803-5000-6
DOI :
10.1109/ISIT.1998.708932