betaFeedback

WorksComputer Science

The APN Property of Two Families of functions over \F_{2^{n}} from the Switching Construction

Abstract

Let m≥5m\geq5 be odd with 3∤m3\nmid m. Helleseth, Ichanska, and Kaleyski \cite{HIK} conjectured that two norm-perturbed Budaghyan–Helleseth–Kaleyski functions F2,F3F_2,F_3 over \F_{2^{2m}} are APN. In this paper, we prove this conjecture. First, by using the basis (1,β)(1,β) of \F_{2^{2m}} over \F_{2^m}, we show that F2F_2 and F3F_3 are EA-equivalent to two functions G1\mathcal G_1 and G0\mathcal G_0, 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 2×22\times2 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 F2F_2 and F3F_3 are APN for every admissible mm.

Introduction

Let nn and mm be two positive integers. A mapping from F2n\mathbb{F}_{2^n} to F2m\mathbb{F}_{2^m} is called an (n,m)(n,m)-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 n=mn=m, 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 FF, it considers a perturbation F+cfF+cf, where cc is a field element and ff 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 x3x^3 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 z2m+1z^{2^m+1} 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 F2F_2 and F3F_3, extensive computations support the APN property, and it was conjectured that both families are APN over F22m\mathbb{F}_{2^{2m}} for every odd m≥5m \ge5 with 3∤m3 \nmid m.

Conjecture 1. [5] Let m≥5m \ge5 be odd with 3∤m3 \nmid m, n=2mn=2m, i=(m−2)−1(modn)i=(m-2)^{-1}\pmod n and k=m−32k=\frac{m-3}{2}. Let β∈F4∖F2\beta\in\mathbb{F}_4 \setminus\mathbb{F}_2 and

B(z)=z3+βz2i+1+β2z3⋅2m+z(2i+1)2m.B(z)=z^3+\beta z^{2i+1}+\beta^2z^{3\cdot2^m}+z^{(2i+1)2^m}.

Then

F2(z)=B(z)+β∑j=1k(z2m+1)2j+∑j=k+1m−1(z2m+1)2j,(1)F_2(z)=B(z)+\beta\sum_{j=1}^{k}(z^{2^m+1})^{2^j}+\sum_{j=k+1}^{m-1}(z^{2^m+1})^{2^j}, \tag*{(1)}
Equation not extracted

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}.

