CryptoDB
Assumptions Related to Discrete Logarithms: Why Subtleties Make a Real Difference
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-2002-11649,
title={Assumptions Related to Discrete Logarithms: Why Subtleties Make a Real Difference},
booktitle={IACR Eprint archive},
keywords={foundations /},
url={http://eprint.iacr.org/2002/126},
note={Revised and extended version of a EuroCrypt'2001 paper with the same title steiner@acm.org 11925 received 26 Aug 2002, last revised 26 Aug 2002},
author={Ahmad-Reza Sadeghi and Michael Steiner},
year=2002
}