Complexity analysis of the cryptographic primitive problems through square-root exponent

Chisato Konoma, Masahiro Mambo, Hiroki Shizuya

Research output: Contribution to journalReview articlepeer-review

10 Citations (Scopus)


To examine the computational complexity of cryptographic primitives such as the discrete logarithm problem, the factoring problem and the Diffle-Hellman problem, we define a new problem called square-root exponent, which is a problem to compute a value whose discrete logarithm is a square root of the discrete logarithm of a given value. We analyze reduction between the discrete logarithm problem modulo a prime and the factoring problem through the square-root exponent. We also examine reductions among the computational version and the decisional version of the square-root exponent and the Diffie-Hellman problem and show that the gap between the computational square-root exponent and the decisional square-root exponent partially overlaps with the gap between the computational Diffie-Hellman and the decisional Diffie-Hellman under some condition.

Original languageEnglish
Pages (from-to)1083-1091
Number of pages9
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number5
Publication statusPublished - 2004 May


  • Computing problem
  • Decision problem
  • Diffie-Hellman problem
  • Discrete logarithm problem
  • Factoring problem
  • Square-root exponent


Dive into the research topics of 'Complexity analysis of the cryptographic primitive problems through square-root exponent'. Together they form a unique fingerprint.

Cite this