On the behavior of some APN permutations under swapping points

We define the pAPN-spectrum (which is a measure of how close a function is to being APN) of an (n, n)-function F and investigate how its size changes when two of the outputs of a given function F are swapped. We completely characterize the behavior of the pAPN-spectrum under swapping outputs when F is the inverse function over \(\mathbb {F}_{2^{n}}\). We further theoretically investigate this behavior for functions from the Gold and Welch monomial APN families, and experimentally determine the size of the pAPN-spectrum after swapping outputs for representatives from all infinite monomial APN families up to dimension n = 10; based on our computation results, we conjecture that the inverse function is the only monomial APN function for which swapping two of its outputs can leave an empty pAPN-spectrum.

1. We have been calling this the “Rodier condition”, but we realized that it did occur in the literature prior to Rodier’s work, for power monomials in [11], so we will now call it by the three names.

The authors would like to thank the referees for the thorough reading and detailed comments, which improved our manuscript. The paper was started while the fourth named author visited the Selmer Center at the University of Bergen and the Western Norway University of Applied Sciences in the Spring of 2019. This author thanks these institutions for the excellent working conditions. The research of the first two named authors is supported by the “Optimal Boolean Functions” grant of the Trond Mohn foundation.

Authors and Affiliations

1. Department of Informatics, University of Bergen, Postboks 7803, N-5020, Bergen, Norway

   Lilya Budaghyan & Nikolay Kaleyski

2. Department of Computer Science, Electrical Engineering and Mathematical Sciences, Western Norway University of Applied Sciences, 5020, Bergen, Norway

   Constanza Riera

3. Department of Applied Mathematics, Naval Postgraduate School, Monterey, CA, 93943-5212, U.S.A.

   Pantelimon Stănică

Corresponding author

Correspondence to Pantelimon Stănică.

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article belongs to the Topical Collection: Sequences and Their Applications III

Guest Editors: Chunlei Li, Tor Helleseth and Zhengchun Zhou

This is asubstantially revised and extended version of the article [5] that appeared in the proceedings of the Sequences and Their Applications – SETA 2020. In particular, the proofs for the Gold and Welch case, and the computational data given in the appendix, are new.

Appendix A: Experimental data on the infinite APN families

For functions from each of the infinite APN monomial families over \(\mathbb {F}_{2^{n}}\) with n ≤ 10 (except for the inverse family which is characterized by Theorem 4), we have computed the size of the pAPN-spectrum of \(G_{x_{0} x_{1}}\) for all possible pairs \((x_{0}, x_{1}) \in \mathbb {F}_{2^{n}}^{2}\). The results are given in Tables 2, 3, 4, 5, 6 below.

In all cases, the results are computed for generalizations of the respective infinite families, with all restrictions on the parameters dropped. This means that we consider the following functions over \(\mathbb {F}_{2^{n}}\), with the parameter i being any positive integer in the range 1 ≤ i ≤ n − 1:

• \(x^{2^{4i} + 2^{3i} + 2^{2i} + 2^{i} - 1}\) for Dobbertin,

• \(x^{2^{2i} - 2^{i} + 1}\) for Kasami,

• \(x^{2^{i} + 2^{i/2} - 1}\) or \(x^{2^{i} + 2^{(3i+1)/2} - 1}\) for even and odd values of i, respectively, for Niho,

• \(x^{2^{i}+3}\) for Welch, and

• \(x^{2^{i}+1}\) for Gold.

The first two columns of each table specify the degree n of the extension field \(\mathbb {F}_{2^{n}}\) and the value of the parameter i. The third column gives the smallest element from the cyclotomic coset of the resulting exponent d. The fourth and fifth columns give the differential uniformity and size of the pAPN-spectrum of x^d over \(\mathbb {F}_{2^{n}}\), respectively. Finally, the last column describes how the pAPN-spectrum changes after swapping two output values of the function. More precisely, for every pair \(\{ x_{0}, x_{1} \} \subseteq \mathbb {F}_{2^{n}}\) with x₀≠x₁, we compute the size of the pAPN-spectrum of \(G_{x_{0} x_{1}}\); the last column then lists the sizes of all possible spectra obtained in this way. The frequencies with which these sizes occur over all possible pairs {x₀, x₁} are given as superscripts. For example, the first row of Table 2 contains 0⁴⁵, 2⁶⁰, 8¹⁵ in the last column. This means that, out of the 120 pairs \(\{ x_{0}, x_{1} \} \subseteq \mathbb {F}_{2^{4}}\), 45 pairs produce a function with an empty pAPN-spectrum, 60 pairs produce a function which is ζ-APN for two values of ζ, and the remaining 15 pairs lead to functions that are ζ-APN for 8 values of ζ.

