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

Authors

  • Carlos Cid Information Security Group, Royal Holloway University of London, Egham, United Kingdom; Simula UiB, Bergen, Norway
  • Lorenzo Grassi Digital Security Group, Radboud University, Nijmegen, The Netherlands
  • Aldo Gunsing Digital Security Group, Radboud University, Nijmegen, The Netherlands
  • Reinhard Lüftenegger Institute of Applied Information Processing and Communications, Graz University of Technology, Graz, Austria
  • Christian Rechberger Institute of Applied Information Processing and Communications, Graz University of Technology, Graz, Austria
  • Markus Schofnegger Institute of Applied Information Processing and Communications, Graz University of Technology, Graz, Austria

DOI:

https://doi.org/10.46586/tosc.v2022.i1.110-137

Keywords:

Higher-Order Differential Cryptanalysis, Algebraic Degree, SPN, Linear Layer

Abstract

We consider SPN schemes, i.e., schemes whose non-linear layer is defined as the parallel application of t ≥ 1 independent S-Boxes over F2n and whose linear layer is defined by the multiplication with a (n · t) × (n · t) matrix over F2. 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: (a) an initial exponential growth of the algebraic degree can be followed by a linear growth until the maximum algebraic degree is reached; (b) the rate of the linear growth is proportional to the degree of the linear layer over Ft2n. Besides providing a theoretical insight, our analysis is particularly relevant for assessing the security of 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.

Downloads

Published

2022-03-11

Issue

Section

Articles

How to Cite

Influence of the Linear Layer on the Algebraic Degree in SP-Networks. (2022). IACR Transactions on Symmetric Cryptology, 2022(1), 110-137. https://doi.org/10.46586/tosc.v2022.i1.110-137