betaFeedback

WorksMathematics

Explicit permutations of (Z/4Z)m(\mathbb{Z}/4\mathbb{Z})^m with uniformly bounded differential uniformity

Abstract

Symmetric primitives over Galois rings need nonlinear components whose differentials with respect to ring addition are controlled. Let R=GR(4,m)R=\mathrm{GR}(4,m) and q=2mq=2^m, so that (R,+)≅(Z/4Z)m(R,+)\cong(\mathbb{Z}/4\mathbb{Z})^m has order N=q2N=q^2. For every m≥1m\ge1 we construct an explicit permutation GcG_c of RR all of whose differentials with a nonzero input difference have probability at most 36/N36/N, whereas every permutation polynomial of RR has such a differential of probability at least 2/N2/\sqrt{N} (Ronjom–Sandrib). The bound holds for the fixed permutation itself, not on average over keys. Equivalently, Δ(Gc)≤36Δ(G_c)\le36 against Δ≥2NΔ\ge2\sqrt{N} for permutation polynomials; since every permutation has Δ≥2Δ\ge2, the least differential uniformity of a permutation of (Z/4Z)m(\mathbb{Z}/4\mathbb{Z})^m lies between 22 and 3636 for every mm. In Teichmuller digits (a,b)∈Fq2(a,b)\in\mathbb{F}_q^2 and for c∈Fqc\in\mathbb{F}_q of absolute trace 11, Gc(a,b)=(L,(L2+L+c)a)G_c(a,b)=(L,(L^2+L+c)a) with L=(a2+a+c)bL=(a^2+a+c)b. The map is Fc∘J∘FcF_c\circ J\circ F_c, where Fc(a,b)=(a,(a2+a+c)b)F_c(a,b)=(a,(a^2+a+c)b) is induced by a polynomial over RR and JJ exchanges the digits: a single digit exchange between two polynomial layers yields a bound independent of mm. The proof reduces the difference equations, in each of three types of directions, to one-variable polynomials whose degrees do not depend on mm. For general maps F∘J∘FF\circ J\circ F with F(a,b)=(p(a),h(a)+d(a)b)F(a,b)=(p(a),h(a)+d(a)b), where p,d,hp,d,h have degrees bounded independently of mm, p′≠0p'\ne0 and dd has no zeros, a Jacobian identity in characteristic 22 bounds the differentials with nonzero low input and output differences independently of mm; the remaining directions need a separate argument, which we give for an explicit family (Δ≤440Δ\le440, resp. 510510, for odd mm).

Introduction

For a map GG on a finite abelian group (R,+)(R,+) put δG(α,β)=#{x∈R:G(x+α)−G(x)=β}\delta_G(\alpha,\beta)=\#\{x \in R:G(x+\alpha)-G(x)=\beta\} and Δ(G)=max⁡α≠0,βδG(α,β)\Delta(G)=\max_{\alpha\ne0,\beta}\delta_G(\alpha,\beta). Over F2n\mathbb{F}_2^n the group is elementary abelian, and power maps such as x3x^3 are permutations with Δ=2\Delta=2 for every odd nn. Symmetric primitives over the integer rings Z2k\mathbb{Z}_{2^k} and over Galois rings, studied for use in multiparty computation and homomorphic encryption [5, 3], raise the same question for groups that are not elementary abelian. The simplest family of this kind is (Z/4Z)m(\mathbb{Z}/4\mathbb{Z})^m, the additive group of R=GR⁡(4,m)R=\operatorname{GR}(4,m), and there polynomial constructions face a restriction: Rønjom and Sandrib proved that every permutation polynomial of GR⁡(pk,m)\operatorname{GR}(p^k,m) has Δ≥2pm(k−1)\Delta\ge2p^{m(k-1)} [1 Theorem 3] (every polynomial function has Δ≥pm(k−1)\Delta\ge p^{m(k-1)} [1 Proposition 2]); for GR⁡(4,m)\operatorname{GR}(4,m) this is Δ≥2q=2∣R∣\Delta\ge2q=2\sqrt{|R|}, so a permutation with smaller Δ\Delta cannot be a polynomial function. Splitting an element into digits, applying maps to the digits and recombining is an established design strategy. It appears in the “cut-and-sew” S-boxes over Zq\mathbb{Z}_q for composite qq [5 §4.3], where for q=p2q=p^2 the two digits are also exchanged; in the Kintsugi strategy over prime fields [6 §2]; and as “digit manipulation” over Zpn\mathbb{Z}_{p^n} in Beyne, Grassi, Øygarden, Richterová and Sandrib [3 §9]. These constructions act on cyclic groups Zq\mathbb{Z}_q or on Fp\mathbb{F}_p. Here we consider the groups (Z/4Z)m(\mathbb{Z}/4\mathbb{Z})^m, noncyclic for m>1m>1, and give an explicit family whose differential uniformity is bounded independently of mm. Rønjom and Sandrib also classify the table-defined (non-polynomial) permutations of GR⁡(4,2)\operatorname{GR}(4,2) with Δ=2\Delta=2 [1 §5]; no family covering all mm is given there. On cyclic groups Zn\mathbb{Z}_n several infinite families of permutations with Δ=2\Delta=2 are known (see [2] and the references there), but Z4m\mathbb{Z}_{4^m} and (Z/4Z)m(\mathbb{Z}/4\mathbb{Z})^m are different groups for m>1m>1. Permutation polynomials are subject to the lower bound Δ≥2∣R∣\Delta\ge2\sqrt{|R|} [1], and the one-sided digit-exchange maps J∘FJ \circ F of [4] attain Δ=q=∣R∣\Delta=q=\sqrt{|R|}, which is optimal within that class (Theorem 3.1). The family constructed here has Δ≤36\Delta\le36 for every mm, so the optimal order is constant.

