Research progress of almost perfect nonlinear functions

As the core nonlinear component of block ciphers, functions over finite fields rely on their low differential uniformity to resist differential cryptanalysis. Almost Perfect Nonlinear (APN) functions, renowned for their optimal differential properties, are a core research focus in this field.

Research progress on APN functions primarily focused on five aspects: the generation of examples; the construction of infinite families; the equivalence classification; the cryptographic properties including the permutation properties, algebraic degree and nonlinearity; and the applications in coding theory and combinatorial design.

First, general methods for generating APN function examples were proposed by researchers. These included primary construction methods such as "Matrix Approach", "Ortho-derivative Method", "Antiderivative Method", "Recursive Tree Search", as well as secondary construction methods like "Switching Method", "Adding Terms", "Isotopic Shift" and "Trims and Extensions". Notably, by using two secondary construction techniques that added a coordinate function and extended the input space one dimension at a time, researchers obtained 3775599 CCZ-inequivalent quadratic APN function examples over $F_{2^8}$, which was the first time that the number of APN functions over $F_{2^8}$ reached the million scale.

Second, using various construction techniques and methods, scholars have constructed infinite families of APN functions. Initially, 6 infinite families of APN monomials were constructed. Later, methods like "Linear Permutation Replacement Method", "Adding Terms", "Isotopic Shift", "Bivariate Construction Method", "Biprojective Construction Method" and "Triprojective Construction Method" were proposed to construct infinite families of APN polynomials. Among these, the "Adding Terms" method was particularly effective. In 2009, Budaghyan et al. derived three new infinite families of APN polynomials by adding three specific Boolean functions to the Gold function. In 2009 and 2011, Bracken et al. applied the method "Adding Terms" to an APN binomial and successively constructed two new infinite families of APN trinomials and quadrinomials. "Bivariate Construction Method" was also a useful technique. Around 2011, Zhou et al. and Carlet respectively employed vectorial Bent functions to construct infinite families of APN functions over $F_{2^m}^2$ with the bivariate form $(xy,G(x,y))$. Subsequently, several scholars have obtained new infinite families of APN polynomials by choosing distinct G. To date, researchers have constructed a total of 20 infinite families of quadratic APN polynomials through various methods.

Third, computational searches in low dimensions have advanced the classification of APN function examples via CCZ-equivalence. A complete classification of APN functions has been achieved for $n\le 5$. Classification of quadratic APN functions has been achieved for $n\le 7$. Classification of quadratic APN functions with coefficients in F₂ has been achieved for $n\le 9$. A standard way of showing equivalence between functions was by using a computer to calculate and compare some CCZ-invariants in small dimensions. Researchers proposed CCZ-invariants such as $\Gamma \text{-rank}$, $\Delta \text{-rank}$, ${\Pi }_F$, ${\mathrm{\Sigma }}_{4,C}$, and differential or extended Walsh spectrum of the corresponding ortho-derivative function. Among these, $\sum _{4,C}$ has successfully distinguished multiple known APN functions, including $x^3$ and $x^9$ over $F_{2^7}$, $x^3$ and $x^{33}$ over $F_{2^9}$, (where previous invariants failed). Apart from that, there were also some theoretical analyses of CCZ-equivalence between APN functions. The CCZ-equivalence between any two APN power functions has been completely determined, and some CCZ-inequivalence results between APN polynomials and monomials were known. By exploiting the existence of some cyclic subgroup in the automorphism groups of the functions, theoretical results on CCZ-equivalence for APN polynomials, especially biprojective and triprojective functions, were established.

Fourth, research on the cryptographic properties of APN functions advanced considerably. Notably, all 6 known infinite families of APN monomials in odd dimensions were permutations. Additionally, two infinite families of polynomial APN permutations in odd dimensions were proposed: one family of APN binomials and one family of triprojective APN functions. The existence of APN permutations in even dimensions, which was known as the "big APN problem", was answered in 2009 when Dillon et al. discovered an APN permutation over $F_{2^6}$, namely the "Dillon permutation". There were also some negative results related to the "big APN problem". In fact, all quadratic APN functions in odd dimensions were AB functions and have optimal nonlinearity. APN functions in even dimensions whose Walsh spectrum distribution coincides with that of Gold functions were called classical. It was worth noting that all known infinite families of APN polynomials were quadratic. In 2009, Edel et al. found a cubic APN polynomial and one non-classical APN function example over $F_{2^6}$ using the "Switching Method". In 2021, Beierle et al. found four non-classical examples over $F_{2^8}$ through "Recursive Tree Search". In 2023, Kölsch et al. proved that all 3-to-1 APN functions were classical.

Fifth, APN functions have important applications in coding theory and combinatorial design. Using APN monomials and selecting appropriate defining sets, researchers have constructed linear codes with optimal parameters. Further results in this direction included the construction of optimal linear codes from APN functions via trace functions. Moreover, by using finite fields as the point sets, and constructing appropriate block sets based on APN monomials, researchers have provided 2-designs and 3-designs. Additional 2-designs and 3-designs have also been derived from linear codes constructed from APN functions.

Overall, scholars have achieved notable advances in APN function research. Through various generation and construction methods, many new APN functions, including infinite families, have been obtained, and important related issues, such as the equivalence problem and cryptographic properties of APN functions, have been investigated. Nevertheless, several key challenges in the field remain open. For example, the "big APN problem". Is Dobbertin’s conjecture on the nonexistence of additional APN monomials over finite fields true? Can a theoretical asymptotic bound on the number of APN functions be established? How to systematically construct infinite families of APN polynomials with high algebraic degree (greater than 2)? Furthermore, constructing infinite classes of APN polynomials with non-classical spectra remains a difficult task. Further progress in resolving these problems holds significant theoretical relevance and practical importance.