Paper 2002/126

Assumptions Related to Discrete Logarithms: Why Subtleties Make a Real Difference

Ahmad-Reza Sadeghi and Michael Steiner


The security of many cryptographic constructions relies on assumptions related to Discrete Logarithms (DL), e.g., the Diffie-Hellman, Square Exponent, Inverse Exponent or Representation Problem assumptions. In the concrete formalizations of these assumptions one has some degrees of freedom offered by parameters such as computational model, problem type (computational, decisional) or success probability of adversary. However, these parameters and their impact are often not properly considered or are simply overlooked in the existing literature. In this paper we identify parameters relevant to cryptographic applications and describe a formal framework for defining DL-related assumptions. This enables us to precisely and systematically classify these assumptions. In particular, we identify a parameter, termed granularity, which describes the underlying probability space in an assumption. Varying granularity we discover the following surprising result: We prove that two DL-related assumptions can be reduced to each other for medium granularity but we also show that they are provably not reducible with generic algorithms for high granularity. Further we show that reductions for medium granularity can achieve much better concrete security than equivalent high-granularity reductions.

Available format(s)
Publication info
Published elsewhere. Revised and extended version of a EuroCrypt'2001 paper with the same title
Contact author(s)
steiner @ acm org
2002-08-26: revised
2002-08-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ahmad-Reza Sadeghi and Michael Steiner},
      title = {Assumptions Related to Discrete Logarithms: Why Subtleties Make a Real Difference},
      howpublished = {Cryptology ePrint Archive, Paper 2002/126},
      year = {2002},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.