Paper 2020/536

Higher-Order Differentials of Strong-Aligned 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 cryptanalysis and its variants are among the most powerful methods for analyzing iterated cryptographic permutations and hash functions with low algebraic degree over binary extension fields. Predicting the evolution of the algebraic degree (as a function of the number of iterations) is the main obstacle for applying these methods. In this paper, we present a new upper bound on the growth of the algebraic degree in strong-aligned SP-Networks with low-degree and large S-Boxes. Our findings generalize a recent result presented at Asiacrypt 2020, which applies to permutations based on an iterated Even-Mansour construction with low-degree round functions. As a main result, we prove that an initial exponential growth of the algebraic degree is followed by a linear growth until the maximum algebraic degree is reached. 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 current best results, showing a substantial improvement for strong-aligned SPN schemes with low-degree and large S-Boxes.

Note: This is a major revision. The main differences with respect to the previous version: - the bound log_delta(t) + log_d(2^n - 1) on the minimum number of rounds for security against higher-order differential distinguishers is replaced by the new bound log_d (t) + log_d(2^n - 1); - we prove a new bound on the growth of the algebraic degree in SPN schemes with a novel proof technique; - new practical results regarding the growth of the algerbraic degree and comparisons with our bound are added; - the organization of the paper has been adapted to accomodate above changes.