Paper 2020/1587

On the properties of the Boolean functions associated to the differential spectrum of general APN functions and their consequences

Claude Carlet

Abstract

The notion of almost perfect nonlinear (APN) function is important, mathematically and cryptographically. Much still needs to be understood on the structure and the properties of APN functions. For instance, finding an APN permutation in an even number of variables larger than 6 would be an important theoretical and practical advance. A way to progress on a notion is to introduce and study generalizations making sense from both theoretical and practical points of view. The introduction and study of differentially uniform functions has brought more knowledge on APN functions themselves. Their notion is directly related to one of the classical characterizations of APN functions and presents an important practical interest for cryptography. In this paper we introduce and study two other generalizations of almost perfect nonlinearity, that are also related to classical characterizations of APN functions. The resulting notions are significantly different (and behave differently) from differential uniformity; they also behave differently from each other, despite the apparent similarity between their definitions. We study their satisfiability, their invariance under classical equivalence relations, their monotonicity and we characterize one of them by the Walsh transform; our results give more insight on the almost perfect nonlinearity notion itself. We study the behavior of the multiplicative inverse function (which plays an important role in cryptography and in the study of finite fields) with respect to these two notions. To this aim, we find a rather simple expression of the sum of the values of this function over any affine subspace $$ of $$ not containing 0. The expression shows that such sum never vanishes (which is a remarkable property of the inverse function, which may represent a tool for attacking block ciphers using it in its S-boxes). We show that, for every $$ not co-prime with $$, the multiplicative inverse function sums to zero over at least one $$-dimensional $$-subspace of $$. We study the behavior of the inverse function over direct sums of vector spaces and we deduce that the property of the inverse function to sum to zero over at least one $$-dimensional $$-subspace of $$ happens for $$ if and only if it happens for $$. We derive several results on the sums of values of the inverse function over vector spaces and we address the cases of dimension at most 3 (equivalently, of co-dimension at most 3). We leave the other cases open.