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

##### 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.

Available format(s)
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
See all versions
Short URL
https://ia.cr/2002/126

CC BY

BibTeX

@misc{cryptoeprint:2002/126,