Welcome to the resource topic for 2020/536
Title:
Influence of the Linear Layer on the Algebraic Degree in SP-Networks
Authors: Carlos Cid, Lorenzo Grassi, Aldo Gunsing, Reinhard Lüftenegger, Christian Rechberger, 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.
ePrint: https://eprint.iacr.org/2020/536
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .