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.
New Instances of Quadratic APN Functions Beierle, Christof; Leander, Gregor
IEEE transactions on information theory,
2022-Jan., 2022-1-00, Volume:
68, Issue:
1
Journal Article
Peer reviewed
Open access
In a recent work, Beierle, Brinkmann and Leander presented a recursive tree search for finding APN permutations with linear self-equivalences in small dimensions. In this paper, we describe how this ...search can be adapted to find many new instances of quadratic APN functions. In particular, we found 12,921 new quadratic APN functions in dimension eight, 35 new quadratic APN functions in dimension nine and five new quadratic APN functions in dimension ten up to CCZ-equivalence. Remarkably, two of the 35 new APN functions in dimension nine are APN permutations. Among the 8-bit APN functions, there are three extended Walsh spectra that do not correspond to any of the previously-known quadratic 8-bit APN functions and, surprisingly, there exist at least four CCZ-inequivalent 8-bit APN functions with linearity 2 7 , i.e., the highest possible non-trivial linearity for quadratic functions in dimension eight.
Vectorial Boolean functions play an important role in cryptography, sequences and coding theory. Both affine equivalence and EA-equivalence are well known equivalence relations between vectorial ...Boolean functions. In this paper, we give an exact formula for the number of affine equivalence classes, and an asymptotic formula for the number of EA-equivalence classes of vectorial Boolean functions.
In this paper, we propose three new classes of permutation trinomials over Fq3. The first two classes are of the form x+L(xq2+q−1), where L(x)∈{x+Axq,x+Axq2}, q even, and the third class is ...x+Axq2−q+1+A2xq2, q odd. In fact we prove a conjecture proposed by Gong, Gao and Liu 8 about permutation trinomials of the form xq+1+L(x)∈Fq3x as a particular case of our results. Moreover, we determine necessary and sufficient conditions for the permutation trinomials studied. We also show that the permutation trinomials proposed in this paper are new in the sense that they are not quasi-multiplicative equivalent to permutation trinomials over Fq3 known so far.
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.
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.
Recently, Beierle and Leander found two new sporadic quadratic APN permutations in dimension 9. Up to EA-equivalence, we present a single trivariate representation of those two permutations as ...Cu:(F2m)3→(F2m)3,(x,y,z)↦(x3+uy2z,y3+uxz2,z3+ux2y), where m=3 and u∈F23∖{0,1} such that the two permutations correspond to different choices of u. We then analyze the differential uniformity and the nonlinearity of Cu in a more general case. For m≥3 being a multiple of 3 and u∈F2m not being a 7-th power, we show that the differential uniformity of Cu is bounded above by 8, and that the linearity of Cu is bounded above by 81+⌊m2⌋. Based on numerical experiments, we conjecture that Cu is not APN if m is greater than 3. We also analyze the CCZ-equivalence classes of the quadratic APN permutations in dimension 9 known so far and derive a lower bound on the number of their EA-equivalence classes. We further show that the two sporadic APN permutations share an interesting similarity with Gold APN permutations in odd dimension divisible by 3, namely that a permutation EA-inequivalent to those sporadic APN permutations and their inverses can be obtained by just applying EA transformations and inversion to the original permutations.
Constructions and equivalence of APN functions play a significant role in the research of cryptographic functions. On finite fields of characteristic 2, 6 families of power APN functions and 14 ...families of polynomial APN functions have been constructed in the literature. However, the study on the equivalence among the aforementioned APN functions is rather limited to the equivalence in the power APN functions. Meanwhile, the theoretical analysis on the equivalence between the polynomial APN functions and the power APN functions, as well as the equivalence in the polynomial APN functions themselves, is far less studied. In this paper, we give the theoretical analysis on the inequivalence in 8 known families of polynomial APN functions and power APN functions.
PDF
