The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E104-A No.1 pp.20-24

- Publication Date
- 2021/01/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.2020CIP0002

- Type of Manuscript
- Special Section PAPER (Special Section on Cryptography and Information Security)

- Category

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 -