Paper 2005/111

Weak Composite Diffie-Hellman is not Weaker than Factoring

Kooshiar Azimian, Javad Mohajeri, and Mahmoud Salmasizadeh

Abstract

In1985, Shmuley proposed a theorem about intractability of Composite Diffie-Hellman [Sh85]. The Theorem of Shmuley may be paraphrased as saying that if there exist a probabilistic poly-time oracle machine which solves the Diffie-Hellman modulo an RSA-number with odd-order base then there exist a probabilistic algorithm which factors the modulo. In the other hand factorization of the module obtained only if we can solve the Diffie-Hellman with odd-order base. In this paper we show that even if there exist a probabilistic poly-time oracle machine which solves the problem only for even-order base and abstain answering the problem for odd-order bases still a probabilistic algorithm can be constructed which factors the modulo in poly-time for more than 98% of RSA-numbers.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Computational ComplexityDiffie-HellmanFactoring
Contact author(s)
kushyaar @ yahoo com
History
2005-04-15: received
Short URL
https://ia.cr/2005/111
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/111,
      author = {Kooshiar Azimian and Javad Mohajeri and Mahmoud Salmasizadeh},
      title = {Weak Composite Diffie-Hellman is not Weaker than Factoring},
      howpublished = {Cryptology ePrint Archive, Paper 2005/111},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/111}},
      url = {https://eprint.iacr.org/2005/111}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.