Paper 2020/536

Influence of the Linear Layer on the Algebraic Degree in SP-Networks

Carlos Cid, Lorenzo Grassi, Aldo Gunsing, Reinhard Lüftenegger, Christian Rechberger, and Markus Schofnegger

Abstract

We consider SPN schemes, i.e., schemes whose non-linear layer is defined as the parallel application of $t\ge 1$ independent S-Boxes over $\mathbb{F}_{2^n}$ and whose linear layer is defined by the multiplication with a $(n\cdot t)\times(n\cdot t)$ matrix over $\mathbb{F}_2$. Even if the algebraic representation of a scheme depends on all its components, upper bounds on the growth of the algebraic degree in the literature usually only consider the details of the non-linear layer. Hence a natural question arises: (how) do the details of the linear layer influence the growth of the algebraic degree? We show that the linear layer plays a crucial role in the growth of the algebraic degree and present a new upper bound on the algebraic degree in SP-networks. As main results, we prove that in the case of low-degree round functions with large S-Boxes: $\textit{(a)}$ an initial exponential growth of the algebraic degree can be followed by a linear growth until the maximum algebraic degree is reached; $\textit{(b)}$ the rate of the linear growth is proportional to the degree of the linear layer over $\mathbb{F}_{2^n}^t$. Besides providing a theoretical insight, our analysis is particularly relevant for assessing the security of cryptographic permutations designed to be competitive in applications like MPC, FHE, SNARKs, and STARKs, including permutations based on the Hades design strategy. We have verified our findings on small-scale instances and we have compared them against the currently best results in the literature, showing a substantial improvement of upper bounds on the algebraic degree in case of low-degree round functions with large S-Boxes.

Note: This is a revised and updated version, now incorporating the degree of the linear layer into the bound on the algebraic degree.