International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Sufficient Conditions for Computational Intractability Regarding Generic Algorithms

Andy Rupp
Gregor Leander
Endre Bangerter
Ahmad-Reza Sadeghi
Alexander W. Dent
Search ePrint
Search Google
Abstract: The generic group model is a valuable methodology for analyzing the computational hardness of the number-theoretic problems used in cryptography. Although generic hardness proofs exhibit many similarities, still the computational intractability of every newly introduced problem needs to be proven from scratch, a task that can easily become complicated and cumbersome when done rigorously. In this paper we make the first steps towards overcoming this problem by identifying verifiable criteria which if met by a cryptographic problem guarantee its hardness with respect to generic algorithms. As useful means for formalization of definitions and proofs we relate the concepts of generic algorithms and straight-line programs that have only been used independently in cryptography so far. The class of problems we cover includes a significant number of the cryptographic problems currently known, and is general enough to also include many future problems. Moreover, we strengthen the conventional generic model by incorporating a broader class of possible oracles (operations) since the underlying algebraic groups may possibly be related through mappings such as isomorphisms, homomorphisms or multilinear maps. Our approach could serve as an appropriate basis for tool-aided hardness verification in the generic model.
  title={Sufficient Conditions for Computational Intractability Regarding Generic Algorithms},
  booktitle={IACR Eprint archive},
  keywords={foundations / Generic Group Model, Straight-Line Programs, Hardness Conditions},
  note={ 13767 received 11 Sep 2007},
  author={Andy Rupp and Gregor Leander and Endre Bangerter and Ahmad-Reza Sadeghi and Alexander W. Dent},