Graphs connected with block ciphers
Otokar Gro, Pavol Zajac · 2005
A block cipher consists of round transformations. Each round transformation contains a mixing layer to create diffusion, that is, to have each output bit dependent on all input bits. Such a transformation can also be described by means of graph theory language. Here we generalize a partial result from our two previous papers. The main result of this paper claims that for an oriented graph G with n vertices, satisfying for all u;v 2 V (G) special conditions, there exists n0 such that for all n > n0 the number of arcs e(G) ‚ (n i 1)(k + 1). We also discuss a relation to the problem of an ideal round transformation.