Cryptology ePrint Archive: Report 2020/536

Higher-Order Differentials of Word-Oriented SPN Schemes 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 iterated ciphers and hash functions over binary extension fields. Predicting the evolution of the algebraic degree (as a function of the number of iterations) is the main obstacle in assessing the feasibility of these attacks. For ciphers with round functions 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 it has recently been shown that the algebraic degree grows linearly with the number of rounds, and not exponentially.

In this paper we generalize these results to SPN schemes and show that the growth of the algebraic degree is often linear for schemes with low-degree S-Boxes as well. Most notably, our analysis 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.

Category / Keywords: secret-key cryptography / Higher-Order Differential Cryptanalysis, SPN, Algebraic Degree

Date: received 7 May 2020, last revised 22 Jun 2020

Contact author: reinhard lueftenegger at iaik tugraz at

Available format(s): PDF | BibTeX Citation

Version: 20200622:124855 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]