Source-linked AI summary
Constructions of complete permutations over $\mathbb{F}_q^n$
Sartaj Ul Hasan, Ramandeep Kaur, Hridesh Kumar, Daniel Panario, Qiang Wang
TL;DR
Complete permutations are used in cryptographic constructions, while earlier bijection criteria for F(X) considered the condition AB^t = 0. Using the AGW criterion, the paper shows that F(X) is bijective if and only if g(X) = X + AB^t(f(X)) permutes F^m. The paper characterizes when F(X) and F(X) + X are permutations without imposing AB^t = 0, and generalizes Sun, Li, Guo, and Qu’s characterization to arbitrary component functions.
Problem
Complete permutations are used in cryptographic constructions, while earlier bijection criteria for F(X) considered the condition AB^t = 0.
Source: §1 · p. 1Method
Results
The paper characterizes when F(X) and F(X) + X are permutations without imposing AB^t = 0, and generalizes Sun, Li, Guo, and Qu’s characterization to arbitrary component functions.
Source: §4.1 · p. 9, §5 · p. 14Takeaways & Limitations
The criteria extend the studied permutation constructions to settings that do not require AB^t = 0 and connect complete permutations to the Lai–Massey scheme.
Source: §5 · p. 14The stated characterization considers component functions ψ_i: Fq^m → Fq.
Source: §4.1 · p. 9
Abstract
from arXiv · showhide
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 $\Psi(X)=M(X+\psi(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 $\psi=(\psi_1,\psi_2,\ldots,\psi_n)$ with each component function $\psi_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$.
1. Introduction
The introduction motivates complete permutations through their cryptographic uses and sets out extensions of earlier criteria for complete permutation behavior. In particular, the paper removes the AB^t = 0 condition from a prior bijection construction and generalizes Sun, Li, Guo, and Qu’s result.
1. Introduction
- A complete permutation polynomial over Fq is a polynomial f for which both f(x) and f(x) + x permute Fq.The introduction traces the study of permutation polynomials to Hermite and Dickson, and complete permutations to Mann.Source: §1 · p. 1
- Complete permutation polynomials have cryptographic uses including avoiding nonzero fixed-point propagation and supporting uniformity of f(k) + k in some modes of operation.The introduction also links their absence in the Lai–Massey scheme to a probability-1 differential for any number of rounds.Source: §1 · p. 1
- Gravel and Panario showed that arbitrary functions can be extended to bijections under suitable conditions, including the restriction AB^t = 0 considered in their construction.The paper asks whether the extension remains bijective when that restriction is removed.Source: §1 · pp. 1–2
- The paper establishes conditions for both F(X) and F(X) + X to be permutations, extending the framework to cases without AB^t = 0.The relaxed condition complicates the function’s structure and motivates new analysis using the AGW criterion.Source: §1 · p. 2
- The paper generalizes Sun, Li, Guo, and Qu’s characterization to mappings with arbitrary component functions ψ_i: Fq^m → Fq.It also studies cryptographic relevance through complete permutation polynomials in the Lai–Massey scheme.Source: §1 · p. 2
2. Preliminaries
The preliminaries establish notation and recall the AGW criterion, alongside earlier results used in the paper’s subsequent permutation analysis.
2. Preliminaries
- The notation specifies X as a column vector, A and B as full-rank matrices, and I_r and 0_{r×s} as identity and zero matrices.The transpose of A is written A^t.Source: §2 · pp. 2–3
- The AGW criterion reduces bijectivity of a map to bijectivity of an induced map and injectivity on each fiber, when the two projection maps are surjective.The criterion is stated for finite sets with equal-sized target and source sets for the induced map.Source: §2 · p. 3
- The preliminaries invoke results from and, respectively, and Lemma 2.3 states that F(X) = T(X + Btf(AX)) is bijective over Fn.Source: §2 · p. 3
3. Extended discrete permutations and complete permutations
The section relaxes the orthogonality restriction for extended discrete permutations and reduces bijectivity of F to a permutation test on an m-dimensional map. It also gives criteria for completeness and constructions that extend functions to bijections.
Bijectivity criterion
- F(X)=T(X+B^t f(AX)) is bijective if and only if g(X)=X+AB^t(f(X)) permutes Fq^m.The criterion applies for full-rank A and B, invertible T, and 0<m<n.Source: §3 · p. 4
Relaxing orthogonality
- A difference condition, f(X+a)-f(X) in ker(AB^t) for every nonzero a, is given as a sufficient condition for F to be bijective.The condition is stated alongside the mapping F(X)=T(X+B^t f(AX)).Source: §3 · p. 4
Function extensions
- The construction extends functions using components g1,...,gk forming an orthogonal system, with the remaining hj allowed to be arbitrary.The paper states that a total of (q^k)!q^(n-m-k)q^m functions can be extended to bijective F.Source: §3 · p. 5
Complete permutation criteria
- F is a complete permutation exactly when g(X)=X+AB^t(f(X)) permutes Fq^m and at least one of the stated additional conditions holds.The conditions are organized by the rank of T+I_n.Source: §3 · p. 5
- For n-m<rank(T+I_n)<n, completeness requires CTB^t f(AX) to be onto and F(X)+X to be injective on each of its fibers.C is chosen full rank with (T^t+I_n)C^t=0.Source: §3 · pp. 6–7
- When rank(T+I_n)=n, the remaining completeness test is that h1 permutes Fq^m; injectivity on each AX fiber holds automatically.Here h1(X)=X+A(T+I_n)^-1TB^t f(X).Source: §3 · p. 6
- When rank(T+I_n)=n-m, completeness requires a row of A to lie outside the span of the other listed rows of A and T+I_n.The criterion states this row-span exclusion for some row rj of A.Source: §3 · p. 7
4. Other complete permutations and cryptographical applications
The section extends complete-permutation criteria to mappings with arbitrary component functions and gives more specific tests for linear components. It also illustrates how the resulting permutations can be used in Lai–Massey rounds.
4.1. Generalizations of Sun, Li, Guo and Qu (2021) construction.
- The generalization treats Ψ(X)=M(X+ψ(AX)) with arbitrary component functions ψ_i: Fq^m→Fq and characterizes its complete-permutation behavior.The theorem assumes a full-rank matrix A and 0<m<n.Source: §4.1 · p. 9
- Compared with the earlier setting of one-variable polynomial components, the generalization permits arbitrary functions on Fq^m and offers broader construction choices.The earlier setting has m=1, whereas the generalization allows m-dimensional inputs.Source: §4.1 · pp. 9–10
- Theorem 4.3 states that Ψ is a complete permutation over F_q^n iff I_m+A_1D is invertible over F_q and one of its three rank-dependent conditions holds.The cases are rank(M+I_n)=n, rank(M+I_n)=n−m, or n−m<rank(M+I_n)=k<n.Source: §4.1 · pp. 9–10
- For full rank(M+I_n), Ψ(X)+X permutes exactly when h1 permutes; in the rank n−m case, the criterion is invertibility of CMD1.The theorem also gives a fiberwise criterion for intermediate rank.Source: §4.1 · p. 11
- In the two-component example, Ψ is complete exactly when a1+1≠0 and a1b2−a2b1≠0.Source: §4.1 · pp. 11–12
4.2. A cryptographical application.
- The paper illustrates one round and an r-round Lai–Massey scheme using its complete permutation, while describing broader scheme applications as potential.Source: Figure 1 · p. 13, Figure 2 · p. 13, §4.2 · p. 13
5. Conclusion
The conclusion reports criteria for complete-permutation behavior in two mapping families and their use in the Lai–Massey scheme.
5. Conclusion
- The mapping F(X)=T(X+B^tf(AX)) has criteria for permutation and complete-permutation behavior without requiring AB^t=0.This extends the framework considered by Gravel and Panario (2023).Source: §5 · p. 14
- The complete-permutation behavior of Ψ(X)=M(X+ψ(AX)) is characterized, generalizing a result of Sun, Li, Guo, and Qu (2021).Source: §5 · p. 14
- The complete permutation polynomials obtained in the work can be incorporated into the Lai–Massey scheme for cryptographic applications.Source: §5 · p. 14