Theorem 1.1. Let m≥1m \ge1, q=2mq=2^m, and c∈Fqc \in\mathbb{F}_q with Tr⁡Fq/F2(c)=1\operatorname{Tr}_{\mathbb{F}_q/\mathbb{F}_2}(c)=1. In Teichmüller digits, the map Gc=Fc∘J∘FcG_c=F_c \circ J \circ F_c with Fc(a,b)=(a,D(a)b)F_c(a,b)=(a,D(a)b), D(x)=x2+x+cD(x)=x^2+x+c, J(a,b)=(b,a)J(a,b)=(b,a), is a permutation of GR⁡(4,m)\operatorname{GR}(4,m) and

Δ(Gc)≤36.\Delta(G_c) \le36.

Let DmD_m be the least Δ\Delta over all permutations of (Z/4Z)m(\mathbb{Z}/4\mathbb{Z})^m. Theorem 1.1 and Proposition 3.2 give 2≤Dm≤362 \le D_m \le36 for every mm, so Dm=Θ(1)D_m=\Theta(1), whereas every permutation polynomial has Δ≥2∣R∣\Delta\ge2\sqrt{|R|}. In terms of probabilities, with N=∣R∣=q2N=|R|=q^2, every differential of GcG_c with a nonzero input difference has probability at most 36/N36/N, which is of the optimal order N−1N^{-1}. For example, for m=8m=8 the ring RR has 65,536 elements (a 16-bit state): every permutation polynomial of RR has a differential of probability at least 512/65,536=1/128512/65,536=1/128, while every differential of GcG_c with a nonzero input difference has probability at most 36/65,53636/65,536, more than 14 times smaller. In the instances of Table 1 (m≤10m \le10) the exact values of Δ(Gc)\Delta(G_c) are at most 20. Since FcF_c is itself induced by a polynomial (§ 2.2), the polynomial lower bound is overcome by a single digit exchange between two polynomial layers. The proof (Section 4) is elementary, and the degrees it uses do not depend on mm.

Comparison. With Fp,d,h(a,b)=(p(a),h(a)+d(a)b)F_{p,d,h}(a,b)=(p(a),h(a)+d(a)b):

mapdigit systemΔ\Delta
permutation polynomial—≥2q\ge2q [1]
J∘FJ \circ F (output exchange only)any≥q\ge q (Thm. 3.1)
Fc∘J∘FcF_c \circ J \circ F_cTeichmüller≤36\le36 for all mm (Thm. 1.1)
F∘J∘FF \circ J \circ F, p=x3p=x^3, d=x4+x2+1d=x^4+x^2+1, h∈{0,x2,x3,x5}h \in\{0,x^2,x^3,x^5\}, mm oddTeichmüller≤440\le440, resp. 510 (Thm. 5.4)
literal exchange JJ (= F∘J∘FF \circ J \circ F with p=xp=x, d=1d=1, h=0h=0)Teichmüller=q=q (Remark 5.3)
literal exchange JJcoordinate=q2/2=q^2/2 (Prop. 6.2)
F∘J∘FF \circ J \circ F, 1-periodic h,dh,dcoordinate≥q/2\ge q/2 (Prop. 6.1)

Table 1.

The class J∘FJ \circ F in the second line contains the maps studied in [4] (coordinate digits, pp APN, dd affine), for which Δ=q\Delta=q is attained; Theorem 3.1 shows that qq cannot be improved within this class. Unlike [4], which also gives key-averaged and multi-round statements, we consider a single fixed permutation and all its differentials. For the families of Theorems 1.1 and 5.4, one more polynomial layer after the exchange removes the dependence on mm.

Scope. We do not determine DmD_m, and we do not consider other attacks (linear, integral, algebraic) or implementation cost. Open questions are collected in § 8.

Setting

Digits

2.12.1. R=GR⁡(4,m)=W2(Fq)R=\operatorname{GR}(4,m)=W_2(\mathbb{F}_q). Every x∈Rx\in R is uniquely x=T(a)+2T(b)x=T(a)+2T(b) with a,b∈Fqa,b\in\mathbb{F}_q, where TT is the Teichmüller lift; we write x=(a,b)x=(a,b). The identity T(a)+T(u)=T(a+u)+2T(au)T(a)+T(u)=T(a+u)+2T(\sqrt{au}) gives

(a,b)+(u,v)=(a+u,b+v+au),−(a,b)=(a,a+b),(1)(a,b)+(u,v)=(a+u,b+v+\sqrt{au}), \qquad-(a,b)=(a,a+b), \tag*{(1)}

hence

(y0,y1)−(z0,z1)=(y0+z0,y1+z0+z1+y0z0).(2)(y_0,y_1)-(z_0,z_1)=(y_0+z_0,y_1+z_0+z_1+\sqrt{y_0z_0}). \tag*{(2)}

The coordinate digit system fixes a basis e0=1,e1,…,em−1e_0 = 1, e_1, \ldots, e_{m-1} of Fq\mathbb{F}_q over F2\mathbb{F}_2 whose first vector is 11 (for definiteness, the polynomial basis 1,ω,…,ωm−11,\omega,\ldots,\omega^{m-1} of Fq=F2(ω)\mathbb{F}_q = \mathbb{F}_2(\omega)) and lifts coordinates to {0,1}⊂Z/4\{0,1\} \subset\mathbb{Z}/4. The resulting map depends on the basis; all statements below about this system are for a basis with e0=1e_0 = 1. Then (1) holds with the carry au\sqrt{au} replaced by the coordinatewise product a⊙ua \odot u.

