On a relation between knowledge-of-exponent assumptions and the DLog vs. CDH question

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)20-24
Number of pages5
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number1
Publication statusPublished - 2021 Jan 1


  • Cryptographic assumptions
  • Diffie-Hellman
  • Discrete logarithm
  • Knowledge-of-exponent


Dive into the research topics of 'On a relation between knowledge-of-exponent assumptions and the DLog vs. CDH question'. Together they form a unique fingerprint.

Cite this