Squeezing a vectorial nonlinear binary transformation between two perpendicular matrices.

We propose a new primitive that could serve as a component in the design of block ciphers defined over a vector space of characteristic two. The primitive consists of squeezing a vectorial non-linear boolean function between two linear transformations. More precisely, the primitive transformation consists of a (linear compression) $\to$ (keyed nonlinear transformation) $\to$ (linear decompression) feed back with its input and then linearly transformed. We impose that the compression and decompression be perpendicular matrices for the system to be invertible even if the nonlinear part is not invertible. Our scheme has the \emph{practical} advantage that many interesting properties of an entire round reduce only to those of the nonlinear transformation. As a matter of fact, we prove a lower bound on the minimal number of iterations, assuming independent keys uniformly distributed among iterations, to avoid paths both in the space of first order differences (differential cryptanalysis) as well as in the space of linear first order correlations (linear cryptanalysis) up to a desired threshold. We neither focus in this paper on the key scheduling algorithm nor on the nonlinear part and solely analyze how the linear components must be set up to be resilient against the aforementioned cryptanalytic attacks. Examples of our scheme are round functions of well-known block ciphers such as DES or IDEA-NXT based on the Lai-Massey scheme, families of block ciphers such as the original Feistel networks and generalized Feistel networks, as long as the underlying field has characteristic two and that no modular arithmetic is involved.