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 .