Paper 2024/841

Two generalizations of almost perfect nonlinearity

Abstract

Almost perfect nonlinear (in brief, APN) functions are (so-called vectorial) functions $F: F_2^n\to F_2^n$ playing roles in several domains of information protection, at the intersection of computer science and mathematics. Their definition comes from cryptography and is also related to coding theory. The cryptographic motivation for studying APN functions is that, when they are used as substitution boxes (S-boxes), ensuring nonlinearity in block ciphers, they contribute optimally to the resistance against differential attacks. Their study has been very active since the 90's, and has posed interesting and difficult mathematical questions, that are still unanswered. \\Since the introduction of differential attacks, more recent types of cryptanalyses have been designed, such as integral attacks. No notion about S-boxes has been identified which would play a similar role with respect to integral attacks. In this paper, we introduce and study two generalizations of almost perfect nonlinearity, that directly extend classical characterizations of APN functions, and are also related to the integral attack. The two resulting notions are significantly different (and behave differently) from differential uniformity, which is a well-known generalization of APNness; they also behave differently from each other, despite the apparent similarity between their definitions. We study the different ways to define them, and on the example of Kasami functions, how difficult they are to achieve. We prove their satisfiability, their monotonicity, their invariance under classical equivalence relations and we characterize them by the Walsh transform. We begin a study of the multiplicative inverse function (used as a substitution box in the Advanced Encryption Standard and other block ciphers) from the viewpoint of these two notions. In particular, we find a simple expression of the sum of the values taken by this function over affine subspaces of $\mathbb F_{2^n}$ that are not vector subspaces. This formula shows that, in such case, the sum never vanishes (which is a remarkable property of the inverse function).