🔢 mathematics

Constructing Complete Permutations via the D-Class of Locally Crooked Permutations

This paper introduces the D-class of permutations over $\mathbb{F}_{2^{n+1}}$ to characterize and construct complete permutations via local conjugations, establishing their algebraic properties, cryptographic bounds, and CCZ-inequivalence while presenting algorithms that successfully enumerate new $\delta=4$ complete permutations.

Original authors: Li Shuai

Published 2026-10-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Li Shuai

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the hidden architecture of modern digital security, there exists a class of mathematical objects known as complete permutations. These are not merely random shuffles of numbers; they are highly structured rearrangements where the act of moving an item to a new position and the act of moving it to a position that is the sum of its old and new locations both result in perfect, non-overlapping order. This dual requirement is crucial for the design of substitution boxes, or S-boxes, which are the primary components in encryption systems that scramble data to hide its meaning. If these components are too predictable, the encryption can be broken; if they are too chaotic, they become inefficient. The challenge for cryptographers has long been to find the sweet spot: permutations that are complex enough to resist sophisticated attacks yet structured enough to be implemented quickly.

A recent study by Li Shuai of Ningxia University tackles this challenge by exploring a specific family of these permutations through a lens of geometric symmetry. The research focuses on a property called "local crookedness," which describes how a permutation behaves when its input is shifted by a specific amount. The author introduces a new category of these functions, defined by a specific pattern in how their outputs change. By treating these functions as elements of a larger group that can be transformed by shifting, rotating, or swapping specific parts of the data, the study maps out a landscape of possibilities. The goal was to see if moving within this landscape could generate new, superior permutations that offer better protection against differential cryptanalysis, a method where attackers study how small changes in input affect the output to deduce the secret key.

The core of the work involves a construction chain that starts with a known, well-behaved permutation and applies a series of precise algebraic operations to create new ones. The author defines a specific set of rules, or a "D-class," that these permutations must follow to remain valid. Within this set, the researcher proves that the collection of "lifted" permutations—those that have been extended from a smaller space to a larger one—possesses a unique rigidity. If one tries to change a single permutation using just one type of operation, such as a simple shift or a linear rotation, the result usually fails to remain a valid complete permutation. However, the study demonstrates that combining two different operations in a specific sequence breaks this rigidity. This combination allows the researcher to navigate the space of possibilities, moving from one valid permutation to another without losing the essential properties required for security.

To make this theoretical framework practical, the paper develops two distinct algorithms. The first is a backtracking search that builds a complete permutation from scratch, ensuring at every step that the dual ordering requirements are met. The second is a greedy local search that starts with an existing permutation and attempts to improve it by applying the combined operations described earlier. This second algorithm acts like a climber seeking a higher peak: it tests various small modifications, but only accepts a change if it strictly improves the cryptographic quality of the permutation. The quality is measured by two main indicators: differential uniformity, which counts the worst-case frequency of output patterns, and nonlinearity, which measures how far the function is from being a simple linear equation. Lower differential uniformity and higher nonlinearity are generally better for security.

The researchers tested these methods on a specific mathematical space of size 32, which corresponds to a 5-bit system. Starting from a simple, linear permutation that was known to be weak, the greedy search algorithm was run one hundred times. The experiments yielded several permutations with a differential uniformity of 4, a significant improvement over the starting value of 32. The study also began with one hundred randomly generated permutations and applied the same search process. Again, the algorithm consistently found permutations with a differential uniformity of 4. The results were not just about finding better numbers; the new permutations possessed distinct "spectra," or patterns of output frequencies, that were different from each other and from the starting point. This proves that the method does not just produce variations of the same object but genuinely discovers new, distinct classes of secure permutations.

One of the most striking findings concerns the relationship between these new permutations and a famous class of functions known as APN (Almost Perfect Nonlinear) functions. Historically, many constructions of secure permutations have relied on starting with these APN functions. However, the study found that the permutations generated by this new local-conjugation method, while having the same excellent differential uniformity of 4, are CCZ-inequivalent to those derived from the classic APN approaches. In fact, a reference permutation based on a well-known APN function performed worse in this specific test, with a differential uniformity of 8. This suggests that the new method explores a different region of the mathematical landscape, uncovering high-quality permutations that were previously inaccessible to standard construction techniques.

The paper concludes by proposing a conjecture based on the experimental evidence: that the entire space of these lifted permutations is connected. In other words, it appears possible to reach any valid permutation in this family from any other by following a path of these specific local modifications. While this connectivity has not been mathematically proven, the fact that the search algorithm consistently found high-quality solutions from diverse starting points provides strong preliminary support for the idea. The study also leaves open the question of whether this specific family of permutations contains functions that are even stronger than the ones found, potentially reaching the theoretical limit of security known as APN. For now, the work provides a robust new toolkit for generating secure permutations, demonstrating that by understanding the local symmetries of these mathematical objects, one can construct better defenses for the digital world.

Technical Summary: Constructing Complete Permutations via the D-Class of Locally Crooked Permutations

Problem Statement

The paper addresses the construction of Complete Permutations (CPs) over finite fields $\mathbb{F}_{2^n}$ . A permutation $f$ is a CP if both $f$ and the map $x \mapsto f(x) + x$ are permutations. CPs are critical in cryptography, specifically as building blocks for S-boxes in the Lai–Massey framework and for generating orthogonal Latin squares.