{#eq:2} are APN over $\mathbb{F}_{2^n}$.

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 (1,β)(1,\beta) of F22m\mathbb{F}_{2^{2m}} over F2m\mathbb{F}_{2^m}, we first show that F2F_2 and F3F_3 are EA-equivalent to two bivariate functions G1\mathcal{G}_1 and G0\mathcal{G}_0, respectively. For a nonzero derivative direction AA and a possible derivative zero XX, we put T=det⁡(A X)T=\det(A\ X). When T≠0T\ne0, 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 T=0T=0, a direct calculation shows that X∈{0,A}X\in\{0,A\}. 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 F2F_2 and F3F_3. Section IV presents the APN proof of F2F_2 and F3F_3, and Section V concludes the paper.

Preliminaries

For positive integers m∣nm\mid n, the relative trace from F2n\mathbb{F}_{2^n} to F2m\mathbb{F}_{2^m} is denoted by Tr⁡mn\operatorname{Tr}_m^n and is defined by

Tr⁡mn(x)=∑j=0n/m−1x2mj.\operatorname{Tr}_m^n(x)=\sum_{j=0}^{n/m-1}x^{2^{mj}}.

In particular, Tr⁡1n\operatorname{Tr}_1^n denotes the absolute trace on F2n\mathbb{F}_{2^n}. For an (n,n)(n,n)-function FF, let ΔF(a,b)\Delta_F(a,b) be the number of solutions x∈F2nx\in\mathbb{F}_{2^n} of

F(x+a)+F(x)=b.F(x+a)+F(x)=b.

The differential uniformity of FF is

δF=max⁡a∈F2n, b∈F2nΔF(a,b).\delta_F=\max_{a\in\mathbb{F}_{2^n},\,b\in\mathbb{F}_{2^n}}\Delta_F(a,b).

The function FF is APN if δF=2\delta_F=2.

For a quadratic function F:F2n→F2nF:\mathbb{F}_{2^n}\to\mathbb{F}_{2^n}, define its symmetric derivative by

DaF(x)=F(x+a)+F(x)+F(a)+F(0).D_aF(x)=F(x+a)+F(x)+F(a)+F(0).

For every a≠0a\ne0, DaFD_aF is F2\mathbb{F}_2-linear and {0,a}⊆ker⁡DaF\{0,a\}\subseteq\ker D_aF. Therefore, FF is APN if and only if

ker⁡DaF={0,a}(2)\ker D_aF=\{0,a\} \tag*{(2)}

for every a≠0a\ne0.

We now recall several notions of equivalence between (n,n)(n,n)-functions.

Definition 1. Two functions F,G:F2n→F2nF,G:\mathbb{F}_{2^n}\to\mathbb{F}_{2^n} are called extended affine equivalent (EA-equivalent), if there exist three affine functions A1,A2,A3:F2n→F2nA_1,A_2,A_3:\mathbb{F}_{2^n}\to\mathbb{F}_{2^n}, where A1,A2A_1,A_2 are permutations, such that

F(A1(x))=A2(G(x))+A3(x).F(A_1(x))=A_2(G(x))+A_3(x).

In particular, F,GF,G are called extended linear equivalent (EL-equivalent) if they are EA-equivalent and A1,A2,A3A_1,A_2,A_3 are linear mappings, F,GF,G are called affine equivalent if they are EA-equivalent and A3=0A_3=0, F,GF,G are called linear equivalent if they are affine equivalent and A1,A2A_1,A_2 are linear mappings.

Definition 2. Two functions F,G:F2n→F2nF,G:\mathbb{F}_2^n\to\mathbb{F}_2^n are called Carlet-Charpin-Zinoviev equivalent (CCZ-equivalent), if their graphs are affine equivalent, that is, if there is an affine permutation CC on F2n×F2n\mathbb{F}_2^n\times\mathbb{F}_2^n such that C(ΓF)=ΓGC(\Gamma_F)=\Gamma_G, where ΓF={(x,F(x)):x∈F2n}\Gamma_F=\{(x,F(x)):x\in\mathbb{F}_2^n\} is the graph of FF.

EA-equivalence implies CCZ-equivalence, and both equivalences preserve differential uniformity and, in particular, the APN property.

Throughout the paper, let m≥5m\geq5 be odd with 3∤m3\nmid m, and put

q=2m,K=Fq,L=Fq2,zˉ=zq.q=2^m,\qquad K=\mathbb{F}_q,\qquad L=\mathbb{F}_{q^2},\qquad\bar{z}=z^q.

Let β∈F4∖F2\beta\in\mathbb{F}_4\setminus\mathbb{F}_2 satisfy β2+β+1=0\beta^2+\beta+1=0. Since mm is odd, we have

F4∩K=F2,βˉ=βq=β2.\mathbb{F}_4\cap K=\mathbb{F}_2,\qquad\bar{\beta}=\beta^q=\beta^2.

Consequently, (1,β)(1,\beta) is a basis of LL over KK. Denote

N(z)=zzˉ,i=(m−2)−1(mod2m),k=m−32.N(z)=z\bar{z},\qquad i=(m-2)^{-1}\pmod{2m},\qquad k=\frac{m-3}{2}.

We identify each power 2r2^r with the corresponding Frobenius automorphism z↦z2rz\mapsto z^{2^r} of LL, and products and inverses of such powers are understood as compositions and inverses of these automorphisms. Put

s=m−12,σ=2s,ts(z)=∑j=0s−1z2j(z∈K).s=\frac{m-1}{2},\qquad\sigma=2^s,\qquad t_s(z)=\sum_{j=0}^{s-1}z^{2^j}\quad(z\in K).

As usual, zσz^\sigma means z2sz^{2^s}. The same notation is used entrywise for vectors and matrices. The following identities will be used repeatedly.

For a field EE and an automorphism τ\tau of EE, the fixed field of τ\tau in EE is

Fix⁡E(τ)={z∈E:zτ=z}.\operatorname{Fix}_E(\tau)=\{z\in E:z^\tau=z\}.

Lemma 1. Let T∈KT\in K, b=ts(T)b=t_s(T), and δ=Tr⁡1m(T)\delta=\operatorname{Tr}_1^m(T). Then

b2+b=Tσ+T,bσ+b=Tσ2+δ.(3)b^2+b=T^\sigma+T,\qquad b^\sigma+b=T^{\sigma^2}+\delta. \tag*{(3)}

Moreover,

Fix⁡K(σ)=F2,\operatorname{Fix}_K(\sigma)=\mathbb{F}_2,
Fix⁡L(σ)={F2,s is odd,F4,s is even.\operatorname{Fix}_L(\sigma)= \begin{cases} \mathbb{F}_2, & s\text{ is odd},\\ \mathbb{F}_4, & s\text{ is even}. \end{cases}

Then the fixed field in Fq2\mathbb{F}_{q^2} of qσ−1=2s+1q\sigma^{-1}=2^{s+1} is F2\mathbb{F}_2 when ss is even and F4\mathbb{F}_4 when ss is odd. Finally,

σm={1,s is even,q,s is oddon L.(4)\sigma^m= \begin{cases} 1, & s\text{ is even},\\ q, & s\text{ is odd} \end{cases} \quad\text{on }L. \tag*{(4)}

Proof: The first identity in (4) follows by squaring the definition of bb. Since m=2s+1m=2s+1, adding bb and bσb^\sigma gives all conjugates of TT except the last one, and this proves the second identity. The fixed field of the map z↦z2rz\mapsto z^{2^r} on F2d\mathbb{F}_{2^d} is F2gcd⁡(r,d)\mathbb{F}_{2^{\gcd(r,d)}}. Now

gcd⁡(s,m)=1,\gcd(s,m)=1,
gcd⁡(s,2m)=gcd⁡(s,2),\gcd(s,2m)=\gcd(s,2),
gcd⁡(s+1,2m)=gcd⁡(s+1,2),\gcd(s+1,2m)=\gcd(s+1,2),

which gives all the fixed fields. (4) follows from reducing smsm modulo 2m2m.

A one-dimensional EE-subspace of E2E^2 is a set of the form

E(u,v)={λ(u,v):λ∈E},E(u,v)=\{\lambda(u,v):\lambda\in E\},

where (u,v)≠(0,0)(u,v) \ne(0,0). We shall use the following elementary observation. If such a line is stable under a Frobenius automorphism τ\tau, then it has a nonzero vector over Fix⁡E(τ)\operatorname{Fix}_{E}(\tau). Indeed, write the line as E(u,v)E(u,v). If v≠0v \ne0, its stability implies (u/v)τ=u/v(u/v)^\tau=u/v, so (u/v,1)(u/v,1) is such a vector. The case v=0v=0 is clear.

A square matrix RR over a field is called nilpotent if Rr=0R^r=0 for some positive integer rr. If RR is a nonzero nilpotent 2×22 \times2 matrix, then its minimal polynomial is a nonconstant divisor of XrX^r and has degree at most two. Since R≠0R \ne0, its minimal polynomial cannot be XX. It is therefore X2X^2, and hence R2=0R^2=0.

Lemma 2. Let R1,R2R_1,R_2 be two nonzero nilpotent 2×22 \times2 matrices over a field of characteristic two. If tr⁡(R1R2)=0\operatorname{tr}(R_1R_2)=0, then ker⁡R1=ker⁡R2\ker R_1=\ker R_2.

Proof. Since R12=0R_1^2=0 and R1≠0R_1 \ne0, choose e2e_2 such that e1=R1e2≠0e_1=R_1e_2 \ne0. Then R1e1=R12e2=0R_1e_1=R_1^2e_2=0, and e1,e2e_1,e_2 are linearly independent. Hence, with respect to the basis (e1,e2)(e_1,e_2), the matrix of R1R_1 is

(0100).\begin{pmatrix}0&1\\0&0\end{pmatrix}.

After applying this change of basis simultaneously to R1R_1 and R2R_2, we may therefore assume that

R1=(0100).R_1=\begin{pmatrix}0&1\\0&0\end{pmatrix}.

Write R2=(uvwu)R_2=\begin{pmatrix}u&v\\w&u\end{pmatrix}; its two diagonal entries are equal because R2R_2 is nilpotent and therefore has trace zero. The condition tr⁡(R1R2)=0\operatorname{tr}(R_1R_2)=0 gives w=0w=0, while det⁡R2=u2+vw=0\det R_2=u^2+vw=0 gives u=0u=0. Thus R2R_2 is a nonzero scalar multiple of R1R_1, and the result follows.

An EA-equivalent bivariate form

In this section, we show that the functions from F2F_2 and F3F_3 in Conjecture 1 are EA-equivalent to bivariate functions.

For a column X=(x,y)T∈K2X=(x,y)^{\mathsf{T}} \in K^2, define

M=(0111),qr(X)=det⁡(X,MX2r).(5)M=\begin{pmatrix}0&1\\1&1\end{pmatrix},\qquad q_r(X)=\det(X,MX^{2^r}). \tag*{(5)}

Then

qr(x,y)=x2r+1+xy2r+y2r+1.(6)q_r(x,y)=x^{2^r+1}+xy^{2^r}+y^{2^r+1}. \tag*{(6)}

Lemma 3. For e∈F2e \in\mathbb{F}_2, define Ge:K2→K2G_e:K^2\to K^2 by

Ge(x,y)=(qs(x,y)+ts(xy)+eTr⁡1m(xy)q1(x,y)+xy+Tr⁡1m(xy)).(7)G_e(x,y)=\begin{pmatrix} q_s(x,y)+t_s(xy)+e\operatorname{Tr}_1^m(xy)\\ q_1(x,y)+xy+\operatorname{Tr}_1^m(xy) \end{pmatrix}. \tag*{(7)}

Then

F3∼EAG0,F2∼EAG1.(8)F_3\sim_{\mathrm{EA}}G_0,\qquad F_2\sim_{\mathrm{EA}}G_1. \tag*{(8)}

Proof. Write the input of LL as Z=x+βyZ=x+\beta y, where x,y∈Kx,y\in K. Since m=2s+1m=2s+1, we have (m−2)s≡(−2)s≡1−m≡1(modm)(m-2)s\equiv(-2)s\equiv1-m\equiv1\pmod m; hence i≡s(modm)i\equiv s\pmod m. Moreover, ii is odd because it is the inverse of the odd integer m−2m-2 modulo 2m2m. Therefore,

Z2i=xσ+β2iyσ.Z^{2^i}=x^\sigma+\beta^{2^i}y^\sigma.

A direct calculation using β2+β+1=0\beta^2+\beta+1=0 gives

Z3+β2Z‾3=βq1(x,y),(9)Z^3+\beta^2\overline{Z}^3=\beta q_1(x,y), \tag*{(9)}
βZ2i+1+Z‾2i+1=β2qs(x,y),(10)\beta Z^{2^{i+1}}+\overline{Z}^{2^{i+1}}=\beta^2q_s(x,y), \tag*{(10)}
N(Z)=x2+xy+y2.(11)N(Z)=x^2+xy+y^2. \tag*{(11)}

For every jj, the difference

N(Z)2j−(xy)2j=x2j+1+y2j+1.N(Z)^{2^j}-(xy)^{2^j}=x^{2^{j+1}}+y^{2^{j+1}}.

is an F2\mathbb{F}_2-linear function of (x,y)(x,y) and can be removed by an EA transformation. Put z=xyz=xy. Modulo such linear terms, the perturbation in F3F_3 is

β2z+∑j=1s−1z2j+β∑j=sm−1z2j.\beta^2z+\sum_{j=1}^{s-1}z^{2^j}+\beta\sum_{j=s}^{m-1}z^{2^j}.

Apply the invertible output map

u+βv⟼(u,u+v).u+\beta v\longmapsto(u,u+v).

By (10)–(12), the BHK component B(z)B(z) becomes (qs,q1)(q_s,q_1), and the displayed perturbation becomes

(∑j=0s−1z2j,∑j=1m−1z2j)=(ts(z),z+Tr⁡1m(z)).\left(\sum_{j=0}^{s-1}z^{2^j},\sum_{j=1}^{m-1}z^{2^j}\right)=\left(t_s(z),z+\operatorname{Tr}_1^m(z)\right).

This proves F3∼EAG0F_3\sim_{\mathrm{EA}}G_0. The difference between the two perturbations satisfies

F2+F3=β2Tr⁡1m(N(Z)).F_2+F_3=\beta^2\operatorname{Tr}_1^m(N(Z)).

Under the same output map, this adds (Tr⁡1m(N(Z)),0)(\operatorname{Tr}_1^m(N(Z)),0). Moreover,

Tr⁡1m(N(Z))=Tr⁡1m(x)+Tr⁡1m(y)+Tr⁡1m(xy),\operatorname{Tr}_1^m(N(Z))=\operatorname{Tr}_1^m(x)+\operatorname{Tr}_1^m(y)+\operatorname{Tr}_1^m(xy),

the first two terms are linear and can again be removed. Thus F2∼EAG1F_2\sim_{\mathrm{EA}}G_1.

Let A,X∈K2A,X\in K^2 be two columns, put P=(A X)P=(A\ X) and T=det⁡PT=\det P. If T≠0T\ne0, then P∈GL(2,K)P\in\mathrm{GL}(2,K). From (6),

DAqr(X)=Ttr⁡(P−1MP2r).(12)D_{A}q_r(X)=T\operatorname{tr}\left(P^{-1}MP^{2^r}\right). \tag*{(12)}

Indeed, if

P−1MP2r=(abcd),P^{-1}MP^{2^r}=\begin{pmatrix}a&b\\c&d\end{pmatrix},

then

MA2r=aA+cX,MX2r=bA+dX,MA^{2^r}=aA+cX,\qquad MX^{2^r}=bA+dX,

and the polar part of qrq_r is (a+d)T(a+d)T. The polar parts of xyxy, Tr⁡1m(xy)\operatorname{Tr}_1^m(xy), and ts(xy)t_s(xy) are TT, Tr⁡1m(T)\operatorname{Tr}_1^m(T), and ts(T)t_s(T), respectively. Therefore, a nontrivial zero of a derivative of GeG_e with T≠0T\ne0 gives a matrix PP satisfying the following system of two equations:

tr⁡(P−1MPσ)=ts(T)+eTr⁡1m(T)T,(13)\operatorname{tr}\left(P^{-1}MP^\sigma\right)=\frac{t_s(T)+e\operatorname{Tr}_1^m(T)}{T}, \tag*{(13)}
tr⁡(P−1MP2)=1+Tr⁡1m(T)T.(14)\operatorname{tr}\left(P^{-1}MP^2\right)=1+\frac{\operatorname{Tr}_1^m(T)}{T}. \tag*{(14)}

The APN property

In this section, we prove the APN property of the functions from F2F_2 and F3F_3 in Conjecture 1. We first prove that (14)–(15) have no solution.

Lemma 4. For every e∈F2e\in\mathbb{F}_2, there is no matrix P∈GL(2,K)P\in\mathrm{GL}(2,K) satisfying (14)–(15).

Proof. Assume otherwise. Put

b=ts(T),δ=Tr⁡1m(T),b=t_s(T),\qquad\delta=\operatorname{Tr}_1^m(T),
S=P−1MPσ,U=P−1MP2,S=P^{-1}MP^\sigma,\qquad U=P^{-1}MP^2,

and

h=b+eδT,d=TσT.(15)h=\frac{b+e\delta}{T},\qquad d=\frac{T^\sigma}{T}. \tag*{(15)}

Thus tr⁡S=h\operatorname{tr}S=h and det⁡S=d\det S=d.

Since σ2=2m−1\sigma^2=2^{m-1} as an automorphism of KK, M3=IM^3=I, and P2σ2=PP^{2\sigma^2}=P, we have

SSσ=P−1M2Pσ2,Uσ2=P−σ2MP2σ2,SS^\sigma=P^{-1}M^2P^{\sigma^2},\qquad U^{\sigma^2}=P^{-\sigma^2}MP^{2\sigma^2},

and hence

(SSσ)Uσ2=I.(16)(SS^\sigma)U^{\sigma^2}=I. \tag*{(16)}

For every invertible 2×22 \times2 matrix VV, tr⁡(V−1)=tr⁡(V)/det⁡V\operatorname{tr}(V^{-1}) = \operatorname{tr}(V)/\det V. By using (14), (16), and (Tσ2)2=T(T^{\sigma^2})^2 = T, we get

tr⁡(SSσ)=det⁡(SSσ)(tr⁡U)σ2=Tσ2+δT.(17)\operatorname{tr}(SS^\sigma) = \det(SS^\sigma)(\operatorname{tr} U)^{\sigma^2} = \frac{T^{\sigma^2}+\delta}{T}. \tag*{(17)}

Here we used det⁡(SSσ)=ddσ=Tσ2/T\det(SS^\sigma) = d d^\sigma= T^{\sigma^2}/T and (tr⁡U)σ2=1+δ/Tσ2(\operatorname{tr} U)^{\sigma^2} = 1 + \delta/T^{\sigma^2}. On the other hand, combining (17) with (3) and (15), we obtain

tr⁡(SSσ)=dhσ+h=bσ+bT=Tσ2+δT.(18)\operatorname{tr}(SS^\sigma) = d h^\sigma+ h = \frac{b^\sigma+b}{T} = \frac{T^{\sigma^2}+\delta}{T}. \tag*{(18)}

The product

Nσ(S)=SSσ⋯Sσm−1=P−1MmP(19)N_\sigma(S) = SS^\sigma\cdots S^{\sigma^{m-1}} = P^{-1}M^mP \tag*{(19)}

is obtained by using Sσj=P−σjMPσj+1S^{\sigma^j} = P^{-\sigma^j}MP^{\sigma^{j+1}} and cancelling all intermediate factors. Since 3∤m3 \nmid m, MmM^m is MM or M2M^2. Hence the matrix in (19) has characteristic polynomial

X2+X+1.(20)X^2 + X + 1. \tag*{(20)}

Because mm is odd, (20) is irreducible over KK. In particular, Nσ(S)N_\sigma(S) has no one-dimensional invariant subspace over KK.

We divide the remainder of the proof into two cases.

Case 1: h≠0h \ne0.

Put c=b+eδc = b + e\delta and u=T/cu = T/c. From c2+c=Tσ+Tc^2 + c = T^\sigma+ T, we obtain

dh2=TTσc2=T+u+u2,Tr⁡1m(dh2)=δ.(21)\frac{d}{h^2} = \frac{TT^\sigma}{c^2} = T + u + u^2,\qquad\operatorname{Tr}_1^m\left(\frac{d}{h^2}\right) = \delta. \tag*{(21)}

After substituting X=hYX = hY, the equation X2+hX+d=0X^2 + hX + d = 0 becomes Y2+Y=d/h2Y^2 + Y = d/h^2. The image of Y↦Y2+YY \mapsto Y^2 + Y on KK is precisely the absolute-trace-zero subspace. Thus, by (21), the polynomial X2+hX+dX^2 + hX + d splits over KK if and only if δ=0\delta= 0. Let EE be its splitting field. Choose v∈Ev \in E satisfying v2+v=Tv^2 + v = T. Since tr⁡s(v2+v)=vσ+v\operatorname{tr}_s(v^2 + v) = v^\sigma+ v, we have vσ+v=bv^\sigma+ v = b. Set

w=u+v,ℓ=hw,ℓ′=ℓ+h.w = u + v,\qquad\ell= hw,\qquad\ell' = \ell+ h.

By (21), ℓ\ell and ℓ′\ell' are the two roots of X2+hX+dX^2 + hX + d.

Let

A0=ℓℓσ+ℓ′ℓ′σ,B0=ℓℓ′σ+ℓ′ℓσ.A_0 = \ell\ell^\sigma+ \ell'\ell'^\sigma,\qquad B_0 = \ell\ell'^\sigma+ \ell'\ell^\sigma.

Then A0+B0=hhσA_0 + B_0 = h h^\sigma. Moreover,

dhσ+h=A0+eδhhσ.(22)d h^\sigma+ h = A_0 + e\delta h h^\sigma. \tag*{(22)}

Indeed,

dhσ+h+A0hhσ=w+wσ+1+du+uσ=u+b+1+du=T+Tσc+b+1=eδ.\frac{d h^\sigma+ h + A_0}{h h^\sigma} = w + w^\sigma+ 1 + du + u^\sigma = u + b + 1 + du = \frac{T+T^\sigma}{c} + b + 1 = e\delta.

Let Q∈GL⁡(2,E)Q \in\operatorname{GL}(2,E) be an eigenvector matrix of SS, and write

S=Qdiag⁡(ℓ,ℓ′)Q−1,C=Q−1Qσ=(αγ0γ1ϵ).S = Q\operatorname{diag}(\ell,\ell')Q^{-1},\qquad C = Q^{-1}Q^\sigma= \begin{pmatrix} \alpha& \gamma_0\\ \gamma_1 & \epsilon \end{pmatrix}.

Put Δ=αϵ+γ0γ1\Delta= \alpha\epsilon+ \gamma_0\gamma_1. A direct multiplication gives

tr⁡(SSσ)=A0+γ0γ1Δ(A0+B0).(23)\operatorname{tr}(SS^\sigma) = A_0 + \frac{\gamma_0\gamma_1}{\Delta}(A_0+B_0). \tag*{(23)}

Comparing (18), (22), and (23), we obtain

γ0γ1Δ=ϵδ.(24)\frac{\gamma_0\gamma_1}{\Delta}=\epsilon\delta. \tag*{(24)}

Subcase 1.1: δ=0\delta=0. Both eigenvalues and eigenlines of SS are defined over KK. Equation (24) shows that CC is upper or lower triangular. Hence at least one eigenline is stable under σ\sigma. The semilinear map

Φ(z)=Szσ(25)\Phi(z)=Sz^\sigma \tag*{(25)}

preserves this KK-line. Its mm-th iterate, whose matrix is Nσ(S)N_\sigma(S), preserves the same line, contradicting (20)–(21).

Subcase 1.2: δ=1\delta=1. Then E=Fq2E=\mathbb{F}_{q^2}, where q=2mq=2^m, and the qq-Frobenius interchanges the two eigenlines. Choose the two columns of QQ as a conjugate pair. Then

Qq=QJ,J=(0110).Q^q=QJ,\qquad J=\begin{pmatrix}0&1\\1&0\end{pmatrix}.

Since the qq- and σ\sigma-Frobenius maps commute, we have JCq=CJJC^q=CJ. Thus

αq=ϵ,γ0q=γ1.(26)\alpha^q=\epsilon,\qquad\gamma_0^q=\gamma_1. \tag*{(26)}

Subcase 1.2.1: e=0e=0. By (24) and (26), γ0=γ1=0\gamma_0=\gamma_1=0. Thus both eigenlines are stable under σ\sigma. If ss is odd, Lemma 1 and the elementary fixed-line observation imply that both lines are defined over F2\mathbb{F}_2. This contradicts the irreducibility of X2+hX+dX^2+hX+d over KK: a KK-rational eigenline of the matrix S∈GL⁡(2,K)S\in\operatorname{GL}(2,K) has an eigenvalue in KK.

Let ss be even. Since Tr⁡1m(T+1)=δ+Tr⁡1m(1)=0\operatorname{Tr}_1^m(T+1)=\delta+\operatorname{Tr}_1^m(1)=0, choose a∈Ka\in K satisfying a2+a=T+1a^2+a=T+1. Let ω∈F4∖F2\omega\in\mathbb{F}_4\setminus\mathbb{F}_2 and put ρ=a+ω\rho=a+\omega. Then

T=ρρq,ωσ=ω,b=ts(T)=aσ+a.T=\rho\rho^q,\qquad\omega^\sigma=\omega,\qquad b=t_s(T)=a^\sigma+a.

Consequently,

λ=ρσρ(27)\lambda=\frac{\rho^\sigma}{\rho} \tag*{(27)}

satisfies

λ+λq=ρσρq+ρσqρT=aσ+aT=h,λλq=TσT=d.\lambda+\lambda^q=\frac{\rho^\sigma\rho^q+\rho^{\sigma q}\rho}{T}=\frac{a^\sigma+a}{T}=h,\qquad\lambda\lambda^q=\frac{T^\sigma}{T}=d.

Hence it is one of ℓ,ℓ′\ell,\ell'. The product of its σ\sigma-conjugates is

λλσ⋯λσm−1=ρσmρ=1\lambda\lambda^\sigma\cdots\lambda^{\sigma^{m-1}}=\frac{\rho^{\sigma^m}}{\rho}=1

by (4); the same holds for λq\lambda^q. The two eigenlines have vectors over F4=Fix⁡E(σ)\mathbb{F}_4=\operatorname{Fix}_E(\sigma). Using these vectors as the columns of QQ gives Qσ=QQ^\sigma=Q, and therefore

Q−1Nσ(S)Q=diag⁡(∏j=0m−1λσj,∏j=0m−1(λq)σj)=I.Q^{-1}N_\sigma(S)Q=\operatorname{diag}\left(\prod_{j=0}^{m-1}\lambda^{\sigma^j},\prod_{j=0}^{m-1}(\lambda^q)^{\sigma^j}\right)=I.

This contradicts (20)–(21).

Subcase 1.2.2: e=1e=1. Equation (24) gives γ0γ1=Δ=αϵ+γ0γ1\gamma_0\gamma_1=\Delta=\alpha\epsilon+\gamma_0\gamma_1, so αϵ=0\alpha\epsilon=0. By (26), α=ϵ=0\alpha=\epsilon=0. Therefore, σ\sigma interchanges the two eigenlines. If ss is even, the automorphism qσ−1=2s+1q\sigma^{-1}=2^{s+1} fixes both lines. Its fixed field is F2\mathbb{F}_2 by Lemma 1, so the two lines are defined over KK, a contradiction.

It remains to consider odd ss. Choose a∈Ka\in K satisfying a2+a=T+1a^2+a=T+1, and put ρ=a+ω\rho=a+\omega, where ω∈F4∖F2\omega\in\mathbb{F}_4\setminus\mathbb{F}_2. Now ωσ=ω2\omega^\sigma=\omega^2 and

b=ts(T)=aσ+a+1,c=b+1=aσ+a.b=t_s(T)=a^\sigma+a+1,\qquad c=b+1=a^\sigma+a.

The element

λ=ρσρq(28)\lambda=\frac{\rho^\sigma}{\rho^q} \tag*{(28)}

satisfies

λ+λq=ρσρ+ρσqρqT=aσ+aT=h,λλq=TσT=d.\lambda+\lambda^{q}=\frac{\rho^{\sigma}\rho+\rho^{\sigma q}\rho^{q}}{T}=\frac{a^{\sigma}+a}{T}=h,\qquad\lambda\lambda^{q}=\frac{T^{\sigma}}{T}=d.

Thus λ,λq\lambda,\lambda^{q} are the eigenvalues of SS. The two eigenlines are fixed by qσ−1q\sigma^{-1}, whose fixed field is F4\mathbb{F}_{4}. Choose their eigenvector matrix Q∈GL⁡(2,F4)Q\in\operatorname{GL}(2,\mathbb{F}_{4}) as follows: choose a nonzero vector on the first line and take its qq-th power as the second column. Then Qq=QJQ^{q}=QJ. Since both mm and ss are odd, the qq- and σ\sigma-Frobenius maps act as squaring on F4\mathbb{F}_{4}, and hence Qσ=QJQ^{\sigma}=QJ as well. In the QQ-coordinates, the map (25) has matrix

A=diag⁡(λ,λq)J.A=\operatorname{diag}(\lambda,\lambda^{q})J.

The product R=AAσ⋯Aσm−1R=AA^{\sigma}\cdots A^{\sigma^{m-1}} is anti-diagonal. Its upper-right entry is

Λ=∏0≤j<mj evenρσj+1ρqσj∏0≤j<mj oddρqσj+1ρσj.(29)\Lambda=\prod_{\substack{0\leq j<m\\j\ \mathrm{even}}}\frac{\rho^{\sigma^{j+1}}}{\rho^{q\sigma^{j}}}\prod_{\substack{0\leq j<m\\j\ \mathrm{odd}}}\frac{\rho^{q\sigma^{j+1}}}{\rho^{\sigma^{j}}}. \tag*{(29)}

By (4), q=σmq=\sigma^{m} on EE. The numerator and denominator in (29) contain exactly the same conjugates

ρσ,ρσ3,…,ρσ2m−1,\rho^{\sigma},\rho^{\sigma^{3}},\ldots,\rho^{\sigma^{2m-1}},

because the numerator exponents are

{j+1:j even}∪{m+j+1:j odd},\{j+1:j\ \mathrm{even}\}\cup\{m+j+1:j\ \mathrm{odd}\},

whereas the denominator exponents are

{m+j:j even}∪{j:j odd};\{m+j:j\ \mathrm{even}\}\cup\{j:j\ \mathrm{odd}\};

where 0≤j<m0\leq j<m in all four sets. Both sets are exactly the odd residues modulo 2m2m. Hence Λ=1\Lambda=1. The lower-left entry is Λq=1\Lambda^{q}=1, and consequently R=JR=J. For completeness, if z=Qyz=Qy, then the two descriptions of the mm-th iterate of (25) give

Φm(Qy)=QRyq=Nσ(S)Qqyq.\Phi^{m}(Qy)=QRy^{q}=N_{\sigma}(S)Q^{q}y^{q}.

Since Qq=QJQ^{q}=QJ, it follows that

Q−1Nσ(S)Q=RJ=I,Q^{-1}N_{\sigma}(S)Q=RJ=I,

contradicting (19).

Case 2: h=0h=0. Then b+eδ=0b+e\delta=0. By (3), Tσ=TT^{\sigma}=T. Since Fix⁡K(σ)=F2\operatorname{Fix}_{K}(\sigma)=\mathbb{F}_{2} and T≠0T\ne0, we have T=1T=1 and d=1d=1. The characteristic polynomial of SS is (X+1)2(X+1)^{2}, so write S=I+RS=I+R, where R2=0R^{2}=0. If R=0R=0, the left-hand side of (19) is II, which is impossible. Hence RR is a nonzero rank-one nilpotent matrix. From (18),

0=tr⁡(SSσ)=tr⁡(RRσ).0=\operatorname{tr}(SS^{\sigma})=\operatorname{tr}(RR^{\sigma}).

Indeed, after expanding (I+R)(I+Rσ)(I+R)(I+R^{\sigma}), the traces of II, RR, and RσR^{\sigma} all vanish in characteristic two. By Lemma 2, RR and RσR^{\sigma} have the same kernel. Since ker⁡Rσ=(ker⁡R)σ\ker R^{\sigma}=(\ker R)^{\sigma}, the KK-line ker⁡R\ker R is stable under σ\sigma. It is preserved by (25), and consequently by its mm-th iterate Nσ(S)N_{\sigma}(S). 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 F2F_{2} and F3F_{3}.

Theorem 1. Let m≥5m\geq5 be odd with 3∤m3\nmid m. The two functions F2F_{2} and F3F_{3} defined in (1)–(2) are APN over F22m\mathbb{F}_{2^{2m}}.

Proof. By Lemma 3, it is enough to prove that Ge\mathcal{G}_{e} is APN for e=0,1e=0,1. Let A=(a,b)T∈K2∖{0}A=(a,b)^{\mathsf{T}}\in K^{2}\setminus\{0\} be a derivative direction and let X=(x,y)TX=(x,y)^{\mathsf{T}} be in the kernel of its symmetric derivative. Put T=det⁡(A X)T=\det(A\ X).

If T≠0T\ne0, equations (12)–(14) give a matrix P=(A X)∈GL⁡(2,K)P=(A\ X)\in\operatorname{GL}(2,K) satisfying (13)–(14), which is impossible by Lemma 4.

Now let T=0T=0. Then X=μAX=\mu A for some μ∈K\mu\in K. The second coordinate of the derivative of Ge\mathcal{G}_{e} is

(μ2+μ)q1(A).(30)(\mu^{2}+\mu)q_{1}(A). \tag*{(30)}

We claim that q1(A)≠0q_1(A) \ne0. If b=0b=0, this is clear. If b≠0b \ne0 and q1(A)=0q_1(A)=0, then a/ba/b is a root of Z3+Z+1Z^3+Z+1. This polynomial is irreducible over F2\mathbb{F}_2 and its roots belong to F8∖F2\mathbb{F}_8 \setminus\mathbb{F}_2. However,

K∩F8=F2gcd⁡(m,3)=F2,K \cap\mathbb{F}_8 = \mathbb{F}_{2^{\gcd(m,3)}} = \mathbb{F}_2,

which is a contradiction. Thus (31) vanishes only when μ∈F2\mu\in\mathbb{F}_2, and therefore X=0X=0 or X=AX=A.

We have proved that the kernel of every nonzero derivative is exactly {0,A}\{0,A\}. Hence G0G_0 and G1G_1 are APN. By (8), the same is true for F3F_3 and F2F_2, respectively.

Conclusion

We have proved that the two conjectured families F2F_2 and F3F_3 are APN over F22m\mathbb{F}_{2^{2m}} for every odd m≥5m \ge5 with 3∤m3 \nmid m. The main step is the EA-equivalent form (7), which transforms every possible nontrivial derivative zero with T≠0T \ne0 into the two matrix equations (14)–(15). The local identity (18) controls the Frobenius action on the two eigenlines of SS, while the global product (19) has no invariant line over KK. The resulting contradiction excludes all nontrivial derivative zeros and completes the proof of Conjecture 1 in [5].

References

  1. [1]E. Biham and A. Shamir, “Differential cryptanalysis of DES-like cryptosystems,” J. Cryptology, vol. 4, no. 1, pp. 3–72, 1991.
  2. [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. [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. [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. [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. [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. [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. [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. [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.

Paper details

vlnc:W_aqzy9bu3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents