Knowledge-of-exponent assumptions (KEAs) are a somewhat controversial but nevertheless commonly used type of cryptographic assumptions. While traditional cryptographic assumptions simply assert that certain tasks (like factoring integers or computing discrete logarithms) cannot be performed efficiently, KEAs assert that certain tasks can be performed efficiently, but only in certain ways. The controversy surrounding those assumptions is due to their non-falsifiability, which is due to the way this idea is formalised, and to the general idea that these assumptions are “strong”. Nevertheless, their relationship to existing assumptions has not received much attention thus far. In this paper, we show that the first KEA (KEA1), introduced by Damgård in 1991, implies that computing discrete logarithms is equivalent to solving the computational Diffie-Hellman (CDH) problem. Since showing this equivalence in the standard setting (i.e., without the assumption that KEA1 holds) is a longstanding open question, this indicates that KEA1 (and KEAs in general) are indeed quite strong assumptions.
Firas KRAIEM
Tohoku University
Shuji ISOBE
Tohoku University
Eisuke KOIZUMI
Tohoku University
Hiroki SHIZUYA
Tohoku University
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.
Copy
Firas KRAIEM, Shuji ISOBE, Eisuke KOIZUMI, Hiroki SHIZUYA, "On a Relation between Knowledge-of-Exponent Assumptions and the DLog vs. CDH Question" in IEICE TRANSACTIONS on Fundamentals,
vol. E104-A, no. 1, pp. 20-24, January 2021, doi: 10.1587/transfun.2020CIP0002.
Abstract: Knowledge-of-exponent assumptions (KEAs) are a somewhat controversial but nevertheless commonly used type of cryptographic assumptions. While traditional cryptographic assumptions simply assert that certain tasks (like factoring integers or computing discrete logarithms) cannot be performed efficiently, KEAs assert that certain tasks can be performed efficiently, but only in certain ways. The controversy surrounding those assumptions is due to their non-falsifiability, which is due to the way this idea is formalised, and to the general idea that these assumptions are “strong”. Nevertheless, their relationship to existing assumptions has not received much attention thus far. In this paper, we show that the first KEA (KEA1), introduced by Damgård in 1991, implies that computing discrete logarithms is equivalent to solving the computational Diffie-Hellman (CDH) problem. Since showing this equivalence in the standard setting (i.e., without the assumption that KEA1 holds) is a longstanding open question, this indicates that KEA1 (and KEAs in general) are indeed quite strong assumptions.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2020CIP0002/_p
Copy
@ARTICLE{e104-a_1_20,
author={Firas KRAIEM, Shuji ISOBE, Eisuke KOIZUMI, Hiroki SHIZUYA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On a Relation between Knowledge-of-Exponent Assumptions and the DLog vs. CDH Question},
year={2021},
volume={E104-A},
number={1},
pages={20-24},
abstract={Knowledge-of-exponent assumptions (KEAs) are a somewhat controversial but nevertheless commonly used type of cryptographic assumptions. While traditional cryptographic assumptions simply assert that certain tasks (like factoring integers or computing discrete logarithms) cannot be performed efficiently, KEAs assert that certain tasks can be performed efficiently, but only in certain ways. The controversy surrounding those assumptions is due to their non-falsifiability, which is due to the way this idea is formalised, and to the general idea that these assumptions are “strong”. Nevertheless, their relationship to existing assumptions has not received much attention thus far. In this paper, we show that the first KEA (KEA1), introduced by Damgård in 1991, implies that computing discrete logarithms is equivalent to solving the computational Diffie-Hellman (CDH) problem. Since showing this equivalence in the standard setting (i.e., without the assumption that KEA1 holds) is a longstanding open question, this indicates that KEA1 (and KEAs in general) are indeed quite strong assumptions.},
keywords={},
doi={10.1587/transfun.2020CIP0002},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - On a Relation between Knowledge-of-Exponent Assumptions and the DLog vs. CDH Question
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 20
EP - 24
AU - Firas KRAIEM
AU - Shuji ISOBE
AU - Eisuke KOIZUMI
AU - Hiroki SHIZUYA
PY - 2021
DO - 10.1587/transfun.2020CIP0002
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E104-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2021
AB - Knowledge-of-exponent assumptions (KEAs) are a somewhat controversial but nevertheless commonly used type of cryptographic assumptions. While traditional cryptographic assumptions simply assert that certain tasks (like factoring integers or computing discrete logarithms) cannot be performed efficiently, KEAs assert that certain tasks can be performed efficiently, but only in certain ways. The controversy surrounding those assumptions is due to their non-falsifiability, which is due to the way this idea is formalised, and to the general idea that these assumptions are “strong”. Nevertheless, their relationship to existing assumptions has not received much attention thus far. In this paper, we show that the first KEA (KEA1), introduced by Damgård in 1991, implies that computing discrete logarithms is equivalent to solving the computational Diffie-Hellman (CDH) problem. Since showing this equivalence in the standard setting (i.e., without the assumption that KEA1 holds) is a longstanding open question, this indicates that KEA1 (and KEAs in general) are indeed quite strong assumptions.
ER -