TY - JOUR

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

AU - Konoma, Chisato

AU - Mambo, Masahiro

AU - Shizuya, Hiroki

PY - 2004/5

Y1 - 2004/5

N2 - 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.

AB - 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.

KW - Computing problem

KW - Decision problem

KW - Diffie-Hellman problem

KW - Discrete logarithm problem

KW - Factoring problem

KW - Square-root exponent

UR - http://www.scopus.com/inward/record.url?scp=2642571834&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=2642571834&partnerID=8YFLogxK

M3 - Review article

AN - SCOPUS:2642571834

SN - 0916-8508

VL - E87-A

SP - 1083

EP - 1091

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 5

ER -