International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Weak Composite Diffie-Hellman is not Weaker than Factoring

Authors:
Kooshiar Azimian
Javad Mohajeri
Mahmoud Salmasizadeh
Download:
URL: http://eprint.iacr.org/2005/111
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2005-12447,
  title={Weak Composite Diffie-Hellman is not Weaker than Factoring},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Computational Complexity, Diffie-Hellman, Factoring},
  url={http://eprint.iacr.org/2005/111},
  note={ kushyaar@yahoo.com 12887 received 14 Apr 2005},
  author={Kooshiar Azimian and Javad Mohajeri and Mahmoud Salmasizadeh},
  year=2005
}