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; Alexander W.  Dent

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 Model Straight-Line Programs Hardness Conditions Lower 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: 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},
      url = {https://eprint.iacr.org/2007/360}
}