The search functionality is under construction.
The search functionality is under construction.

On a Relation between Knowledge-of-Exponent Assumptions and the DLog vs. CDH Question

Firas KRAIEM, Shuji ISOBE, Eisuke KOIZUMI, Hiroki SHIZUYA

  • Full Text Views

    0

  • Cite this

Summary :

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

Authors

Firas KRAIEM
  Tohoku University
Shuji ISOBE
  Tohoku University
Eisuke KOIZUMI
  Tohoku University
Hiroki SHIZUYA
  Tohoku University

Keyword