Explicit permutations of (ℤ/4ℤ)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) and q=2m, so that (R,+)≅(ℤ/4ℤ)m has order N=q2. For every m≥1 we construct an explicit permutation Gc of R all of whose differentials with a nonzero input difference have probability at most 36/N, whereas every permutation polynomial of R has such a differential of probability at least 2/√N (Ronjom--Sandrib). The bound holds for the fixed permutation itself, not on average over keys. Equivalently, Δ(Gc)≤36 against Δ≥2√N for permutation polynomials; since every permutation has Δ≥2, the least differential uniformity of a permutation of (ℤ/4ℤ)m lies between $2$ and $36$ for every m. In Teichmuller digits (a,b)∈𝔽q2 and for c∈𝔽q of absolute trace $1$, Gc(a,b)=(L,(L2+L+c)a) with L=(a2+a+c)b. The map is Fc∘ J∘ Fc, where Fc(a,b)=(a,(a2+a+c)b) is induced by a polynomial over R and J exchanges the digits: a single digit exchange between two polynomial layers yields a bound independent of m. The proof reduces the difference equations, in each of three types of directions, to one-variable polynomials whose degrees do not depend on m. For general maps F∘ J∘ F with F(a,b)=(p(a),h(a)+d(a)b), where p,d,h have degrees bounded independently of m, p'≠0 and d has no zeros, a Jacobian identity in characteristic $2$ bounds the differentials with nonzero low input and output differences independently of m; the remaining directions need a separate argument, which we give for an explicit family (Δ≤440, resp. $510$, for odd m).
Related
- Uniformly Bounded Orthonormal Bases of Homogeneous Polynomials on the Complex Sphere
- Relative property (T) for uniformly bounded representations
- Rudin's Problem on Uniformly Bounded Homogeneous Orthonormal Bases
- New Construction of Power Functions with Low c-Differential Uniformity over Finite Fields
- Low-dimensional approximation of uniformly bounded orthonormal systems
BibTeX
@misc{fukui2026explicit,
title = {{Explicit permutations of $(\mathbbZ/4\mathbbZ)^m$ with uniformly bounded differential uniformity}},
author = {Hiroki Fukui},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02572},
eprint = {2611.02572},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02572},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Explicit permutations of (ℤ/4ℤ)^m with uniformly bounded differential uniformity
AU - Hiroki Fukui
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.02572
UR - https://arxiv.org/abs/2611.02572
AB - Symmetric primitives over Galois rings need nonlinear components whose differentials with respect to ring addition are controlled. Let R=GR(4,m) and q=2^m, so that (R,+)≅(ℤ/4ℤ)^m has order N=q^2. For every m≥1 we construct an explicit permutation G_c of R all of whose differentials with a nonzero input difference have probability at most 36/N, whereas every permutation polynomial of R has such a differential of probability at least 2/√N (Ronjom--Sandrib). The bound holds for the fixed permutation itself, not on average over keys. Equivalently, Δ(G_c)≤36 against Δ≥2√N for permutation polynomials; since every permutation has Δ≥2, the least differential uniformity of a permutation of (ℤ/4ℤ)^m lies between $2$ and $36$ for every m. In Teichmuller digits (a,b)∈𝔽_q^2 and for c∈𝔽_q of absolute trace $1$, G_c(a,b)=(L,(L^2+L+c)a) with L=(a^2+a+c)b. The map is F_c∘ J∘ F_c, where F_c(a,b)=(a,(a^2+a+c)b) is induced by a polynomial over R and J exchanges the digits: a single digit exchange between two polynomial layers yields a bound independent of m. The proof reduces the difference equations, in each of three types of directions, to one-variable polynomials whose degrees do not depend on m. For general maps F∘ J∘ F with F(a,b)=(p(a),h(a)+d(a)b), where p,d,h have degrees bounded independently of m, p'≠0 and d has no zeros, a Jacobian identity in characteristic $2$ bounds the differentials with nonzero low input and output differences independently of m; the remaining directions need a separate argument, which we give for an explicit family (Δ≤440, resp. $510$, for odd m).
ER -