Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-047 | 10th April 2005 00:00

Weak Composite Diffie-Hellman is not Weaker than Factoring

RSS-Feed




TR05-047
Authors: Kooshiar Azimian, Mahmoud Salmasizadeh, Javad Mohajeri
Publication: 19th April 2005 01:52
Downloads: 2902
Keywords: 


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.



ISSN 1433-8092 | Imprint