### 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.

Available format(s)
Category
Secret-key cryptography
Publication info
Keywords
Higher-Order Differential CryptanalysisSPNAlgebraic DegreeLinear Layer
Contact author(s)
reinhard lueftenegger @ iaik tugraz at
History
2022-02-28: last of 7 revisions
See all versions
Short URL
https://ia.cr/2020/536

CC BY

BibTeX

@misc{cryptoeprint:2020/536,
author = {Carlos Cid and Lorenzo Grassi and Aldo Gunsing and Reinhard Lüftenegger and Christian Rechberger and Markus Schofnegger},
title = {Influence of the Linear Layer on the Algebraic Degree in SP-Networks},
howpublished = {Cryptology ePrint Archive, Paper 2020/536},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/536}},
url = {https://eprint.iacr.org/2020/536}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.