Two New Families of Quadratic APN Functions Li, Kangquan; Zhou, Yue; Li, Chunlei ...
IEEE transactions on information theory,
2022-July, Volume:
68, Issue:
7
Journal Article
Peer reviewed
In this paper, we present two new families of APN functions. The first family is in bivariate form <inline-formula> <tex-math notation="LaTeX">\big (x^{3}+xy^{2}+ y^{3}+xy, ...x^{5}+x^{4}y+y^{5}+xy+x^{2}y^{2} \big)\,\,\vphantom {_{\int _{\int }}} </tex-math></inline-formula>over <inline-formula> <tex-math notation="LaTeX">{\mathbb F}_{2^{m}}^{2} </tex-math></inline-formula>. It is obtained by adding certain terms of the form <inline-formula> <tex-math notation="LaTeX">\sum _{i}(a_{i}x^{2^{i}}y^{2^{i}},b_{i}x^{2^{i}}y^{2^{i}}) </tex-math></inline-formula> to a family of APN functions recently proposed by Gölo&gcaron;lu. The<inline-formula> <tex-math notation="LaTeX">\vphantom {_{\int _{\int }}} </tex-math></inline-formula> second family has the form <inline-formula> <tex-math notation="LaTeX">L(z)^{2^{m}+1}+vz^{2^{m}+1} </tex-math></inline-formula> over <inline-formula> <tex-math notation="LaTeX">{\mathbb F}_{{2^{3m}}} </tex-math></inline-formula>, which generalizes a family of APN functions by Bracken et al. from 2011. By calculating the <inline-formula> <tex-math notation="LaTeX">\Gamma </tex-math></inline-formula>-rank of the constructed APN functions over <inline-formula> <tex-math notation="LaTeX">{\mathbb F}_{2^{8}} </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">{\mathbb F}_{2^{9}} </tex-math></inline-formula>, we demonstrate that the two families are CCZ-inequivalent to all known families. In addition, the two new families cover two known sporadic APN instances over <inline-formula> <tex-math notation="LaTeX">{\mathbb F}_{2^{8}} </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">{\mathbb F}_{2^{9}} </tex-math></inline-formula>, which were found by Edel and Pott in 2009 and by Beierle and Leander in 2021, respectively.
This paper is dedicated to a question whether the currently known families of quadratic APN polynomials are pairwise different up to CCZ-equivalence. We reduce the list of these families to those ...CCZ-inequivalent to each other. In particular, we prove that the families of APN trinomials (constructed by Budaghyan and Carlet in 2008) and multinomials (constructed by Bracken et al. 2008) are contained in the APN hexanomial family introduced by Budaghyan and Carlet in 2008. We also prove that a generalization of these trinomial and multinomial families given by Duan et al. (2014) is contained in the family of hexanomials as well.
Let <inline-formula> <tex-math notation="LaTeX">n=2m </tex-math></inline-formula>. In 2020, Budaghyan, Helleseth and Kaleyski IEEE TIT 66(11): 7081-7087, 2020 considered a family of quadrinomials ...over <inline-formula> <tex-math notation="LaTeX">\mathbb {F}_{2^{n}} </tex-math></inline-formula> of the form <inline-formula> <tex-math notation="LaTeX">x^{3}+a(x^{2^{s}+1})^{2^{k}}+bx^{3\cdot 2^{m}}+c(x^{2^{s+m}+2^{m}})^{2^{k}} </tex-math></inline-formula>. They showed that two infinite classes of almost perfect nonlinear (APN) functions belong to this family when <inline-formula> <tex-math notation="LaTeX">\gcd (6,m)=1 </tex-math></inline-formula>. We observe that these two infinite classes of APN quadrinomials and the infinite class of APN polynomials from the Budaghyan-Carlet family belong to a more general family of polynomials over <inline-formula> <tex-math notation="LaTeX">\mathbb {F}_{2^{n}} </tex-math></inline-formula> with the form <inline-formula> <tex-math notation="LaTeX">f(x)=a{\mathrm{ Tr}}^{n}_{m}(F(x))+a^{2^{m}}{\mathrm{ Tr}}^{n}_{m}(G(x)) </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">a \in \mathbb {F}_{2^{n}}\backslash \mathbb {F}_{2^{m}} </tex-math></inline-formula>, and both <inline-formula> <tex-math notation="LaTeX">F </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">G </tex-math></inline-formula> are quadratic functions over <inline-formula> <tex-math notation="LaTeX">\mathbb {F}_{2^{n}} </tex-math></inline-formula>. We characterize when <inline-formula> <tex-math notation="LaTeX">f(x) </tex-math></inline-formula> is APN. With the help of our characterization, letting <inline-formula> <tex-math notation="LaTeX">F(x)=bx^{2^{i}+1} </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">G(x)=cx^{2^{s}+1} </tex-math></inline-formula> with <inline-formula> <tex-math notation="LaTeX">b, c\in \mathbb {F}_{2^{n}} </tex-math></inline-formula>, we obtain an infinite family of APN functions of the form <inline-formula> <tex-math notation="LaTeX">f(x) </tex-math></inline-formula> when <inline-formula> <tex-math notation="LaTeX">{\mathrm{ gcd}}(2,m)=1 </tex-math></inline-formula> and verify that for <inline-formula> <tex-math notation="LaTeX">n=10 </tex-math></inline-formula> two APN instances from this infinite family are CCZ-inequivalent to each other, and to any APN function over <inline-formula> <tex-math notation="LaTeX">\mathbb {F}_{2^{10}} </tex-math></inline-formula> from the previously known infinite families.
All almost perfect nonlinear (APN) permutations that we know to date admit a special kind of linear self-equivalence, i.e., there exists a permutation <inline-formula> <tex-math notation="LaTeX">G ...</tex-math></inline-formula> in their CCZ-equivalence class and two linear permutations <inline-formula> <tex-math notation="LaTeX">A </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">B </tex-math></inline-formula>, such that <inline-formula> <tex-math notation="LaTeX">G \circ A = B \circ G </tex-math></inline-formula>. After providing a survey on the known APN functions with a focus on the existence of self-equivalences, we search for APN permutations in dimension 6, 7, and 8 that admit such a linear self-equivalence. In dimension six, we were able to conduct an exhaustive search and obtain that there is only one such APN permutation up to CCZ-equivalence. In dimensions 7 and 8, we performed an exhaustive search for all but a few classes of linear self-equivalences and we did not find any new APN permutation. As one interesting result in dimension 7, we obtain that all APN permutation polynomials with coefficients in <inline-formula> <tex-math notation="LaTeX">\mathbb {F}_{2} </tex-math></inline-formula> must be (up to CCZ-equivalence) monomial functions.
In this paper, we establish a lower bound on the total number of inequivalent APN functions on the finite field with 22m elements, where m is even. We obtain this result by proving that the APN ...functions introduced by Pott and the second author 22, which depend on three parameters k, s and α, are pairwise inequivalent for distinct choices of the parameters k and s. Moreover, we determine the automorphism group of these APN functions.
The inverse function <inline-formula> <tex-math notation="LaTeX">x \mapsto x^{-1} </tex-math></inline-formula> on <inline-formula> <tex-math notation="LaTeX">\mathbb F_{2^{n}} ...</tex-math></inline-formula> is one of the most studied functions in cryptography due to its widespread use as an S-box in block ciphers like AES. In this paper, we show that, if <inline-formula> <tex-math notation="LaTeX">n\geq 5 </tex-math></inline-formula>, every function that is CCZ-equivalent to the inverse function is already EA-equivalent to it. This confirms a conjecture by Budaghyan, Calderini and Villa. We also prove that every permutation that is CCZ-equivalent to the inverse function is already affine equivalent to it. The majority of the paper is devoted to proving that there is no permutation polynomial of the form <inline-formula> <tex-math notation="LaTeX">L_{1}(x^{-1})+L_{2}(x) </tex-math></inline-formula> over <inline-formula> <tex-math notation="LaTeX">\mathbb F_{2^{n}} </tex-math></inline-formula> if <inline-formula> <tex-math notation="LaTeX">n\geq 5 </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">L_{1},L_{2} </tex-math></inline-formula> are nonzero linear functions. In the proof, we combine Kloosterman sums, quadratic forms and tools from additive combinatorics.
An important problem on almost perfect nonlinear (APN) functions is the existence of APN permutations on even-degree extensions of F2 larger than 6. Browning et al. (2010) gave the first known ...example of an APN permutation on the degree-6 extension of F2. The APN permutation is CCZ-equivalent to the previously known quadratic Kim κ-function (Browning et al. (2009)). Aside from the computer based CCZ-inequivalence results on known APN functions on even-degree extensions of F2 with extension degrees less than 12, no theoretical CCZ-inequivalence result on infinite families is known. In this paper, we show that Gold and Kasami APN functions are not CCZ-equivalent to permutations on infinitely many even-degree extensions of F2. In the Gold case, we show that Gold APN functions are not equivalent to permutations on any even-degree extension of F2, whereas in the Kasami case we are able to prove inequivalence results for every doubly-even-degree extension of F2.
Boolean plateaued functions and vectorial functions with plateaued components play a significant role in cryptography, sequences for communications, and the related combinatorics and designs. Our ...knowledge on them is not at a level corresponding to their importance. We introduce new characterizations of plateaued Boolean functions. We give the characterizations of vectorial functions whose components are all plateaued (with possibly different amplitudes), that we simply call plateaued, by means of the value distributions of their derivatives (we characterize similarly those functions whose components are partially bent) and autocorrelation functions, and of the power moments of their Walsh transform. This allows us to derive several characterizations of almost perfect nonlinear (APN) functions in this framework. We prove that all the main results known for quadratic APN functions extend to plateaued functions, allowing the study of their APN-ness to be simplified. We show that if, additionally, the component functions are all unbalanced, this study is still simpler: the APN-ness of such functions depends only on their value distribution. This allows proving, for instance, that any plateaued (n, n)-function, n even, having similar value distribution as the APN power functions, is APN, and has the same extended Walsh spectrum as the APN Gold functions. As by-products, we obtain a few other new results. For instance, any plateaued function in even dimension, which is Carlet-Charpin-Zinoviev (CCZ)-equivalent to a Gold or Kasami APN function, is necessarily extended affine (EA)-equivalent to it.
Two vectorial Boolean functions are “CCZ-equivalent” if there exists an affine permutation mapping the graph of one to the other. It preserves many of the cryptographic properties of a function such ...as its differential and Walsh spectra, which is why it could be used by Dillon et al. to find the first APN permutation on an even number of variables. However, the meaning of this form of equivalence remains unclear. In fact, to the best of our knowledge, it is not known how to partition a CCZ-equivalence class into its Extended-Affine (EA) equivalence classes; EA-equivalence being a simple particular case of CCZ-equivalence.
In this paper, we characterize CCZ-equivalence as a property of the zeroes in the Walsh spectrum of a function F:F2n→F2m or, equivalently, of the zeroes in its Difference Distribution Table. We use this framework to show how to efficiently upper bound the number of distinct EA-equivalence classes in a given CCZ-equivalence class. More importantly, we prove that it is possible to go from a specific member of any EA-equivalence class to a specific member of another EA-equivalence class in the same CCZ-equivalence class using an operation called twisting; so that CCZ-equivalence can be reduced to the association of EA-equivalence and twisting. Twisting a function is a simple process and its possibility is equivalent to the existence of a particular decomposition of the function considered. Using this knowledge, we revisit several results from the literature on CCZ-equivalence and show how they can be interpreted in light of our new framework.
Our results rely on a new concept, the “thickness” of a space (or linear permutation), which can be of independent interest.
PDF
