The Black-Box Model for Cryptographic Primitives

We introduce the black-box model for cryptographic primitives. In this model cryptographic primitives are given by a computation graph, where the computation boxes sitting on the vertices of the graph act as random oracles. We formalize and study a family of generic attacks which generalize exhaustive search and the birthday paradox. We establish complexity lower bounds for these attacks and we apply it to compression functions based on the FFT network. Received 25 October 1995 and revised 15 September 1997