WorksComputer Science
The APN Property of Two Families of functions over \F_{2^{n}} from the Switching Construction
Abstract
Let be odd with . Helleseth, Ichanska, and Kaleyski \cite{HIK} conjectured that two norm-perturbed Budaghyan–Helleseth–Kaleyski functions over \F_{2^{2m}} are APN. In this paper, we prove this conjecture. First, by using the basis of \F_{2^{2m}} over \F_{2^m}, we show that and are EA-equivalent to two functions and , respectively. Their derivatives can be written as two trace equations for a matrix P\in\mathrm{GL}(2,\F_{2^m}). We then prove that these two equations have no solution. The proof uses only identities over finite fields, the characteristic polynomial of a matrix, and elementary properties of Frobenius automorphisms. The repeated-root case and all parity cases are considered separately. It follows that the derivative of each function has kernel of size two in every nonzero direction, and hence both and are APN for every admissible .
Introduction
Let and be two positive integers. A mapping from to is called an -function, or a vectorial Boolean function. Such mappings are used as substitution boxes in block ciphers and form the main nonlinear component of many symmetric cryptosystems. Differential cryptanalysis is one of the most efficient attacks on block ciphers [1], and differential uniformity was introduced to measure the resistance of a function to this attack [9]. When , the smallest possible differential uniformity is two, and the functions attaining this bound are called almost perfect nonlinear (APN) functions. Among the equivalence relations for vectorial Boolean functions, the Carlet–Charpin–Zinoviev (CCZ) equivalence is the most general known one preserving differential uniformity [3]. Consequently, constructing APN functions that are CCZ-inequivalent to the known constructions is an important but difficult problem. Prior to the recent switching families, the known constructions were commonly summarized as six infinite families of APN monomials, thirteen families in univariate polynomial form, nine families in bivariate form, and two families in trivariate form; see [7] and the references therein.
Constructions of APN functions can be broadly divided into primary constructions, which define APN functions directly, and secondary constructions, which derive new APN functions from known ones. An important secondary method is the switching construction of Edel and Pott [4]. Starting from an APN function , it considers a perturbation , where is a field element and is Boolean, and seeks conditions under which the APN property is preserved. Although this method has produced several sporadic APN functions, obtaining an infinite family by switching is considerably more difficult: both the Boolean perturbation and the proof of the APN property must work uniformly in the field dimension. In 2009, by using the switching method to perturb the Gold function with a trace term, Budaghyan et al. constructed new infinite families of APN functions [2].
Recently, in [5], Helleseth et al. applied the switching method in even dimension to the Budaghyan–Helleseth–Kaleyski (BHK) quadrinomials [6] and obtained new infinite families by perturbing them with functions of the relative norm. This is the first construction of infinite families of APN functions obtained by applying the switching method to a non-power APN family. The construction uses the Frobenius conjugates of the relative norm as structured perturbation terms. Suitable combinations of these conjugates give four families in even dimension, organized into two switching pairs. In the first pair, one construction is EA-equivalent to a previously known family that obtained by Li et al. [8], whereas its switching neighbor was proved to be a new infinite family of APN functions. For the second pair, denoted by and , extensive computations support the APN property, and it was conjectured that both families are APN over for every odd with .
Conjecture 1. [5] Let be odd with , , and . Let and
Then
F_3(z)=B(z)+\beta^2z^{2^m+1}+\sum_{j=1}^{k}(z^{2^m+1})^{2^j}+\beta\sum_{j=k+1}^{m-1}(z^{2^m+1})^{2^j}.
The purpose of this paper is to prove this conjecture. Our proof is based entirely on finite-field and elementary matrix arguments. Using the basis of over , we first show that and are EA-equivalent to two bivariate functions and , respectively. For a nonzero derivative direction and a possible derivative zero , we put . When , the derivative equations are converted into two matrix equations. By studying the traces, determinants, and characteristic polynomials of the matrices involved, together with their behavior under Frobenius automorphisms, we show that the two equations cannot hold simultaneously. When , a direct calculation shows that . Hence every nonzero derivative has kernel of size two.
The remainder of this paper is organized as follows. Section III recalls the necessary definitions and finite-field facts. In Section III, we derive the EA-equivalent bivariate forms of and . Section IV presents the APN proof of and , and Section V concludes the paper.
Preliminaries
For positive integers , the relative trace from to is denoted by and is defined by
In particular, denotes the absolute trace on . For an -function , let be the number of solutions of
The differential uniformity of is
The function is APN if .
For a quadratic function , define its symmetric derivative by
For every , is -linear and . Therefore, is APN if and only if
for every .
We now recall several notions of equivalence between -functions.
Definition 1. Two functions are called extended affine equivalent (EA-equivalent), if there exist three affine functions , where are permutations, such that
In particular, are called extended linear equivalent (EL-equivalent) if they are EA-equivalent and are linear mappings, are called affine equivalent if they are EA-equivalent and , are called linear equivalent if they are affine equivalent and are linear mappings.
Definition 2. Two functions are called Carlet-Charpin-Zinoviev equivalent (CCZ-equivalent), if their graphs are affine equivalent, that is, if there is an affine permutation on such that , where is the graph of .
EA-equivalence implies CCZ-equivalence, and both equivalences preserve differential uniformity and, in particular, the APN property.
Throughout the paper, let be odd with , and put
Let satisfy . Since is odd, we have
Consequently, is a basis of over . Denote
We identify each power with the corresponding Frobenius automorphism of , and products and inverses of such powers are understood as compositions and inverses of these automorphisms. Put
As usual, means . The same notation is used entrywise for vectors and matrices. The following identities will be used repeatedly.
For a field and an automorphism of , the fixed field of in is
Lemma 1. Let , , and . Then
Moreover,
Then the fixed field in of is when is even and when is odd. Finally,
Proof: The first identity in (4) follows by squaring the definition of . Since , adding and gives all conjugates of except the last one, and this proves the second identity. The fixed field of the map on is . Now
which gives all the fixed fields. (4) follows from reducing modulo .
A one-dimensional -subspace of is a set of the form
where . We shall use the following elementary observation. If such a line is stable under a Frobenius automorphism , then it has a nonzero vector over . Indeed, write the line as . If , its stability implies , so is such a vector. The case is clear.
A square matrix over a field is called nilpotent if for some positive integer . If is a nonzero nilpotent matrix, then its minimal polynomial is a nonconstant divisor of and has degree at most two. Since , its minimal polynomial cannot be . It is therefore , and hence .
Lemma 2. Let be two nonzero nilpotent matrices over a field of characteristic two. If , then .
Proof. Since and , choose such that . Then , and are linearly independent. Hence, with respect to the basis , the matrix of is
After applying this change of basis simultaneously to and , we may therefore assume that
Write ; its two diagonal entries are equal because is nilpotent and therefore has trace zero. The condition gives , while gives . Thus is a nonzero scalar multiple of , and the result follows.
An EA-equivalent bivariate form
In this section, we show that the functions from and in Conjecture 1 are EA-equivalent to bivariate functions.
For a column , define
Then
Lemma 3. For , define by
Then
Proof. Write the input of as , where . Since , we have ; hence . Moreover, is odd because it is the inverse of the odd integer modulo . Therefore,
A direct calculation using gives
For every , the difference
is an -linear function of and can be removed by an EA transformation. Put . Modulo such linear terms, the perturbation in is
Apply the invertible output map
By (10)–(12), the BHK component becomes , and the displayed perturbation becomes
This proves . The difference between the two perturbations satisfies
Under the same output map, this adds . Moreover,
the first two terms are linear and can again be removed. Thus .
Let be two columns, put and . If , then . From (6),
Indeed, if
then
and the polar part of is . The polar parts of , , and are , , and , respectively. Therefore, a nontrivial zero of a derivative of with gives a matrix satisfying the following system of two equations:
The APN property
In this section, we prove the APN property of the functions from and in Conjecture 1. We first prove that (14)–(15) have no solution.
Lemma 4. For every , there is no matrix satisfying (14)–(15).
Proof. Assume otherwise. Put
and
Thus and .
Since as an automorphism of , , and , we have
and hence
For every invertible matrix , . By using (14), (16), and , we get
Here we used and . On the other hand, combining (17) with (3) and (15), we obtain
The product
is obtained by using and cancelling all intermediate factors. Since , is or . Hence the matrix in (19) has characteristic polynomial
Because is odd, (20) is irreducible over . In particular, has no one-dimensional invariant subspace over .
We divide the remainder of the proof into two cases.
Case 1: .
Put and . From , we obtain
After substituting , the equation becomes . The image of on is precisely the absolute-trace-zero subspace. Thus, by (21), the polynomial splits over if and only if . Let be its splitting field. Choose satisfying . Since , we have . Set
By (21), and are the two roots of .
Let
Then . Moreover,
Indeed,
Let be an eigenvector matrix of , and write
Put . A direct multiplication gives
Comparing (18), (22), and (23), we obtain
Subcase 1.1: . Both eigenvalues and eigenlines of are defined over . Equation (24) shows that is upper or lower triangular. Hence at least one eigenline is stable under . The semilinear map
preserves this -line. Its -th iterate, whose matrix is , preserves the same line, contradicting (20)–(21).
Subcase 1.2: . Then , where , and the -Frobenius interchanges the two eigenlines. Choose the two columns of as a conjugate pair. Then
Since the - and -Frobenius maps commute, we have . Thus
Subcase 1.2.1: . By (24) and (26), . Thus both eigenlines are stable under . If is odd, Lemma 1 and the elementary fixed-line observation imply that both lines are defined over . This contradicts the irreducibility of over : a -rational eigenline of the matrix has an eigenvalue in .
Let be even. Since , choose satisfying . Let and put . Then
Consequently,
satisfies
Hence it is one of . The product of its -conjugates is
by (4); the same holds for . The two eigenlines have vectors over . Using these vectors as the columns of gives , and therefore
This contradicts (20)–(21).
Subcase 1.2.2: . Equation (24) gives , so . By (26), . Therefore, interchanges the two eigenlines. If is even, the automorphism fixes both lines. Its fixed field is by Lemma 1, so the two lines are defined over , a contradiction.
It remains to consider odd . Choose satisfying , and put , where . Now and
The element
satisfies
Thus are the eigenvalues of . The two eigenlines are fixed by , whose fixed field is . Choose their eigenvector matrix as follows: choose a nonzero vector on the first line and take its -th power as the second column. Then . Since both and are odd, the - and -Frobenius maps act as squaring on , and hence as well. In the -coordinates, the map (25) has matrix
The product is anti-diagonal. Its upper-right entry is
By (4), on . The numerator and denominator in (29) contain exactly the same conjugates
because the numerator exponents are
whereas the denominator exponents are
where in all four sets. Both sets are exactly the odd residues modulo . Hence . The lower-left entry is , and consequently . For completeness, if , then the two descriptions of the -th iterate of (25) give
Since , it follows that
contradicting (19).
Case 2: . Then . By (3), . Since and , we have and . The characteristic polynomial of is , so write , where . If , the left-hand side of (19) is , which is impossible. Hence is a nonzero rank-one nilpotent matrix. From (18),
Indeed, after expanding , the traces of , , and all vanish in characteristic two. By Lemma 2, and have the same kernel. Since , the -line is stable under . It is preserved by (25), and consequently by its -th iterate . This again contradicts (19)–(20).
All cases lead to a contradiction, and the proof is complete.
We now combining Lemma 4 to prove the APN property of the functions from and .
Theorem 1. Let be odd with . The two functions and defined in (1)–(2) are APN over .
Proof. By Lemma 3, it is enough to prove that is APN for . Let be a derivative direction and let be in the kernel of its symmetric derivative. Put .
If , equations (12)–(14) give a matrix satisfying (13)–(14), which is impossible by Lemma 4.
Now let . Then for some . The second coordinate of the derivative of is
We claim that . If , this is clear. If and , then is a root of . This polynomial is irreducible over and its roots belong to . However,
which is a contradiction. Thus (31) vanishes only when , and therefore or .
We have proved that the kernel of every nonzero derivative is exactly . Hence and are APN. By (8), the same is true for and , respectively.
Conclusion
We have proved that the two conjectured families and are APN over for every odd with . The main step is the EA-equivalent form (7), which transforms every possible nontrivial derivative zero with into the two matrix equations (14)–(15). The local identity (18) controls the Frobenius action on the two eigenlines of , while the global product (19) has no invariant line over . The resulting contradiction excludes all nontrivial derivative zeros and completes the proof of Conjecture 1 in [5].
References
- [1]E. Biham and A. Shamir, “Differential cryptanalysis of DES-like cryptosystems,” J. Cryptology, vol. 4, no. 1, pp. 3–72, 1991.
- [2]L. Budaghyan, C. Carlet, and G. Leander, “Constructing new APN functions from known ones,” Finite Fields Appl., vol. 15, no. 2, pp. 150–159, 2009.
- [3]C. Carlet, P. Charpin, and V. Zinoviev, “Codes, bent functions and permutations suitable for DES-like cryptosystems,” Des. Codes Cryptogr., vol. 15, no. 2, pp. 125–156, 1998.DOI
- [4]Y. Edel and A. Pott, “A new almost perfect nonlinear function which is not quadratic,” IACR Cryptology ePrint Archive, Paper 2008/313, 2008.
- [5]T. Helleseth, N. Ichanska, and N. S. Kaleyski, “New infinite families of APN functions from the switching construction in even dimension,” IACR Cryptology ePrint Archive, Paper 2026/2401, 2026.
- [6]L. Budaghyan, T. Helleseth, and N. S. Kaleyski, “A new family of APN quadrinomials,” IEEE Trans. Inf. Theory, vol. 66, no. 11, pp. 7081–7087, Nov. 2020.DOI
- [7]K. Li and N. S. Kaleyski, “Two new infinite families of APN functions in trivariate form,” IEEE Trans. Inf. Theory, vol. 70, no. 2, pp. 1436–1452, Feb. 2024.DOI
- [8]K. Li, Y. Zhou, C. Li, and L. Qu, “Two new families of quadratic APN functions,” IEEE Trans. Inf. Theory, vol. 68, no. 7, pp. 4761–4769, Feb. 2022.DOI
- [9]K. Nyberg, “Differentially uniform mappings for cryptography,” in Advances in Cryptology—EUROCRYPT’93, Lecture Notes in Computer Science, vol. 765. Berlin, Germany: Springer, 1994, pp. 55–64.