CS Paper Radar

A generalization of the map $χ$

Xiutao Feng, Qiang Wang, Jingyi Yu, Anpeng Zhang

cs.IT ·submitted 2026-09-17 01:17 UTC · v3

Abstract

The mapping $ χ_n:\mathbb{F}_2^n \to \mathbb{F}_2^n$ defined by $y=χ_n(x)$ with $y_i = x_i + x_{i+1}x_{i+2} + x_{i+2}$, where the indices are computed modulo $n$, has been widely studied for its application in lightweight cryptography. In this paper, we generalize this mapping and completely characterize all these shift-invariant permutations of the form $y_i=x_{i+u}+x_{i+v}(x_{i+w}+a_i)$, where $0\le u, v, w<n$ and $a_i\in \mathbb{F}_2$, $1\le i\le n$. We also determine their compositional inverses explicitly.

Comment
added a few remarks

Closest papers

Nearest neighbours by meaning across the whole index.

Shift-Invariant Permutations with Polynomial Composition: Construction and Algebraic Structure

cs.IT ·2026-09-25 ·Cheng Lyu, Dabin Zheng, Mu Yuan, Lei Hu
theory similarity 0.78
Abstract

Shift-invariant permutations of $\mathbb F_2^n$ are particularly attractive in symmetric cryptography because of their regularity and implementation efficiency. Constructing such permutations with an explicit algebraic structure remains a challenging problem. In this paper, we study a family of shift-invariant transformations of $\mathbb F_2^n$ constructed from a recursively defined sequence of mappings $\{γ_j\}_{j\ge 0}$ associated with landscapes. First, we prove that, under an explicit dimension condition relating $n$ to the support of the landscape, the sequence $\{γ_j\}_{j\ge 0}$ has the polynomial composition property if and only if the corresponding landscape is quasi-conserved on $\mathbb F_2^n$ with a nonzero special index. Then, we determine the eventual zero or periodic behavior of $\{γ_j\}_{j\ge0}$, including the exact index at which the sequence either first vanishes or becomes periodic, together with the least eventual period, and establish linear independence until the first linear relation occurs. When the polynomial composition property holds, we establish an explicit isomorphism between the group of permutation elements in the monoid generated by these mappings and the unit group of a quotient ring $\mathbb F_2[z]/\langle p(z)\rangle$, where $p(z)$ is a monomial or a binomial determined by the landscape. This framework reduces the tasks of testing bijectivity, computing iterates, and determining compositional inverses and orders of permutation elements to polynomial computations. Finally, we apply the results to mappings represented by binomials and trinomials in the quotient ring, obtaining explicit criteria and formulas, and tabulate more than one hundred representative constructions of shift-invariant permutations, recovering and unifying several previously studied families.

0.07

Constructions of complete permutations over $\mathbb{F}_q^n$

cs.CR cs.IT ·2026-09-03 ·Sartaj Ul Hasan, Ramandeep Kaur, Hridesh Kumar, Daniel Panario, Qiang Wang
similarity 0.64
Abstract

Complete permutation polynomials play an important role in cryptography, particularly in the design of cryptographic primitives such as the Lai--Massey scheme and S-boxes. We generalize a result of Sun, Li, Guo, and Qu (2021) by characterizing the complete permutation behavior of the mapping $Ψ(X)=M(X+ψ(AX))$ over $\mathbb{F}_q^n$, where $\mathbb{F}_q$ is a finite field of $q$ elements with $q$ being a prime power, $M\in GL(n, \mathbb{F}_q)$, $GL(n, \mathbb{F}_q)$ is the general linear group of order $n$ over $\mathbb{F}_q$, $A_{m \times n}$ is a full-rank matrix over $\mathbb{F}_q$, and $ψ=(ψ_1,ψ_2,\ldots,ψ_n)$ with each component function $ψ_i:\mathbb{F}_q^m\to\mathbb{F}_q$. Furthermore, we establish criteria for the permutation and complete permutation properties of the mapping $F(X)=T(X+B^tf(AX))$ over $\mathbb{F}_{q}^n$, $f: \mathbb{F}_{q}^{m} \rightarrow \mathbb{F}_{q}^{n-m}$, $T \in GL(n, \mathbb{F}_q)$, $A_{m \times n}$ and $B_{(n-m)\times n}$ are full-rank matrices over $\mathbb{F}_q$, $B^t$ represents the transpose of the matrix $B$, and $0<m<n$ are integers. These results also generalize an earlier result of Gravel and Panario (2023), who showed that any arbitrary function $f$ from $\mathbb{F}_q^m$ to $\mathbb{F}_q^{\,n-m}$ can be extended to a bijection over $\mathbb{F}_{q}^n$ through the mapping $F(X)=T(X+B^tf(AX))$, under the condition $AB^t=0$. Here we do not impose the restriction that $AB^t=0$.

