Paper 2007/360

Sufficient Conditions for Intractability over Black-Box Groups: Generic Lower Bounds for Generalized DL and DH Problems

Andy Rupp, Gregor Leander, Endre Bangerter, Ahmad-Reza Sadeghi, and Alexander W. Dent

Abstract

The generic (aka. black-box) group model is a valuable methodology for analyzing the computational hardness of number-theoretic problems used in cryptography. Since the properties ensuring generic hardness have not been well-studied and formalized yet, for each newly proposed problem an entire hardness proof has to be done from scratch. In this work we identify criteria that guarantee the hardness of generalized DL and DH problems in an extended generic group model where algorithms are allowed to perform any operation representable by a polynomial function. Assuming our conditions are satisfied, we are able to provide negligible upper bounds on the success probability of such algorithms. As useful means for the formalization of definitions and conditions we explicitly relate the concepts of generic algorithms and straight-line programs that have only been used independently in cryptography so far.

Note: Completely revised, new formalization, concrete bounds given.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
Generic Group ModelStraight-Line ProgramsHardness ConditionsLower Bounds.
Contact author(s)
gregor leander @ rub de
History
2008-08-08: revised
2007-09-13: received
See all versions
Short URL
https://ia.cr/2007/360
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/360,
      author = {Andy Rupp and Gregor Leander and Endre Bangerter and Ahmad-Reza Sadeghi and Alexander W.  Dent},
      title = {Sufficient Conditions for Intractability over Black-Box Groups: Generic Lower Bounds for Generalized DL and DH Problems},
      howpublished = {Cryptology ePrint Archive, Paper 2007/360},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/360}},
      url = {https://eprint.iacr.org/2007/360}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.