We apply the same formulas in both digit systems; they give different permutations of RR. The change of digits has the form C(a,b)=(a,b+γ(a))C(a,b) = (a,b+\gamma(a)), under which Fp,d,hF_{p,d,h} becomes Fp,d,h′F_{p,d,h'} with h′(a)=h(a)+d(a)γ(a)+γ(p(a))h'(a) = h(a) + d(a)\gamma(a) + \gamma(p(a)), and CJC−1CJC^{-1} is in general not the literal exchange JJ.

The maps

For p,d,h∈Fq[x]p,d,h \in\mathbb{F}_q[x] with pp a permutation of Fq\mathbb{F}_q and dd without zeros in Fq\mathbb{F}_q, F=Fp,d,hF = F_{p,d,h} is a permutation of Fq2\mathbb{F}_q^2, hence of RR; so are J∘FJ \circ F and F∘J∘FF \circ J \circ F. Theorem 1.1 is the case p=xp = x, h=0h = 0, d=x2+x+cd = x^2 + x + c.

We call Fp,d,hF_{p,d,h} a polynomial layer because it is induced by a polynomial over RR. For F∈R[X]F \in R[X] with reduction F‾∈Fq[X]\overline{F} \in\mathbb{F}_q[X], the identity F(y+2z)=F(y)+2zF‾′(y)F(y + 2z) = F(y) + 2z\overline{F}'(y) shows that FF acts on digits as (a,b)↦(F‾(a),h0(a)+F‾′(a)b)(a,b) \mapsto(\overline{F}(a), h_0(a) + \overline{F}'(a)b), where h0(a)h_0(a) is the high digit of FF at (a,0)(a,0); conversely, every triple of functions p,d,hp,d,h arises in this way, by interpolation with the factor Xq−XX^q-X and a correction 2H^2\widehat{H} of the high digit. This is [4 Proposition “Coordinate form and realizability”], stated there for coordinate digits; the argument uses only that 2w∈R2w \in R depends on w mod 2w \bmod2 alone, and holds verbatim for Teichmüller digits. The exchange JJ is not of this form. Since every permutation polynomial of RR has Δ≥2q\Delta\ge2q [1], Theorem 1.1 shows that for m≥5m \ge5 the permutation GcG_c is not induced by any polynomial over RR.

Output exchange alone

Theorem 3.1. Let p,h:Fq→Fqp,h:\mathbb{F}_q \to\mathbb{F}_q be arbitrary and d:Fq→Fq×d:\mathbb{F}_q \to\mathbb{F}_q^\times. In either digit system, Δ(J∘Fp,d,h)≥q\Delta(J \circ F_{p,d,h}) \ge q.

Proof. Teichmüller digits: B=J∘FB = J \circ F is B(a,b)=(h(a)+d(a)b,p(a))B(a,b) = (h(a) + d(a)b,p(a)). Since ∣Fq×∣<q|\mathbb{F}_q^\times| < q, dd is not injective; choose a0a_0 and u≠0u \ne0 with d(a0+u)=d(a0)d(a_0+u) = d(a_0), and vv with h(a0+u)+h(a0)+d(a0)(v+a0u)=0h(a_0+u) + h(a_0) + d(a_0)(v+\sqrt{a_0u}) = 0. For x=(a0,b)x = (a_0,b) and α=(u,v)\alpha= (u,v) the low digits of B(x+α)B(x+\alpha) and B(x)B(x) coincide, so by (2) B(x+α)−B(x)=(0,p(a0+u)+p(a0))B(x+\alpha)-B(x) = (0,p(a_0+u)+p(a_0)) for all qq values of bb. The coordinate case is identical with a0⊙ua_0 \odot u in place of a0u\sqrt{a_0u} (for the maps of [4], Δ(B)=q\Delta(B)=q exactly). □

Proposition 3.2. Every map G:(Z/4Z)m→(Z/4Z)mG:(\mathbb{Z}/4\mathbb{Z})^m \to(\mathbb{Z}/4\mathbb{Z})^m, m≥1m \ge1, has Δ(G)≥2\Delta(G) \ge2. Consequently, for every mm, 2≤min⁡GΔ(G)≤362 \le\min_G \Delta(G) \le36, the minimum over all permutations.

Proof. Let α≠0\alpha\ne0 with 2α=02\alpha= 0 and put D(x)=G(x+α)−G(x)D(x) = G(x+\alpha)-G(x). Then D(x+α)=G(x)−G(x+α)=−D(x)D(x+\alpha)=G(x)-G(x+\alpha)=-D(x). If some xx has D(x)=βD(x)=\beta with 2β=02\beta=0, then D(x+α)=βD(x+\alpha)=\beta as well, so δG(α,β)≥2\delta_G(\alpha,\beta) \ge2. Otherwise DD misses the 2m≥22^m \ge2 elements of order at most 22, so DD is not surjective and some value is taken twice. □

For permutations the bound Δ≥2\Delta\ge2 is immediate in any finite group of order >2>2, since x↦G(x+α)−G(x)x \mapsto G(x+\alpha)-G(x) never takes the value 00; Proposition 3.2 extends it to arbitrary maps.

Proof of the main theorem

Permutation. The image of x↦x2+xx \mapsto x^2+x on Fq\mathbb{F}_q is the trace-zero hyperplane, so Tr⁡(c)=1\operatorname{Tr}(c)=1 gives D(a)≠0D(a) \ne0 for all aa; FcF_c multiplies bb by a nonzero scalar on each fibre and is bijective. Explicitly

Gc(a,b)=(L,D(L)a),L=D(a)b.G_c(a,b) = (L,D(L)a), \qquad L = D(a)b.

Difference equations. Fix α=(u,v)≠0\alpha=(u,v)\ne0 and β=(s,t)\beta=(s,t), and write a=A2a=A^2, u=U2u=U^2 (Frobenius is bijective on Fq\mathbb{F}_q, so AA runs over Fq\mathbb{F}_q and au=AU\sqrt{au}=AU). By (1), x+α=(a+u,b+v+AU)x+\alpha=(a+u,b+v+AU), so

