
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.
lower bounds, generic attacks, Cryptography, cryptographic primitives, computation graph
lower bounds, generic attacks, Cryptography, cryptographic primitives, computation graph
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
