Coefficient choice in Galois-ring lifts of APN permutations: sharp unit-direction spectra and one-term optimal lifts
Abstract
Permutation polynomials over the Galois ring GR(2k,m) are nonlinear components for symmetric primitives that add keys in the ring, as in secure computation modulo 2k. Rønjom and Sandrib showed that their differential uniformity is at least 2qk−1, where q=2m. For the class studied here it is attained on top-layer differences, while almost all differences are units. We ask how small the difference table can be on unit differences when the residue permutation is fixed and only higher coefficient digits of its lift are chosen. Let m≥5 be odd, k≥3, and let p be a reduced quadratic almost perfect nonlinear (APN) permutation of 𝔽q whose derivative is nowhere zero and two-to-one. Over all lifts of p, the least possible maximum on unit differences is q or 2q, decided by two invariants of p and the level k. We describe every lift attaining it and show that the coefficients modulo $8$ decide optimality at every level. For every odd m≥5, residue permutations with at most $16$ monomials attain q after one $2$-adic digit of one coefficient of the natural lift is changed. For an explicit infinite family, one added monomial lowers the maximum on unit differences from 4q, or from at least q2, to 2q at every level without raising the degree. Under a uniform starting state and independent uniform round keys, valuation preservation yields layerwise bounds for characteristics and two-round differentials that distinguish lifts with the same global uniformity. Core results are formalized in Lean 4.
Related
- An optimal constant for vector balancing with permutations
- Atomic toposes, choice spectra and model-theoretic stability
- Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension
- Poisson contingency tables, Gibbs permutations, and entropic optimal transport
- Boundary Geometry Determines Optimal Shallow ReLU Approximation under Weighted Coefficient Constraints
BibTeX
@misc{fukui2026coefficient,
title = {{Coefficient choice in Galois-ring lifts of APN permutations: sharp unit-direction spectra and one-term optimal lifts}},
author = {Hiroki Fukui},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.21178},
eprint = {2610.21178},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.21178},
}
RIS
TY - UNPB
TI - Coefficient choice in Galois-ring lifts of APN permutations: sharp unit-direction spectra and one-term optimal lifts
AU - Hiroki Fukui
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2610.21178
UR - https://arxiv.org/abs/2610.21178
AB - Permutation polynomials over the Galois ring GR(2^k,m) are nonlinear components for symmetric primitives that add keys in the ring, as in secure computation modulo 2^k. Rønjom and Sandrib showed that their differential uniformity is at least 2q^k−1, where q=2^m. For the class studied here it is attained on top-layer differences, while almost all differences are units. We ask how small the difference table can be on unit differences when the residue permutation is fixed and only higher coefficient digits of its lift are chosen. Let m≥5 be odd, k≥3, and let p be a reduced quadratic almost perfect nonlinear (APN) permutation of 𝔽_q whose derivative is nowhere zero and two-to-one. Over all lifts of p, the least possible maximum on unit differences is q or 2q, decided by two invariants of p and the level k. We describe every lift attaining it and show that the coefficients modulo $8$ decide optimality at every level. For every odd m≥5, residue permutations with at most $16$ monomials attain q after one $2$-adic digit of one coefficient of the natural lift is changed. For an explicit infinite family, one added monomial lowers the maximum on unit differences from 4q, or from at least q^2, to 2q at every level without raising the degree. Under a uniform starting state and independent uniform round keys, valuation preservation yields layerwise bounds for characteristics and two-round differentials that distinguish lifts with the same global uniformity. Core results are formalized in Lean 4.
ER -