L=D(a)b,L′=D(a+u)(b+v+AU)L = D(a)b,\qquad L' = D(a+u)(b+v+AU)

are the low digits of Gc(x)G_c(x) and Gc(x+α)G_c(x+\alpha). By (2), Gc(x+α)−Gc(x)=βG_c(x+\alpha)-G_c(x)=\beta is equivalent to

L′+L=s,(3)L' + L = s, \tag*{(3)}
t=D(L′)(a+u)+L+D(L)a+LL′.(4)t=D(L')(a+u)+L+D(L)a+\sqrt{LL'}. \tag*{(4)}

Given (3), D(L′)=D(L)+s2+sD(L')=D(L)+s^2+s and LL′=L2+sL=L+sL\sqrt{LL'}=\sqrt{L^2+sL}=L+\sqrt{sL}, so (4) becomes t=uD(L)+(s2+s)(a+u)+sLt=uD(L)+(s^2+s)(a+u)+\sqrt{sL}, and squaring (Frobenius is injective) gives the equivalent condition

u2(L4+L2+c2)+(s4+s2)(a2+u2)+sL+t2=0.(5)u^2(L^4+L^2+c^2)+(s^4+s^2)(a^2+u^2)+sL+t^2=0. \tag*{(5)}

We count pairs (A,b)∈Fq2(A,b)\in\mathbb{F}_q^2 satisfying (3) and (5); the map (A,b)↦x=(A2,b)(A,b)\mapsto x=(A^2,b) is a bijection.

*Case A: u∉{0,1}u\notin\{0,1\}. Put κ=u2+u≠0\kappa=u^2+u\ne0, so D(a+u)=D(a)+κD(a+u)=D(a)+\kappa. Then (3) reads κb+D(a+u)(v+AU)+s=0\kappa b+D(a+u)(v+AU)+s=0, which determines bb from AA, and

L=N(A)κ,N(A)=D(a)s+D(a)D(a+u)(v+AU),L=\frac{N(A)}{\kappa},\qquad N(A)=D(a)s+D(a)D(a+u)(v+AU),

a polynomial in AA of degree 9 with leading coefficient UU. Substituting into (5) and multiplying by κ4\kappa^4 gives

u2(N4+κ2N2+c2κ4)+(s4+s2)(A4+u2)κ4+sNκ3+t2κ4=0,u^2(N^4+\kappa^2N^2+c^2\kappa^4)+(s^4+s^2)(A^4+u^2)\kappa^4+sN\kappa^3+t^2\kappa^4=0,

a polynomial in AA of degree 36 with leading coefficient u2U4=U8≠0u^2U^4=U^8\ne0 (all other terms have degree at most 18). Hence at most 36 values of AA, each with one bb: δ≤36\delta\le36. This includes s=0s=0.

*Case B: u=1u=1. Then U=1U=1 and D(a+1)=D(a)D(a+1)=D(a), so (3) reads D(A2)(v+A)+s=0D(A^2)(v+A)+s=0, a monic polynomial of degree 5 in AA: at most 5 values. For each, (5) is a monic polynomial of degree 4 in LL, and b=L/D(a)b=L/D(a). Hence δ≤20\delta\le20.

*Case C: u=0u=0, v≠0v\ne0. Then (3) reads vD(a)=svD(a)=s; there is no solution unless s≠0s\ne0, and then D(a)=s/vD(a)=s/v has at most 2 roots aa. For each, (5) becomes (s4+s2)a2+sL+t2=0(s^4+s^2)a^2+sL+t^2=0, linear in LL with coefficient s≠0s\ne0. Hence δ≤2\delta\le2.

The three cases cover all α≠0\alpha\ne0, so Δ(Gc)≤36\Delta(G_c)\le36. □

Remark 4.1. The argument holds for all mm and uses neither an APN property nor intersection theory. The constant comes from Case A: the degree 36=4⋅936=4\cdot9 of u2N4u^2N^4. In the instances of Table 1 the observed values are at most 20 and are not monotone in mm (10 for m=5m=5, 9 for m=6m=6).

Remark 4.2 (Evaluation). On Teichmüller digits, GcG_c costs two general multiplications, two squarings and four additions in Fq\mathbb{F}_q; given the output (L,y)(L,y), the inverse a=y/D(L)a=y/D(L), b=L/D(a)b=L/D(a) costs two inversions, two multiplications and two squarings. Passing between x∈Rx\in R and its digits requires a=x mod 2a=x\bmod2 and T(a)T(a), i.e. mm squarings in RR (since T(a)=a~T(a)=\widetilde{a} for any lift a~\widetilde{a}). In settings where elements of RR are held as shares modulo 4, the reduction x mod 2x\bmod2 is a bit extraction whose cost depends on the protocol; we do not analyse it here.

A general method for FJF

For general (p,d,h)(p,d,h) the low-digit equation is no longer linear in bb, and a uniform bound needs an argument about common components. Let G=F∘J∘FG=F\circ J\circ F, α=(u,v)≠0\alpha=(u,v)\ne0, β=(s,t)\beta=(s,t), a=A2a=A^2, u=U2u=U^2, and

