Paper 2002/126

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

Ahmad-Reza Sadeghi and Michael Steiner

Abstract

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.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Revised and extended version of a EuroCrypt'2001 paper with the same title
Contact author(s)
steiner @ acm org
History
2002-08-26: revised
2002-08-26: received
See all versions
Short URL
https://ia.cr/2002/126
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2002/126,
      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{https://eprint.iacr.org/2002/126}},
      url = {https://eprint.iacr.org/2002/126}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.