Complexity Analysis of the Cryptographic Primitive Problems through Square-Root Exponent
Summary :
To examine the computational complexity of cryptographic primitives such as the discrete logarithm problem, the factoring problem and the Diffie-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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E87-A No.5 pp.1083-1091
- Publication Date
- 2004/05/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Chisato KONOMA, Masahiro MAMBO, Hiroki SHIZUYA, "Complexity Analysis of the Cryptographic Primitive Problems through Square-Root Exponent" in IEICE TRANSACTIONS on Fundamentals,
vol. E87-A, no. 5, pp. 1083-1091, May 2004, doi: .
Abstract: To examine the computational complexity of cryptographic primitives such as the discrete logarithm problem, the factoring problem and the Diffie-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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e87-a_5_1083/_p
Copy
@ARTICLE{e87-a_5_1083,
author={Chisato KONOMA, Masahiro MAMBO, Hiroki SHIZUYA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Complexity Analysis of the Cryptographic Primitive Problems through Square-Root Exponent},
year={2004},
volume={E87-A},
number={5},
pages={1083-1091},
abstract={To examine the computational complexity of cryptographic primitives such as the discrete logarithm problem, the factoring problem and the Diffie-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.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - Complexity Analysis of the Cryptographic Primitive Problems through Square-Root Exponent
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1083
EP - 1091
AU - Chisato KONOMA
AU - Masahiro MAMBO
AU - Hiroki SHIZUYA
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E87-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2004
AB - To examine the computational complexity of cryptographic primitives such as the discrete logarithm problem, the factoring problem and the Diffie-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.
ER -
English
