International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Two Generalizations of Almost Perfect Nonlinearity

Authors:
Claude Carlet
Download:
DOI: 10.1007/s00145-025-09538-5
Search ePrint
Search Google
Abstract: Abstract Almost perfect nonlinear (in brief, APN) functions are vectorial functions $$F:{\mathbb {F}}_2^n\rightarrow {\mathbb {F}}_2^n$$ F : F 2 n → 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. When they are used as substitution boxes (S-boxes, which are the only nonlinear components in block ciphers), APN functions contribute optimally to the resistance against differential attacks. This makes of course a strong cryptographic motivation for their study, which has been very active since the 90’s, and has posed interesting and difficult mathematical questions, some of which 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 study two generalizations of APNness that are natural from a mathematical point of view, since they directly extend classical characterizations of APN functions. We call these two notions strong non-normality and sum-freedom. The former existed already for Boolean functions (it had been introduced by Dobbertin), and the latter is new. We study how these two notions are related to cryptanalyses (the relation is weaker for strong non-normality). The two notions behave differently from each other, while they have similar definitions. They behave differently from differential uniformity, which is a well-known generalization of APNness. We study the different ways to define them. We prove their satisfiability, their monotonicity, and their invariance under classical equivalence relations, and we characterize them by the Walsh transform. We finally 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}$$ F 2 n that are not vector subspaces. This formula shows that the sum never vanishes on such affine spaces. We also give a formula for the case of a vector space defined by one of its bases.
BibTeX
@article{jofc-2024-35418,
  title={Two Generalizations of Almost Perfect Nonlinearity},
  journal={Journal of Cryptology},
  publisher={Springer},
  volume={38},
  pages={20},
  doi={10.1007/s00145-025-09538-5},
  author={Claude Carlet},
  year=2024
}