Paper 2011/263

The Computational Square-Root Exponent Problem- Revisited

Fangguo Zhang

Abstract

In this paper, we revisit the Computational Square-Root Exponent Problem (CSREP), and give a more generic condition such that CSREP is polynomial-time equivalent to the Computational Diffie-Hellman Problem (CDHP) in the group with prime order. The results obtained in this paper contain Zhang \textit{et al.}'s results at IWCC2011. We also analyze the existence of such condition. Although primes satisfying such condition are rare (compare to all primes), it can be regarded as an evidence that CSREP may be equivalent to CDHP.

Note: Thanks to Prof. Steven Galbraith for bringing the paper of Roh et al to my attention. I added a short description about Roh et al.'s work at the end of Section 4.3 .

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
isszhfg @ mail sysu edu cn
History
2011-06-07: last of 3 revisions
2011-05-28: received
See all versions
Short URL
https://ia.cr/2011/263
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/263,
      author = {Fangguo Zhang},
      title = {The Computational Square-Root Exponent Problem- Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2011/263},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/263}},
      url = {https://eprint.iacr.org/2011/263}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.