Explicit permutations of (Z/4 Z) m with uniformly bounded differential uniformity
math.NT, cs.CR, cs.IT, math.IT
Submitted: 2026-11-02
Updated: 2026-11-02
Comments: 8 pages. Source, verification scripts and recorded outputs: https://doi.org/10.5281/zenodo.23876071
Code: https://github.com/hirokifukui/z4m-bounded-differential-uniformity
License: http://creativecommons.org/licenses/by/4.0/
The gist: Symmetric primitives over Galois rings need nonlinear components whose differentials with respect to ring addition are controlled.
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=2 m, so that (R,+) (Z/4 Z) m has order N=q squared. For every m at least1 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/sqrt N (Ronjom--Sandrib). The bound holds for the fixed permutation itself, not on average over keys. Equivalently, Δ(G c) at most36 against Δ at least2 sqrt N for permutation polynomials; since every permutation has Δ at least2, the least differential uniformity of a permutation of (Z/4 Z) m lies between 2 and 36 for every m. In Teichmuller digits (a,b) in F q squared and for c in F 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'not equal to0 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 (Δ at most440, resp. 510, for odd m).
Sources
Related papers
- K ab has the Bogomolov property for canonical heights
- Quasi-Jacobi forms, Appell-Lerch functions, and false theta functions as q-brackets of functions on partitions
- Wasserstein rates of all orders for the Sato-Tate law of Kloosterman sums
- Riemann functions for almost primes and their counting errors
- Topological flatness of orthogonal spin local models
- Asymptotic counting of integers with prime factors p r a s b