By Proposition 3, all exponents d such that x^d has 2^s-to-1 derivatives for some fixed s > 1 are omitted. All such functions and all two-point swaps of these functions have an empty pAPN-spectrum by the proposition, and are therefore of very limited interest. These include all Gold functions with \(\gcd (i,n) > 1\) and all Kasami functions with \(\gcd (i,n) > 1\) and \(n/\gcd (i,n)\) odd. They also include the exponents i = 3, 4 for n = 6 and i = 5 for n = 10 in the Dobbertin case; i = 3 for n = 6 in the Kasami case; i = 1 for even n, i = 4 for n = 6 and i = 8 for n = 10 in the Welch case; i = 1, 2 for n even, i = 3 for n = 5, i = 4 for n = 6, i = 5 for n = 8 and i = 6 for n = 9 in the Niho case.

We note that in some cases, swap operations lead to a full-sized pAPN-spectrum, indicating that the corresponding function is APN. This occurs exclusively in even dimensions for APN functions, and is caused by pairs {x₀, x₁} with x₀≠x₁ but F(x₀) = F(x₁), where F is the function in question. Consider, for example, F(x) = x³ for n = 6 and i = 2 in Table 2; there are 63 pairs leading to a pAPN-spectrum of size 64. We know that APN power functions over even-degree extensions of \(\mathbb {F}_{2}\) are 3-to-1; in this case, x³ has 21 non-zero images y, for each of which there are three pre-images x₁, x₂, x₃ such that F(x₁) = F(x₂) = F(x₃) = y. Since a pair of elements from among {x₁, x₂, x₃} can be selected in three different ways, each of the 21 images contributes three pairs, leading to these 63 pairs which trivially preserve the APN-ness of the initial function.

The only exceptions to this occur for n = 4; for example, for F(x) = x³ in Table 2, there are 30 pairs giving a full pAPN-spectrum, while the trivial pairs as described above account for only 15 of these. To the best of our knowledge, n = 4 is the highest extension degree for which APN functions at Hamming distance 2 from each other exist; this is reflected in e.g. [12] and agrees with the results presented in the tables.

Conversely, we can observe that the inverse function is the only APN function among the ones considered whose pAPN-spectrum can become empty after a two-point swap. We ran a separate experiment in which we computed the sizes of the pAPN-spectra of all two-points swaps for representatives from all known CCZ-equivalence classes of APN functions, and observed the same phenomenon: the inverse function is the only one for which an empty pAPN-spectrum could be obtained by swapping two points. Based on this, we formulate the following conjecture.

Conjecture 1

Let F be any APN power function over \(\mathbb {F}_{2^{n}}\), CCZ-inequivalent to the inverse power function \(x^{2^{n}-2}\), and let \(G_{x_{0} x_{1}}\) be the (x₀, x₁)-swapping of F for some \((x_{0}, x_{1}) \in \mathbb {F}_{2^{n}}^{2}\). Then the pAPN-spectrum of \(G_{x_{0}x_{1}}\) is not empty.

According to some limited computational experiments, the same might be true for quadratic APN functions; however, we do not state this as a conjecture in general since we do not have enough data, nor heuristics on why that would happen.

We note that the multiset of the sizes of the pAPN-spectra of all functions obtained by swapping two points in a given function is not CCZ-invariant. Counterexamples can be found easily, for instance by considering the Kim function and its CCZ-equivalent permutation [2] over \(\mathbb {F}_{2^{6}}\): the pAPN-spectra of all functions obtained by swapping two outputs of the former are of even size, while pAPN-spectra of odd size can be obtained from the latter. Hence, our conjecture relates only to power APN functions and does not include the ones CCZ-equivalent to them.

Some of the functions listed in the tables have a singleton pAPN-spectrum, e.g. F(x) = x⁴⁷ for i = 3 and n = 7 in Table 2. All such functions are 0-APN.

The function F(x) = x¹⁵ over \(\mathbb {F}_{2^{8}}\), as given in Table 4, is remarkable due to the fact that all possible pairs {x₀, x₁} lead to a function with a singleton pAPN-spectrum. When x₀ = 0, the resulting function is x₁-APN, and when x₀ ≠ 0, the resulting function is 0-APN.

Reprints and permissions