The black-box model for cryptographic primitives
To investigate security properties of a cryptographic primitive it is useful to grasp the idea a class of attacks is based on. Having a model that describes essential features of the primitive without unnecessary details one can concentrate on what makes the primitive resistant to what class of attacks. A cryptographic primitive can be modelled by a computation graph in which the vertices are computation boxes. Given such a model one can say that some attacks are based on utilizing certain properties of the boxes while others may make use of the structure of the computation graph. The article is about investigating security properties provided by a computation graph, i.e. regardless of the inner structure of the boxes. This allows one to study a family of generic attacks which generalize exhaustive search and the birthday paradox. The authors first introduce the black-box model, i.e. the model in which the cryptographic primitives are given by a computation graph, where the computation boxes associated with the vertices of the graph act as random oracles (black-boxes). After defining complexity measure for the model lower bound for a family of generic attacks is established. Then the approach is applied to compression functions whose computation graph is represented by the FFT interconnection network (the computation graph of the Fast Fourier Transform). Upper and lower bounds for the complexity of inverting the function computed by this network are proved. Finally, the authors briefly outline possible extensions to their approach.
scientific article; zbMATH DE number 1185256