0.38

Optimal Reduced Representatives of Quadratic APN Permutations in Odd Dimension

cs.CR math.NTcs.IT ·2026-10-15 ·Hiroki Fukui
theorycode/data similarity 0.62
Abstract · 22 pages. Submitted to IEEE Transactions on Information Theory. Code, certificates and Lean 4 formalization: https://github.com/hirokifukui/…

The formal derivative of the reduced polynomial representative of a map on a binary finite field depends on the coordinates, although its differential uniformity does not. This matters for lifting permutations to Galois rings: a polynomial over a Galois ring of characteristic a power of two greater than two permutes the ring exactly when its reduction permutes the residue field and the derivative of the reduction has no zero there. We prove that for every odd $n\ge5$, every quadratic almost perfect nonlinear permutation $Q$ of $\mathbb{F}_{2^n}$ admits invertible binary-linear maps $L$ and $A$ such that the derivative of the reduced representative of $L\circ Q\circ A$ has no zero and each of its nonempty fibres has exactly two elements. The range is exact: this fails for $n=3$, as computed earlier, and for even $n$ there are no such permutations. For $n\ge9$, a linearization and a projectively injective cofactor map reduce the problem to counting binary matrices: more than 5% of the invertible inputs $A$ succeed, more than half for $n\ge15$, without any classification. For $n=5,7$ we use two independent classifications and finite certificates. Consequently every such permutation is linearly equivalent to a counterexample to the reduced critical-point conjecture of Bartoli and Stănică that lifts to permutation polynomials of optimal differential uniformity over every Galois ring with this residue field. For odd $n\ge9$ the existence proof is checked in the Lean 4 proof assistant.

0.47

Double circulant LCD codes over $\mathbb{F}_2+u\mathbb{F}_2$ and their related binary LCD codes

cs.IT math.RA ·2026-10-12 ·Xingxing Xu, Bo Wu, Jon-Lark Kim
theory similarity 0.61
Abstract

Linear complementary dual (LCD) codes are linear codes that intersect their dual trivially. We study double circulant (Euclidean) LCD codes over the finite chain ring $R=\mathbb F_2+u\mathbb F_2$, where $u^2=0$. Using the Chinese Remainder Theorem and the factorization of $x^n-1$, we derive an explicit enumeration formula, with a separate treatment of the constituent corresponding to $x-1$, which is not obtained by a formal specialization of the previously known counting formula over $\mathbb F_q[u]/(u^k)$. Assuming Artin's primitive root conjecture for $2$, we show that the binary Gray images contain an asymptotically good family of rate $1/2$ which attains the asymptotic Gilbert--Varshamov bound, i.e., whose relative distance can approach $H_2^{-1}(1/2)$ from below. More importantly from the constructive viewpoint, by combining Gray images with a known extension construction, we obtain a binary LCD code with previously unknown parameters $[29,15,7]$ and construct two explicit permutation-inequivalent binary LCD codes with parameters $[45,23,9]$ and nine binary LCD codes with the best known parameters.

0.25

Equal Hamming Weights at Fixed Root Order and Applications to Constacyclic MDS Codes

cs.IT ·2026-10-31 ·Li Zhu, Hongfeng Wu
theory similarity 0.58
Abstract

For a fixed positive integer $n>1$, we study the prime powers $q$ coprime to $n$ for which all monic irreducible factors of $Φ_n$ over $\F_q$ have the same coefficient Hamming weight. Cyclotomic orbit coefficients give a finite, effective classification of these fields. Outside finitely many computable characteristics, every factor has the support of its characteristic-zero orbit polynomial; the uniform condition $p>2^{\varphi(n)}$ suffices. In each remaining characteristic, extension exponents reduce to divisors of $\ord_n(p)$, and an integer variance identity expressed by polynomial gcd degrees decides equal weight. The same coefficient data determine the full weight distribution. As an application, we prove that an MDS constacyclic code with an irreducible generator forces every irreducible polynomial of the same root order to have full support, including factors associated with different constacyclic constants. This yields a uniform gcd and norm obstruction. We develop its short-multiplier extension, give a prime-order cubic family, and establish an explicit quadratic-residue exclusion without a prime-square alphabet or a near-square length hypothesis.