While CPs are linked to Locally Crooked Permutations (LCPs) over $\mathbb{F}_{2^{n+1}}$ via the Shuai–Li correspondence, previous methods relied on a "crooked function $\to$ LCP $\to$ CP" path. This approach was restrictive, as it did not allow for free movement or generation of new LCPs within the class itself. The paper seeks to overcome this by working directly inside the LCP class to generate new CPs through internal group actions, thereby expanding the search space for cryptographically strong permutations.

Methodology

1. The D-Class and Invariance

The author introduces the D-class, defined as the set of permutations $f$ over $\mathbb{F}_{2^{n+1}}$ such that the derivative in a fixed direction $q_1 = 2^n$ has an image equal to the complement of a fixed hyperplane $H = \{x : x_n = 0\}$ .
$D = \{f \in S_q : \text{Im } \Delta_{q_1}f = K\}$
where $K = \mathbb{F}_{2^{n+1}} \setminus H$ .

The paper proves that $D$ is closed under three specific group actions:

Left Translation: $t_a \circ f$ for any $a \in \mathbb{F}_q$ .
Left Multiplication: $g \circ f$ for any $g$ in the general linear group preserving $H$ ( $GL_H$ ).
Right Multiplication: $f \circ h$ for any $h$ in the centralizer $C$ of the involution swapping $H$ and $K$ .

Additionally, the class is closed under specific local translations $t_{a,X}$ (translations restricted to a subset $X$ ) provided $X$ is a union of orbits of a specific dihedral group generated by the translation and the conjugated involution.

2. Rigidity and the Construction Chain

The author defines the lifted CP subclass $D^\uparrow \subset D$ , consisting of permutations in $D$ that act as the identity on the complement $K$ .

Rigidity: The paper proves that $D^\uparrow$ is "rigid" under any single operation from the closure properties above (translation, linear multiplication, or centralizer multiplication). A single operation cannot map a lifted CP to another lifted CP unless it is the identity.
Construction Chain: To generate new CPs, the author constructs a chain involving a product of operations:
$CP \xrightarrow{\text{lift}} LCP \xrightarrow{\text{local translation}} LCP' \xrightarrow{\text{centralizer correction}} LCP'' \xrightarrow{\text{restriction}} \text{New } CP$
This chain utilizes localized centralizer elements ( $g_{a,X_1}$ and $g_{a,X_2}$ ) to "repair" the defect introduced by local translations, ensuring the result remains in $D^\uparrow$ .

3. Local Conjugations

The construction yields two specific local conjugations, $f_1$ and $f_2$ , defined on the base field $\mathbb{F}_{2^n}$ :

$f_1$ : A modification of $f$ on a subset $X_1 \subset H$ where $X_1$ is invariant under a dihedral group.
$f_2$ : A modification involving the inverse of $f$ on a subset $X_2$ where $X_2$ is invariant under a cyclic group.
The paper provides necessary and sufficient conditions for these modified maps to remain CPs.

4. Algorithms

Two algorithms are presented to implement the theory:

Random Backtracking Search: Generates random CPs from scratch by maintaining constraints on $f(x)$ and $f(x)+x$ .
Greedy Local Search: Iteratively applies the local conjugations ( $f_1, f_2$ ) to a seed CP. It accepts moves only if they strictly improve a quality function based on the full differential spectrum (DDT) and Walsh spectrum.

Key Results

Theoretical Contributions

Invariance Proof: Established that the D-class is invariant under the specified group actions and local translations.
Rigidity Theorem: Proved that the lifted CP subclass $D^\uparrow$ cannot be generated by single operations, necessitating the composite construction chain.
CCZ-Inequivalence Criteria: Derived criteria to determine when the newly constructed CPs are CCZ-inequivalent to the seed. This relies on checking if the Differential Distribution Table (DDT) or the multiset of absolute Walsh coefficients change.
Cryptographic Bounds: Derived bounds for differential uniformity ( $\delta$ ), nonlinearity ($nl$), and algebraic degree ( $\deg$ ) under local modifications. Specifically, $\delta$ changes by at most $2m$ where $m$ is the size of the modified subset.

Experimental Findings

Experiments were conducted on $H \cong \mathbb{F}_{2^5}$ (32 elements):

Generation of $\delta=4$ CPs: Starting from a linear seed ( $\delta=32$ ) and random seeds, the greedy search successfully found multiple complete permutations with differential uniformity $\delta=4$ .
Distinct Spectra: The generated CPs exhibited distinct differential spectra compared to each other and to a reference Dillon-based CP (which had $\delta=8$ ).
CCZ-Inequivalence: The distinct differential spectra confirm that the construction produces new CCZ-inequivalence classes, not just affine variants of the seed.
Connectivity Evidence: The repeated convergence to similar indicator distributions from different random seeds provides preliminary evidence that the set of lifted CPs $D^\uparrow$ may be connected under local-conjugation moves.

Significance and Claims

The paper claims to provide a systematic algebraic framework for generating new complete permutations by exploiting the internal structure of the LCP class.

Beyond Crooked Functions: Unlike previous methods dependent on starting with a crooked function, this approach allows for the exploration of the LCP space itself to find CPs.
Cryptographic Utility: The method successfully produces CPs with low differential uniformity ( $\delta=4$ ), a desirable property for S-boxes, which were previously harder to construct via the standard crooked-function correspondence.
Structural Insight: The identification of the "rigidity" of $D^\uparrow$ and the specific role of the centralizer in "repairing" local translations offers a deeper theoretical understanding of the relationship between LCPs and CPs.
Open Problems: The author modestly frames the connectivity of $D^\uparrow$ and the existence of APN functions within this class as open problems, suggesting that while the experiments support connectivity, a formal proof is required. They also note that while the results suggest a potential link to APN permutations, no APN permutations were explicitly established in this work.