International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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
Download:
DOI: 10.46586/tosc.v2022.i1.110-137
URL: https://tosc.iacr.org/index.php/ToSC/article/view/9530
Search ePrint
Search Google
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.
Video from TOSC 2022
BibTeX
@article{tosc-2022-31975,
  title={Influence of the Linear Layer on the Algebraic Degree in SP-Networks},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2022, Issue 1},
  pages={110-137},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/9530},
  doi={10.46586/tosc.v2022.i1.110-137},
  author={Carlos Cid and Lorenzo Grassi and Aldo Gunsing and Reinhard Lüftenegger and Christian Rechberger and Markus Schofnegger},
  year=2022
}