Welcome to the resource topic for
**2002/126**

**Title:**

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

**Authors:**
Ahmad-Reza Sadeghi, 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.

**ePrint:**
https://eprint.iacr.org/2002/126

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .