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 $A$ of $F_{2^n}$ 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 Sboxes). We show that, for every $k$ not coprime with $n$, the multiplicative inverse function sums to zero over at least one $k$dimensional $F_2$subspace of $F_{2^n}$. 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 $k$dimensional $F_2$subspace of $F_{2^n}$ happens for $k$ if and only if it happens for $nk$. 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 codimension at most 3). We leave the other cases open.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published elsewhere. Minor revision. IEEE Transactions on Information Theory
 Keywords
 SboxAPN
 Contact author(s)
 Claude carlet @ gmail com
 History
 20210512: revised
 20201221: received
 See all versions
 Short URL
 https://ia.cr/2020/1587
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/1587, author = {Claude Carlet}, title = {On the properties of the Boolean functions associated to the differential spectrum of general {APN} functions and their consequences}, howpublished = {Cryptology ePrint Archive, Paper 2020/1587}, year = {2020}, note = {\url{https://eprint.iacr.org/2020/1587}}, url = {https://eprint.iacr.org/2020/1587} }