Cryptology ePrint Archive: Report 2007/360

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

Andy Rupp and Gregor Leander and Endre Bangerter and 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.

Category / Keywords: Generic Group Model, Straight-Line Programs, Hardness Conditions, Lower Bounds.

Date: received 11 Sep 2007, last revised 8 Aug 2008

Contact author: gregor leander at rub de

Available format(s): PDF | BibTeX Citation

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

Version: 20080808:171038 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]