WorksMathematics
Explicit permutations of with uniformly bounded differential uniformity
Abstract
Symmetric primitives over Galois rings need nonlinear components whose differentials with respect to ring addition are controlled. Let and , so that has order . For every we construct an explicit permutation of all of whose differentials with a nonzero input difference have probability at most , whereas every permutation polynomial of has such a differential of probability at least (Ronjom–Sandrib). The bound holds for the fixed permutation itself, not on average over keys. Equivalently, against for permutation polynomials; since every permutation has , the least differential uniformity of a permutation of lies between and for every . In Teichmuller digits and for of absolute trace , with . The map is , where is induced by a polynomial over and exchanges the digits: a single digit exchange between two polynomial layers yields a bound independent of . The proof reduces the difference equations, in each of three types of directions, to one-variable polynomials whose degrees do not depend on . For general maps with , where have degrees bounded independently of , and has no zeros, a Jacobian identity in characteristic bounds the differentials with nonzero low input and output differences independently of ; the remaining directions need a separate argument, which we give for an explicit family (, resp. , for odd ).
Introduction
For a map on a finite abelian group put and . Over the group is elementary abelian, and power maps such as are permutations with for every odd . Symmetric primitives over the integer rings 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 , the additive group of , and there polynomial constructions face a restriction: Rønjom and Sandrib proved that every permutation polynomial of has [1 Theorem 3] (every polynomial function has [1 Proposition 2]); for this is , so a permutation with smaller 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 for composite [5 §4.3], where for the two digits are also exchanged; in the Kintsugi strategy over prime fields [6 §2]; and as “digit manipulation” over in Beyne, Grassi, Øygarden, Richterová and Sandrib [3 §9]. These constructions act on cyclic groups or on . Here we consider the groups , noncyclic for , and give an explicit family whose differential uniformity is bounded independently of . Rønjom and Sandrib also classify the table-defined (non-polynomial) permutations of with [1 §5]; no family covering all is given there. On cyclic groups several infinite families of permutations with are known (see [2] and the references there), but and are different groups for . Permutation polynomials are subject to the lower bound [1], and the one-sided digit-exchange maps of [4] attain , which is optimal within that class (Theorem 3.1). The family constructed here has for every , so the optimal order is constant.
Theorem 1.1. Let , , and with . In Teichmüller digits, the map with , , , is a permutation of and
Let be the least over all permutations of . Theorem 1.1 and Proposition 3.2 give for every , so , whereas every permutation polynomial has . In terms of probabilities, with , every differential of with a nonzero input difference has probability at most , which is of the optimal order . For example, for the ring has 65,536 elements (a 16-bit state): every permutation polynomial of has a differential of probability at least , while every differential of with a nonzero input difference has probability at most , more than 14 times smaller. In the instances of Table 1 () the exact values of are at most 20. Since 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 .
Comparison. With :
| map | digit system | |
| permutation polynomial | — | [1] |
| (output exchange only) | any | (Thm. 3.1) |
| Teichmüller | for all (Thm. 1.1) | |
| , , , , odd | Teichmüller | , resp. 510 (Thm. 5.4) |
| literal exchange (= with , , ) | Teichmüller | (Remark 5.3) |
| literal exchange | coordinate | (Prop. 6.2) |
| , 1-periodic | coordinate | (Prop. 6.1) |
Table 1.
The class in the second line contains the maps studied in [4] (coordinate digits, APN, affine), for which is attained; Theorem 3.1 shows that 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 .
Scope. We do not determine , and we do not consider other attacks (linear, integral, algebraic) or implementation cost. Open questions are collected in § 8.
Setting
Digits
. . Every is uniquely with , where is the Teichmüller lift; we write . The identity gives
hence
The coordinate digit system fixes a basis of over whose first vector is (for definiteness, the polynomial basis of ) and lifts coordinates to . The resulting map depends on the basis; all statements below about this system are for a basis with . Then (1) holds with the carry replaced by the coordinatewise product .
We apply the same formulas in both digit systems; they give different permutations of . The change of digits has the form , under which becomes with , and is in general not the literal exchange .
The maps
For with a permutation of and without zeros in , is a permutation of , hence of ; so are and . Theorem 1.1 is the case , , .
We call a polynomial layer because it is induced by a polynomial over . For with reduction , the identity shows that acts on digits as , where is the high digit of at ; conversely, every triple of functions arises in this way, by interpolation with the factor and a correction of the high digit. This is [4 Proposition “Coordinate form and realizability”], stated there for coordinate digits; the argument uses only that depends on alone, and holds verbatim for Teichmüller digits. The exchange is not of this form. Since every permutation polynomial of has [1], Theorem 1.1 shows that for the permutation is not induced by any polynomial over .
Output exchange alone
Theorem 3.1. Let be arbitrary and . In either digit system, .
Proof. Teichmüller digits: is . Since , is not injective; choose and with , and with . For and the low digits of and coincide, so by (2) for all values of . The coordinate case is identical with in place of (for the maps of [4], exactly). □
Proposition 3.2. Every map , , has . Consequently, for every , , the minimum over all permutations.
Proof. Let with and put . Then . If some has with , then as well, so . Otherwise misses the elements of order at most , so is not surjective and some value is taken twice. □
For permutations the bound is immediate in any finite group of order , since never takes the value ; Proposition 3.2 extends it to arbitrary maps.
Proof of the main theorem
Permutation. The image of on is the trace-zero hyperplane, so gives for all ; multiplies by a nonzero scalar on each fibre and is bijective. Explicitly
Difference equations. Fix and , and write , (Frobenius is bijective on , so runs over and ). By (1), , so
are the low digits of and . By (2), is equivalent to
Given (3), and , so (4) becomes , and squaring (Frobenius is injective) gives the equivalent condition
We count pairs satisfying (3) and (5); the map is a bijection.
*Case A: . Put , so . Then (3) reads , which determines from , and
a polynomial in of degree 9 with leading coefficient . Substituting into (5) and multiplying by gives
a polynomial in of degree 36 with leading coefficient (all other terms have degree at most 18). Hence at most 36 values of , each with one : . This includes .
*Case B: . Then and , so (3) reads , a monic polynomial of degree 5 in : at most 5 values. For each, (5) is a monic polynomial of degree 4 in , and . Hence .
*Case C: , . Then (3) reads ; there is no solution unless , and then has at most 2 roots . For each, (5) becomes , linear in with coefficient . Hence .
The three cases cover all , so . □
Remark 4.1. The argument holds for all and uses neither an APN property nor intersection theory. The constant comes from Case A: the degree of . In the instances of Table 1 the observed values are at most 20 and are not monotone in (10 for , 9 for ).
Remark 4.2 (Evaluation). On Teichmüller digits, costs two general multiplications, two squarings and four additions in ; given the output , the inverse , costs two inversions, two multiplications and two squarings. Passing between and its digits requires and , i.e. squarings in (since for any lift ). In settings where elements of are held as shares modulo 4, the reduction is a bit extraction whose cost depends on the protocol; we do not analyse it here.
A general method for FJF
For general the low-digit equation is no longer linear in , and a uniform bound needs an argument about common components. Let , , , , , and
By (2), after squaring the high digit,
Lemma 5.1. Put and . Then .
Proof. In characteristic 2 squares have zero derivative, so may be replaced by . The pair consists of the elementary symmetric functions of , with Jacobian ; next . Since involves only through , , , , , so .
Theorem 5.2. Let with and without zeros in , and let . If and , every common component of and in is a line with , and .
Proof. Let be an irreducible common component. On , and , so both differentials vanish on the tangent line at smooth points and the Jacobian of Lemma 5.1 vanishes on . As and , lies in , , or . The last two are unions of lines with or a root of , so .
Suppose on , so for a root of . If is vertical, while varies along , so forces and . If is not vertical, is transcendental over on and , so the function field is and
Since and , ; hence is not constant, contradicting . The case is symmetric: then with .
Thus is a product of vertical lines without -points, every -solution is an isolated point of , and affine Bézout gives the bound.
The second-stage high digit enters only inside the square, so Theorem 5.2 holds for every . The bound depends on only through the degrees of , and is uniform in when these degrees are bounded.
Remark 5.3. Theorem 5.2 bounds only for , , and assumes . The directions with or need a separate argument, and without one the differential uniformity of need not be bounded independently of . For example, , , satisfy the hypotheses, but and . For and we have , and by (2)
so . In fact : for put ; then . If , the value determines ; then determines when , and when we have with free. If , then , determines , and is free. The same row gives for the literal exchange in the coordinate system, but its exact value there is (Proposition 6.2); the two literal exchanges are different permutations of . In Theorem 1.1 and Theorem 5.2 the remaining directions are treated by hand.
Theorem 5.4. Let be odd, , , , and in Teichmüller digits. Then for and for .
Proof. For odd, is bijective and has no zeros in .
, . By Theorem 5.2 the -solutions are isolated roots in of a system whose supports are contained in the generic supports of ; the total degrees are at most , resp. , which already gives , resp. . These supports contain the origin and a pure power of each variable, so the pair is cornered, and it is nice (e.g. , resp. , 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
the second pair for .
, . On -points forces , and then cancels: . If , put ; then gives with , of degree 17 in with leading coefficient , and the remaining equation is non-constant of degree 72 in ; is then determined. If , then , reads , whose odd part is nonzero, so at most 9 values of ; for each, and is two-to-one. Hence .
, . Put ; in the coordinates (a bijection of ), . If then , impossible as cubing is bijective and ; so . Reducing modulo over leaves a polynomial of degree 1 in with coefficient , so each gives at most one . Eliminating , (resp. for ) with of degree 88 (resp. 96), nonzero leading coefficient for , and only even powers of . As is perfect, is the square of a polynomial of degree 44 (resp. 48), so (resp. 48). □
Remark 5.5. For the doubly exchanged maps of the same family, an analogous Jacobian identity holds, with ; whether these maps also have bounded independently of is left open (§ 8).
The coordinate digit system
Proposition 6.1. In the coordinate digit system with , if and for all (for instance , , or , ), then .
Proof. Take . Since , the carry is , the first coordinate of . For the values of with and all , and , so . These inputs land in at most values of . □
For and (with ) the row alone reaches 6, 22, 74 for . In general the kernel of has elements; in the Teichmüller system, by contrast, is injective for . In the coordinate system the carry is a linearised polynomial of degree up to , so the bounded-degree arguments above do not apply; whether has bounded there for some that is not 1-periodic is open.
Proposition 6.2. In the coordinate digit system with , the literal exchange has .
Proof. For put . Then . For a target , the set of with has 0 or elements, and the set of with has 0 or elements; hence . If then ; if then and . In both cases , so . For and , every and every with is a solution, so the bound is attained. □
For both literal exchanges have ; for they differ.
Data
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | |
| 2 | 4 | 4 | 6 | 10 | 9 | 12 | 14 | 16 | 20 |
Table 1 (PDF p. 7). Exact for the tested parameters. Ring model: with ring addition only and digits recovered by table lookup, for all with when and for two values of when . Digit formulas (1)–(2) (all directions, with a coverage check): one value of for each and two for ; these agree with the ring model for . The field polynomial and the values of are listed in the supplementary material. For each , the value was the same for every tested .
Open problems
Determine . By Table 1 and [1 §5], . Are there permutations of with for every ?
How far can the constant 36 be lowered, for or for other explicit families? For the tested parameters with (Table 1) the values of are at most 20.
For families of bounded degree, Theorem 5.2 bounds the differentials with , independently of . For which such families are the remaining directions also bounded independently of ? Does the same hold for the doubly exchanged maps ?
Can remain bounded independently of in the coordinate digit system for some 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, of degree 9 with leading coefficient and the eliminated equation of degree 36 with leading coefficient ; in Case B, the low equation monic of degree 5 in and the high equation monic of degree 4 in ; in Case C, the low equation and the high equation linear in with coefficient .
t5_ringmodel_v2.m(parameters mlo, mhi, cmax): in the ring model, using ring addition only.
gc_ddt_v2.cwithrun_gc_v2.sh: 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 .
c1_form1_assert.m: Lemma 5.1 as a polynomial identity (the family of Theorem 5.4 and random ), and the mixed volumes 440 and 510.
t3_u0_form1_v2.m: the elimination in Theorem 5.4 (exponent of the removed factor , degree and leading coefficient of , even exponents, and the linear remainder).
t1_J_counterexample.m: in the ring model for (Teichmüller digits, Remark 5.3);r05_t1_digit_swap.m: both literal exchanges for , with (Teichmüller) and coordinate, Proposition 6.2.
t6_sigma_row.m: the row 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]S. Rønjom, 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]D. Tang, Three infinite classes of APN permutations on Zₙ, arXiv:2609.05917 (2026), https://arxiv.org/abs/2609.05917.
- [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]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]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]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]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.