0.20

Linear Equivalence of Full Weight Spectrum Cyclic Orbit Codes

cs.IT cs.GT ·2026-11-03 ·Minjia Shi, Ferruh Ozbudak
theory similarity 0.58
Abstract · 12 pages

We determine the linear-equivalence classes within the two families of full weight spectrum one-orbit cyclic subspace codes. This solves the second open problem posed by Castello, Polverino and Zullo [J. Combin. Theory Ser. A 212 (2025) 106005]. For the first family, the criterion is a fractional linear transformation over $\F_q$ followed by a power of $q$-Frobenius. For the second family, it is an affine transformation over $\F_{q^2}$ together with a power of $q$-Frobenius. We use polynomial spaces over finite fields, the linear-isometry theorem for cyclic orbit codes, and trace duality. The arguments include parameters belonging to proper subfields of the ambient field.

0.13

Affine Symmetries of Polynomial Roots with Multiplicities and Applications to Constacyclic Codes

cs.IT math.NT ·2026-09-22 ·Li Zhu, Hongfeng Wu
similarity 0.57
Abstract

Let $f(X)$ be a polynomial over a finite field, and let its defining function record the multiplicities of its roots. In this paper, we introduce the affine stabilizer group and the affine stabilizer group scheme of the defining function of $f(X)$. These objects characterize the affine symmetries of the roots of $f(X)$ together with their multiplicities. We establish structural descriptions of these affine stabilizers and relate them to the coefficient structure of $f(X)$. In particular, the affine stabilizer group determines quotient structures of the defining function, which yield canonical descriptions of the corresponding semi-invariant polynomial spaces. The resulting coefficient constraints provide explicit restrictions on the possible supports of polynomials with prescribed affine symmetries. The affine stabilizer group scheme further captures infinitesimal symmetries arising from multiple roots and gives refined coefficient constraints beyond those obtained from ordinary affine transformations. We apply this framework to generator polynomials of constacyclic codes over finite fields. The affine stabilizer structure of a generator polynomial induces subcodes defined by semi-invariant conditions and provides constraints on their dimensions and Hamming distances. In the special case of multiplicative symmetries, the construction specializes to the support-primitive decomposition of constacyclic codes.

0.33

Testing CCZ-equivalence to permutations via projections of Walsh zero spaces, with applications to APN functions

cs.CR cs.IT ·2026-11-06 ·Emanuele Bellini
similarity 0.57
Abstract

Whether almost perfect nonlinear (APN) permutations exist in even dimension $n\ge 8$ is a long-standing open question, the big APN problem. The only example known in even dimension, on six bits, was found from a quadratic APN function that is not itself a permutation, by Carlet--Charpin--Zinoviev (CCZ) equivalence. It is therefore natural to test APN functions for CCZ-equivalence to a permutation. This amounts to finding two complementary $n$-dimensional subspaces among the zeros of the Walsh transform, which lie in $\mathbb{F}_2^{2n}$. A known necessary condition only uses their projections to $\mathbb{F}_2^n$ and cannot decide every case. We give an exact test for functions whose Walsh supports are affine, including all quadratic functions. It reconstructs the subspaces from their projections, through searches for subspaces of $\mathbb{F}_2^n$ and for constrained bilinear maps. On the benchmarked functions in dimension twelve, it lists them $39$ to $55$ times faster than the generic search of the commonly used sboxU library. We then study the functions $x^3+a^{-1}\mathrm{Tr}(a^3x^9)$, which Göloğlu and Pavlů proved not to be CCZ-equivalent to permutations when $4$ divides $n$. With their result, our computations show that this holds for every even $n\le 24$. In dimension $18$ the necessary condition is satisfied, and the new test decides the case. We conjecture this for every even dimension. We also compile $25$ classes of quadratic APN functions in dimension ten from published instances, with equivalence certificates. No function in these classes or in their switching closure is CCZ-equivalent to a permutation. All code and data are public.

0.61