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, the 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.
Chapter PDF
Similar content being viewed by others
Keywords
References
Kevin S. McCurley. The discrete logarithm problem. In Carl Pomerance, editor, Cryptology and Computational Number Theory, volume 42 of Proceedings of Symposia in Applied Mathematics, pages 49–74, Providence, 1990. American Mathematical Society.
Whitfield Diffie and Martin Hellman. New directions in cryptography. IEEE Transactions on Information Theory, IT-22(6):644–654, November 1976.
Dan Boneh. The Decision Diffie-Hellman problem. In Third Algorithmic Number Theory Symposium, number 1423 in Lecture Notes in Computer Science, pages 48–63. Springer-Verlag, Berlin Germany, 1998.
Ronald Cramer and Victor Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In Hugo Krawczyk, editor, Advances in Cryptology-CRYPTO '98, number 1462 in Lecture Notes in Computer Science, pages 13–25. International Association for Cryptologic Research, Springer-Verlag, Berlin Germany, August 1998.
Moni Naor and Omer Reingold. Number-theoretic constructions of efficient pseudo-random functions. In 38th Symposium on Foundations of Computer Science (FOCS), pages 458–467. IEEE Computer Society Press, 1997.
Michael Steiner, Gene Tsudik, and Michael Waidner. Key agreement in dynamic peer groups. IEEE Transactions on Parallel and Distributed Systems, 11(8):769–780, August 2000.
Yair Frankel, Yiannis Tsiounis, and Moti Yung. “indirect discourse proofs”: Achieving fair off-line cash (FOLC). In K. Kim and T. Matsumoto, editors, Advances in Cryptology-ASIACRYPT '96, number 1163 in Lecture Notes in Computer Science, pages 286–300. Springer-Verlag, Berlin Germany, 1996.
Helena Handschuh, Yiannis Tsiounis, and Moti Yung. Decision oracles are equivalent to matching oracles. In International Workshop on Practice and Theory in Public Key Cryptography '99 (PKC '99), number 1560 in Lecture Notes in Computer Science, Kamakura, Japan, March 1999. Springer-Verlag, Berlin Germany.
Stefan Wolf. Information-theoretically and Computionally Secure Key Agreement in Cryptography. PhD thesis, ETH Zürich, 1999.
Ueli M. Maurer and Stefan Wolf. Diffie-Hellman oracles. In Koblitz [32], pages 268–282.
Mike Burmester, Yvo Desmedt, and Jennifer Seberry. Equitable key escrow with limited time span (or, how to enforce time expiration cryptographically). In K. Ohta and D. Pei, editors, Advances in Cryptology-ASIACRYPT '98, number 1514 in Lecture Notes in Computer Science, pages 380–391. Springer-Verlag, Berlin Germany, 1998.
Birgit Pfitzmann and Ahmad-Reza Sadeghi. Anonymous fingerprinting with direct non-repudiation. In Okamoto [33], pages 401–414.
Jan Camenisch, Ueli Maurer, and Markus Stadler. Digital payment systems with passive anonymity-revoking trustees. In E. Bertino, H. Kurth, G. Martella, and E. Montolivo, editors, Proceedings of the Fourth European Symposium on Research in Computer Security (ESORICS), number 1146 in Lecture Notes in Computer Science, pages 33–43, Rome, Italy, September 1996. Springer-Verlag, Berlin Germany.
George Davida, Yair Frankel, Yiannis Tsiounis, and Moti Yung. Anonymity control in e-cash systems. In Proceedings of the First Conference on Financial Cryptography (FC '97), number 1318 in Lecture Notes in Computer Science, pages 1–16, Anguilla, BritishWest Indies, February 1997. International Financial Cryptography Association (IFCA), Springer-Verlag, Berlin Germany.
Victor Shoup. Lower bounds for discrete logarithms and related problems. In Walter Fumy, editor, Advances in Cryptology-EUROCRYPT '97, number 1233 in Lecture Notes in Computer Science, pages 256–266. International Association for Cryptologic Research, Springer-Verlag, Berlin Germany, 1997.
Ueli M. Maurer and Stefan Wolf. Diffie-Hellman, Decision Diffie-Hellman, and discrete logarithms. In IEEE Symposium on Information Theory, page 327, Cambridge, USA, August 1998.
Ueli M. Maurer and Stefan Wolf. Lower bounds on generic algorithms in groups. In Kaisa Nyberg, editor, Advances in Cryptology-EUROCRYPT '98, number 1403 in Lecture Notes in Computer Science, pages 72–84. International Association for Cryptologic Research, Springer-Verlag, Berlin Germany, 1998.
Eli Biham, Dan Boneh, and Omer Reingold. Breaking generalized Diffie-Hellman modulo a composite is no easier than factoring. Information Processing Letters, 70:83–87, 1999. Also appeares in Theory of Cryptography Library, Record 97-14, 1997.
Daniel M. Gordon. Designing and detecting trapdoors for discrete log cryptosystems. In E.F. Brickell, editor, Advances in Cryptology-CRYPTO '92, volume 740 of Lecture Notes in Computer Science, pages 66–75. International Association for Cryptologic Research, Springer-Verlag, Berlin Germany, 1993.
National Institute of Standards and Technology (NIST). The digital signature standard (DSS). FIPS PUB 186-2, January 2000.
Ahmad-Reza Sadeghi and Michael Steiner. Assumptions related to discrete logarithms: Why subtleties make a real difference. Full version of paper, available from http://www.semper.org/sirene/lit/abstrA1.html.
Dan Boneh and Richard J. Lipton. Algorithms for black box fields and their application to cryptography. In Koblitz [32], pages 283–297.
V. I. Nechaev. Complexity of a determinate algorithm for the discrete logarithm. Mathematical Notes, 55(2):165–172, 1994. Translated from Matematicheskie Zametki, 55(2):91–101, 1994.
Christian Cachin, Klaus Kursawe, and Victor Shoup. Random oracles in Constantinople: practical asynchronous Byzantine agreement using cryptography. In Proceedings of the 19th Annual ACM Symposium on Principles of Distributed Computing, Portland, Oregon, July 2000. ACM. Full version appeared as Cryptology ePrint Archive Report 2000/034 (2000/7/7).
J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27(4):701–717, 1980.
S.C. Pohlig and M. E. Hellman. An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Transactions on Information Theory, 24:106–110, 1978.
J. M. Pollard. Monte carlo methods for index computation mod p. Mathematics of Computation, 32:918–924, 1978.
Marc Fischlin. A note on security proofs in the generic model. In Okamoto [33], pages 458–469.
Victor Shoup. On formal models for secure key exchange. Research Report RZ 3120 (#93166), IBM Research, April 1999. A revised version 4, dated November 15, 1999, is available from http://www.shoup.net/papers/.
Dan Boneh. Personal Communication, October 2000.
Miklóos Ajtai and Cynthia Dwork. A public-key cryptosystem with worstcase/average-case equivalence. In 29th Annual Symposium on Theory Of Computing (STOC), pages 284–293, El Paso, TX, USA, May 1997. ACM Press.
Neal Koblitz, editor. Advances in Cryptology-CRYPTO '96, number 1109 in Lecture Notes in Computer Science. International Association for Cryptologic Research, Springer-Verlag, Berlin Germany, 1996.
T. Okamoto, editor. Advances in Cryptology-ASIACRYPT '2000, number 1976 in Lecture Notes in Computer Science, Kyoto, Japan, 2000. International Association for Cryptologic Research, Springer-Verlag, Berlin Germany.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sadeghi, AR., Steiner, M. (2001). Assumptions Related to Discrete Logarithms: Why Subtleties Make a Real Difference. In: Pfitzmann, B. (eds) Advances in Cryptology — EUROCRYPT 2001. EUROCRYPT 2001. Lecture Notes in Computer Science, vol 2045. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44987-6_16
Download citation
DOI: https://doi.org/10.1007/3-540-44987-6_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42070-5
Online ISBN: 978-3-540-44987-4
eBook Packages: Springer Book Archive