L=h(a)+d(a)b,L′=h(a+u)+d(a+u)(b+v+AU).L=h(a)+d(a)b,\qquad L'=h(a+u)+d(a+u)(b+v+AU).
Z0=p(L),Z1=h(L)+d(L)p(a),Y0=p(L′),Y1=h(L′)+d(L′)p(a+u).Z_0=p(L),\quad Z_1=h(L)+d(L)p(a),\qquad Y_0=p(L'),\quad Y_1=h(L')+d(L')p(a+u).

By (2), after squaring the high digit,

δG(α,β)≔#{(A,b)∈Fq2:E1=E2=0},E1=Y0+Z0+s,E2=(Y1+Z0+Z1+t)2+Y0Z0.(6)\delta_G(\alpha,\beta)\coloneqq\#\{(A,b)\in\mathbb{F}_q^2:E_1=E_2=0\},\qquad E_1=Y_0+Z_0+s,\qquad E_2=(Y_1+Z_0+Z_1+t)^2+Y_0Z_0. \tag*{(6)}

Lemma 5.1. Put Ψ=Y0+Z0\Psi=Y_0+Z_0 and Φ=(Y1+Z0+Z1)2+Y0Z0\Phi=(Y_1+Z_0+Z_1)^2+Y_0Z_0. Then det⁡(∂(Ψ,Φ)/∂(A,b))=Ψ⋅p′(L)p′(L′)⋅d(a)d(a+u)⋅U\det(\partial(\Psi,\Phi)/\partial(A,b))=\Psi\cdot p'(L)p'(L')\cdot d(a)d(a+u)\cdot U.

Proof. In characteristic 2 squares have zero derivative, so Φ\Phi may be replaced by Y0Z0Y_0Z_0. The pair (Ψ,Y0Z0)(\Psi,Y_0Z_0) consists of the elementary symmetric functions of (Z0,Y0)(Z_0,Y_0), with Jacobian Z0+Y0=ΨZ_0+Y_0=\Psi; next ∂(Z0,Y0)∂(L,L′)=p′(L)p′(L′)\frac{\partial(Z_0,Y_0)}{\partial(L,L')}=p'(L)p'(L'). Since LL involves AA only through a=A2a=A^2, ∂L∂A=0\frac{\partial L}{\partial A}=0, ∂L∂b=d(a)\frac{\partial L}{\partial b}=d(a), ∂L′∂b=d(a+u)\frac{\partial L'}{\partial b}=d(a+u), ∂L′∂A=d(a+u)U\frac{\partial L'}{\partial A}=d(a+u)U, so ∂(L,L′)∂(A,b)=d(a)d(a+u)U\frac{\partial(L,L')}{\partial(A,b)}=d(a)d(a+u)U.

Theorem 5.2. Let p,d,h∈Fq[x]p,d,h\in\mathbb{F}_q[x] with p′≠0p'\ne0 and dd without zeros in Fq\mathbb{F}_q, and let K=F‾2K=\overline{\mathbb{F}}_2. If u≠0u\ne0 and s≠0s\ne0, every common component of E1E_1 and E2E_2 in K2K^2 is a line A=c0A=c_0 with c0∉Fqc_0\notin\mathbb{F}_q, and δG(α,β)≤deg⁡E1⋅deg⁡E2\delta_G(\alpha,\beta)\le\deg E_1\cdot\deg E_2.

Proof. Let Γ\Gamma be an irreducible common component. On Γ\Gamma, Ψ≡s\Psi\equiv s and Φ≡t2\Phi\equiv t^2, so both differentials vanish on the tangent line at smooth points and the Jacobian of Lemma 5.1 vanishes on Γ\Gamma. As Ψ=s≠0\Psi=s\ne0 and U≠0U\ne0, Γ\Gamma lies in {p′(L)=0}\{p'(L)=0\}, {p′(L′)=0}\{p'(L')=0\}, {d(a)=0}\{d(a)=0\} or {d(a+u)=0}\{d(a+u)=0\}. The last two are unions of lines A=c0A=c_0 with c02c_0^2 or c02+uc_0^2+u a root of dd, so c0∉Fqc_0\notin\mathbb{F}_q.

Suppose p′(L)=0p'(L)=0 on Γ\Gamma, so L≡rL\equiv r for a root rr of p′p'. If Γ\Gamma is vertical, A≡c0A\equiv c_0 while bb varies along Γ\Gamma, so L=h(c02)+d(c02)b≡rL=h(c_0^2)+d(c_0^2)b\equiv r forces d(c02)=0d(c_0^2)=0 and c0∉Fqc_0\notin\mathbb{F}_q. If Γ\Gamma is not vertical, AA is transcendental over KK on Γ\Gamma and b=(r−h(A2))/d(A2)b=(r-h(A^2))/d(A^2), so the function field is K(Γ)=K(A)K(\Gamma)=K(A) and

L′∣Γ=E(A2)+Ud(A2+u)A,E∈K(A2).L'|_\Gamma=E(A^2)+Ud(A^2+u)A,\qquad E\in K(A^2).

Since K(A)=K(A2)⊕AK(A2)K(A)=K(A^2)\oplus AK(A^2) and Ud(A2+u)≠0Ud(A^2+u)\ne0, L′∣Γ∉KL'|_\Gamma\notin K; hence Ψ∣Γ=p(r)+p(L′∣Γ)\Psi|_\Gamma=p(r)+p(L'|_\Gamma) is not constant, contradicting Ψ≡s\Psi\equiv s. The case p′(L′)=0p'(L')=0 is symmetric: then L∣Γ=E′(A2)+Ud(A2)AL|_\Gamma=E'(A^2)+Ud(A^2)A with E′∈K(A2)E'\in K(A^2).

Thus C=gcd⁡(E1,E2)C=\gcd(E_1,E_2) is a product of vertical lines without Fq\mathbb{F}_q-points, every Fq\mathbb{F}_q-solution is an isolated point of V(E1/C)∩V(E2/C)V(E_1/C)\cap V(E_2/C), and affine Bézout gives the bound.

The second-stage high digit enters E2E_2 only inside the square, so Theorem 5.2 holds for every hh. The bound depends on mm only through the degrees of p,d,hp,d,h, and is uniform in mm when these degrees are bounded.

Remark 5.3. Theorem 5.2 bounds δG(α,β)\delta_G(\alpha,\beta) only for u≠0u\ne0, s≠0s\ne0, and assumes p′≠0p'\ne0. The directions with u=0u=0 or s=0s=0 need a separate argument, and without one the differential uniformity of F∘J∘FF\circ J\circ F need not be bounded independently of mm. For example, p=xp=x, d=1d=1, h=0h=0 satisfy the hypotheses, but F=id⁡F=\operatorname{id} and F∘J∘F=JF\circ J\circ F=J. For α=(1,0)\alpha=(1,0) and x=(0,b)x=(0,b) we have x+α=(1,b)x+\alpha=(1,b), and by (2)

J(x+α)−J(x)=(b,1)−(b,0)=(0,1)for all b∈Fq,J(x+\alpha)-J(x)=(b,1)-(b,0)=(0,1)\qquad\text{for all }b\in\mathbb{F}_q,

so Δ(J)≥q\Delta(J)\ge q. In fact Δ(J)=q\Delta(J)=q: for α=(u,v)\alpha=(u,v) put s=v+aus=v+\sqrt{au}; then J(x+α)−J(x)=(s,u+bs)J(x+\alpha)-J(x)=(s,u+\sqrt{bs}). If u≠0u\ne0, the value ss determines aa; then tt determines bb when s≠0s\ne0, and when s=0s=0 we have t=ut=u with bb free. If u=0u=0, then s=v≠0s=v\ne0, tt determines bb, and aa is free. The same row α=(1,0)\alpha=(1,0) gives Δ≥q\Delta\ge q for the literal exchange in the coordinate system, but its exact value there is q2/2q^2/2 (Proposition 6.2); the two literal exchanges are different permutations of RR. In Theorem 1.1 and Theorem 5.2 the remaining directions are treated by hand.

Theorem 5.4. Let mm be odd, p=x3p=x^3, d=x4+x2+1d=x^4+x^2+1, h∈{0,x2,x3,x5}h\in\{0,x^2,x^3,x^5\}, and G=F∘J∘FG=F\circ J\circ F in Teichmüller digits. Then Δ(G)≤440\Delta(G)\le440 for h∈{0,x2,x3}h\in\{0,x^2,x^3\} and Δ(G)≤510\Delta(G)\le510 for h=x5h=x^5.

Proof. For mm odd, pp is bijective and d=(x2+x+1)2d=(x^2+x+1)^2 has no zeros in Fq\mathbb{F}_q.

u≠0u\ne0, s≠0s\ne0. By Theorem 5.2 the Fq\mathbb{F}_q-solutions are isolated roots in K2K^2 of a system whose supports are contained in the generic supports of (E1,E2)(E_1,E_2); the total degrees are at most (27,84)(27,84), resp. (29,98)(29,98), which already gives 22682268, resp. 28422842. These supports contain the origin and a pure power of each variable, so the pair is cornered, and it is nice (e.g. (A27+1,b8+1)(A^{27}+1,b^8+1), resp. (A29+1,b10+1)(A^{29}+1,b^{10}+1), has finitely many common roots). Rojas’ Affine Point Theorem II, valid over any algebraically closed field, bounds the number of isolated affine roots, with multiplicity, of every system with these supports by the mixed volume of the Newton polygons [7 Affine Point Theorem II]; this applies to each specialised system. The Newton polygons are

P1=conv⁡{(0,0),(27,0),(25,2),(16,3),(0,3)},P_1=\operatorname{conv}\{(0,0),(27,0),(25,2),(16,3),(0,3)\},
P2=conv⁡{(0,0),(84,0),(72,8),(0,8)}(MV=440),P_2=\operatorname{conv}\{(0,0),(84,0),(72,8),(0,8)\}\quad(\mathrm{MV}=440),
P1=conv⁡{(0,0),(29,0),(25,2),(16,3),(0,3)},P_1=\operatorname{conv}\{(0,0),(29,0),(25,2),(16,3),(0,3)\},
P2=conv⁡{(0,0),(98,0),(82,8),(64,10),(0,10)}(MV=510),P_2=\operatorname{conv}\{(0,0),(98,0),(82,8),(64,10),(0,10)\}\quad(\mathrm{MV}=510),

the second pair for h=x5h=x^5.

u≠0u\ne0, s=0s=0. On Fq\mathbb{F}_q-points p(L)=p(L′)p(L)=p(L') forces L=L′L=L', and then hh cancels: E2⟺t=ud(L)(a2+ua+u2)E_2\Longleftrightarrow t=ud(L)(a^2+ua+u^2). If u∉{0,1}u\notin\{0,1\}, put c1=u4+u2≠0c_1=u^4+u^2\ne0; then L=L′L=L' gives L=N/c1L=N/c_1 with N=d(a)h(a+u)+d(a+u)h(a)+d(a)d(a+u)(v+AU)N=d(a)h(a+u)+d(a+u)h(a)+d(a)d(a+u)(v+AU), of degree 17 in AA with leading coefficient UU, and the remaining equation is non-constant of degree 72 in AA; bb is then determined. If u=1u=1, then d(a+1)=d(a)d(a+1)=d(a), L′=LL'=L reads h(a+1)+h(a)+d(a)(v+A)=0h(a+1)+h(a)+d(a)(v+A)=0, whose odd part d(a)Ad(a)A is nonzero, so at most 9 values of AA; for each, d(L)=t/(a2+a+1)d(L)=t/(a^2+a+1) and L↦L4+L2L\mapsto L^4+L^2 is two-to-one. Hence δ≤72\delta\le72.

u=0u=0, v≠0v\ne0. Put w=vd(a)≠0w=vd(a)\ne0; in the coordinates (a,L)(a,L) (a bijection of Fq2\mathbb{F}_q^2), E1=wL2+w2L+w3+sE_1=wL^2+w^2L+w^3+s. If s=0s=0 then L3=(L+w)3L^3=(L+w)^3, impossible as cubing is bijective and w≠0w\ne0; so s≠0s\ne0. Reducing E2E_2 modulo E1E_1 over K(a)K(a) leaves a polynomial of degree 1 in LL with coefficient s2/w≠0s^2/w\ne0, so each aa gives at most one LL. Eliminating LL, Res⁡L(E1,E2)=d(a)2g(a)\operatorname{Res}_L(E_1,E_2)=d(a)^2g(a) (resp. d(a)4g(a)d(a)^4g(a) for h=x5h=x^5) with gg of degree 88 (resp. 96), nonzero leading coefficient for v≠0v\ne0, and only even powers of aa. As Fq\mathbb{F}_q is perfect, gg is the square of a polynomial of degree 44 (resp. 48), so δ≤44\delta\le44 (resp. 48). □

Remark 5.5. For the doubly exchanged maps J∘F∘J∘FJ\circ F\circ J\circ F of the same family, an analogous Jacobian identity holds, det⁡∂(Y1+Z1,Y1Z1)∂(A,b)=(Y1+Z1)g(L)g(L′)d(a)d(a+u)U\det\frac{\partial(Y_1+Z_1,Y_1Z_1)}{\partial(A,b)}=(Y_1+Z_1)g(L)g(L')d(a)d(a+u)U with g=h′+d′⋅pg=h'+d'\cdot p; whether these maps also have Δ\Delta bounded independently of mm is left open (§ 8).

The coordinate digit system

Proposition 6.1. In the coordinate digit system with e0=1e_0=1, if d(a+1)=d(a)d(a+1)=d(a) and h(a+1)=h(a)h(a+1)=h(a) for all aa (for instance h=0h=0, d=x4+x2+1d=x^4+x^2+1, or h=0h=0, d=x2+x+cd=x^2+x+c), then Δ(F∘J∘F)≥q/2\Delta(F\circ J\circ F)\ge q/2.

Proof. Take α=(1,0)\alpha=(1,0). Since 1=e01=e_0, the carry is a⊙1=a0a\mathbin{\odot}1=a_0, the first coordinate of aa. For the q/2q/2 values of aa with a0=0a_0=0 and all bb, x+α=(a+1,b)x+\alpha=(a+1,b) and L′=LL'=L, so G(x+α)−G(x)=(0,d(L)(p(a+1)+p(a)))G(x+\alpha)-G(x)=(0,d(L)(p(a+1)+p(a))). These q2/2q^2/2 inputs land in at most qq values of β\beta. □

For h=0h=0 and d=x4+x2+1d=x^4+x^2+1 (with p=x3p=x^3) the row α=(1,0)\alpha=(1,0) alone reaches 6, 22, 74 for m=3,5,7m=3,5,7. In general the kernel of a↦a⊙ua\mapsto a\mathbin{\odot}u has 2m−wt⁡(u)2^{m-\operatorname{wt}(u)} elements; in the Teichmüller system, by contrast, a↦aua\mapsto\sqrt{au} is injective for u≠0u\ne0. In the coordinate system the carry is a linearised polynomial of degree up to 2m−12^{m-1}, so the bounded-degree arguments above do not apply; whether F∘J∘FF\circ J\circ F has bounded Δ\Delta there for some hh that is not 1-periodic is open.

Proposition 6.2. In the coordinate digit system with e0=1e_0=1, the literal exchange Jσ(a,b)=(b,a)J_\sigma(a,b)=(b,a) has Δ(Jσ)=q2/2\Delta(J_\sigma)=q^2/2.

Proof. For α=(u,v)\alpha=(u,v) put s=v+a⊙us=v+a\mathbin{\odot}u. Then Jσ(x+α)−Jσ(x)=(s,u+b⊙s)J_\sigma(x+\alpha)-J_\sigma(x)=(s,u+b\mathbin{\odot}s). For a target (s,t)(s,t), the set of aa with a⊙u=s+va\mathbin{\odot}u=s+v has 0 or 2m−wt⁡(u)2^{m-\operatorname{wt}(u)} elements, and the set of bb with b⊙s=t+ub\mathbin{\odot}s=t+u has 0 or 2m−wt⁡(s)2^{m-\operatorname{wt}(s)} elements; hence δ(α,(s,t))≤22m−wt⁡(u)−wt⁡(s)\delta(\alpha,(s,t))\le2^{2m-\operatorname{wt}(u)-\operatorname{wt}(s)}. If u≠0u\ne0 then wt⁡(u)≥1\operatorname{wt}(u)\ge1; if u=0u=0 then s=v≠0s=v\ne0 and wt⁡(s)≥1\operatorname{wt}(s)\ge1. In both cases wt⁡(u)+wt⁡(s)≥1\operatorname{wt}(u)+\operatorname{wt}(s)\ge1, so δ≤q2/2\delta\le q^2/2. For α=(0,e0)\alpha=(0,e_0) and β=(e0,0)\beta=(e_0,0), every aa and every bb with b0=0b_0=0 is a solution, so the bound is attained. □

For m=1m=1 both literal exchanges have Δ=2\Delta=2; for m>1m>1 they differ.

Data

mm12345678910
qq2481632641282565121024
Δ(Gc)\Delta(G_c)244610912141620

Table 1 (PDF p. 7). Exact Δ(Gc)\Delta(G_c) for the tested parameters. Ring model: GR⁡(4,m)=Z4[X]/(f)\operatorname{GR}(4,m)=\mathbb{Z}_4[X]/(f) with ring addition only and digits recovered by table lookup, for all cc with Tr⁡(c)=1\operatorname{Tr}(c)=1 when m≤5m\leq5 and for two values of cc when m=6m=6. Digit formulas (1)–(2) (all N−1N-1 directions, with a coverage check): one value of cc for each m≤10m\leq10 and two for m=8m=8; these agree with the ring model for m≤6m\leq6. The field polynomial and the values of cc are listed in the supplementary material. For each mm, the value was the same for every tested cc.

Open problems

  1. Determine DmD_m. By Table 1 and [1 §5], D1=D2=2D_1=D_2=2. Are there permutations of (Z/4Z)m(\mathbb{Z}/4\mathbb{Z})^m with Δ=2\Delta=2 for every mm?

  1. How far can the constant 36 be lowered, for GcG_c or for other explicit families? For the tested parameters with m≤10m\leq10 (Table 1) the values of Δ(Gc)\Delta(G_c) are at most 20.

  1. For families (p,d,h)(p,d,h) of bounded degree, Theorem 5.2 bounds the differentials with u≠0u\ne0, s≠0s\ne0 independently of mm. For which such families are the remaining directions also bounded independently of mm? Does the same hold for the doubly exchanged maps J∘F∘J∘FJ\circ F\circ J\circ F?

  1. Can Δ(F∘J∘F)\Delta(F\circ J\circ F) remain bounded independently of mm in the coordinate digit system for some hh that is not 1-periodic (§ 6)?

Computational checks

The proofs above are complete without computation. The following scripts (supplementary material; Magma, and one C program with its runner) check the stated identities and degrees with assert, and recompute the table.

  • t4_v2_bounded36_symbolic.m: Theorem 1.1, from the unreduced equations (3)–(4): in Case A, NN of degree 9 with leading coefficient UU and the eliminated equation of degree 36 with leading coefficient U8/κ4U^{8}/\kappa^{4}; in Case B, the low equation monic of degree 5 in AA and the high equation monic of degree 4 in LL; in Case C, the low equation vD(a)+svD(a)+s and the high equation linear in LL with coefficient ss.

  • t5_ringmodel_v2.m (parameters mlo, mhi, cmax): Δ(Gc)\Delta(G_c) in the ring model, using ring addition only.

  • gc_ddt_v2.c with run_gc_v2.sh: Δ(Gc)\Delta(G_c) from the digit formulas, in parallel shards; the runner accepts a run only if every shard exits with status 0 and the recorded number and sum of directions of each shard equal those of its residue class α≡k(modK)\alpha\equiv k\pmod K.

  • c1_form1_assert.m: Lemma 5.1 as a polynomial identity (the family of Theorem 5.4 and random (p,d,h)(p,d,h)), and the mixed volumes 440 and 510.

  • t3_u0_form1_v2.m: the u=0u=0 elimination in Theorem 5.4 (exponent of the removed factor d(a)d(a), degree and leading coefficient of gg, even exponents, and the linear remainder).

  • t1_J_counterexample.m: Δ(J)=q\Delta(J)=q in the ring model for m≤5m\leq5 (Teichmüller digits, Remark 5.3); r05_t1_digit_swap.m: both literal exchanges for m≤5m\leq5, with Δ=q\Delta=q (Teichmüller) and Δ=q2/2\Delta=q^2/2 coordinate, Proposition 6.2.

  • t6_sigma_row.m: the row α=(1,0)\alpha=(1,0) in the coordinate system (Proposition 6.1).

The supplementary material contains the scripts, their raw outputs, a manifest with SHA-256 hashes, and instructions for reproducing each run. It is archived with the paper at https://doi.org/10.5281/zenodo.23875215 and at https://github.com/hirokifukui/z4m-bounded-differential-uniformity.

Funding

This research received no external funding.

Use of AI tools

The author used ChatGPT (OpenAI) and Claude (Anthropic) as research assistants, for exploring constructions and proof strategies, checking arguments, writing verification scripts, and drafting and editing the text. The author reviewed and revised all content and takes full responsibility for it. The numerical results were obtained with the supplied C and Magma programs.

References

Research Institute of Criminal Psychiatry / Sex Offender Medical Center, Tokyo, Japan; Department of Neuropsychiatry, Kyoto University, Kyoto, Japan

Email address: [email protected]

References

  1. [1]S. Røn­jom, A. Sandrib, On the differential uniformity of polynomials over Galois rings, Cryptogr. Commun. 18(6) (2026), 2057–2077, https://doi.org/10.1007/s12095–026–00895–x.
  2. [2]D. Tang, Three infinite classes of APN permutations on Zₙ, arXiv:2609.05917 (2026), https://arxiv.org/abs/2609.05917.
  3. [3]T. Beyne, L. Grassi, M. Øygarden, B. Richterová, A. Sandrib, The ABC of symmetric primitives over integer rings: milk before meat, Advances in Cryptology – CRYPTO 2026, LNCS, Springer, 438–470, https://doi.org/10.1007/978–3–032–35412–9_15; extended version: IACR ePrint 2026/1104.
  4. [4]H. Fukui, Carry-aware differential bounds and certified correction of local zero sums, preprint, version 1.0.1, Zenodo (2026), https://doi.org/10.5281/zenodo.23333044.
  5. [5]L. Grassi, I. Mantero Ayala, M. N. Hovd, M. Øygarden, H. Raddum, Q. Wang, Cryptanalysis of symmetric primitives over rings and a key recovery attack on Rubato, Advances in Cryptology – CRYPTO 2023, LNCS, Springer, 305–339, https://doi.org/10.1007/978–3–031–38548–3_11; extended version: IACR ePrint 2023/822.
  6. [6]L. Grassi, D. Khovratovich, R. Lüttenegger, C. Rechberger, M. Schofnegger, R. Walch, Monolith: circuit-friendly hash functions with new nonlinear layers for fast and constant-time implementations, IACR Trans. Symmetric Cryptol. 2024(3), 44–83, https://doi.org/10.46586/tosc.v2024.i3.44–83.
  7. [7]J. M. Rojas, Torric intersection theory for affine root counting, J. Pure Appl. Algebra 136 (1999), 67–100, https://doi.org/10.1016/S0022–4049(98)00023–1.

Paper details

vlnc:W_vqaqgytk
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

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

  • Mathematics

ChatGPT, Claude

View statement
Looking for related papers…
Contents