Paper 2020/536

Higher-Order Differentials of Ciphers with Low-Degree S-Boxes

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

Abstract

Higher-order differential attacks are among the most powerful attacks against low-degree ciphers and hash functions. Predicting the evolution of the algebraic degree of the cipher (as a function of the number of rounds) is the main obstacle in assessing the feasibility of these attacks. For an SPN cipher over a finite field $\mathbb F$ of characteristic 2 with round function of algebraic degree $\delta$, it is a common belief that the degree of the cipher grows almost exponentially with $\delta$. However, for an iterated Even--Mansour cipher whose round function can be described as an invertible low-degree polynomial over $\mathbb F_{2^n}$ it has recently been shown that the algebraic degree grows linearly with the number of rounds, and not exponentially. In this paper we generalise these results for SPN ciphers, showing that the growth of the algebraic degree is often linear for SPN ciphers with low-degree S-Boxes as well. We prove that the initial exponential growth of the degree turns into a linear growth after a certain number of rounds. Our analysis includes iterated Even--Mansour and MiMC-like ciphers as a special case, but most notably it also applies to SPN ciphers designed to be competitive for recent applications like MPC, FHE, SNARKs, and STARKs (e.g., HadesMiMC). Our findings have been practically verified on small-scale ciphers.