🔢 数学

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

本文通过引入 $\mathbb{F}_{2^{n+1}}$ 上的 D 类置换，利用局部共轭来刻画并构造完全置换，建立了其代数性质、密码学界限及 CCZ 不等价性，并提出了成功枚举出新的 $\delta=4$ 完全置换的算法。

原作者： Li Shuai

发布于 2026-10-16

📖 1 分钟阅读🧠 深度阅读

原作者： Li Shuai

原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在现代数字安全的隐秘架构中，存在着一类被称为“完全置换”（complete permutations）的数学对象。它们并非仅仅是数字的随机打乱，而是具有高度结构的重排：将一个元素移动到新位置的行为，与将其移动到其旧位置与新位置之和的位置的行为，两者都能产生完美的、互不重叠的有序状态。这种双重要求对于替换盒（S-boxes）的设计至关重要，而 S 盒是加密系统中用于扰乱数据以隐藏其含义的核心组件。如果这些组件过于可预测，加密就会被破解；如果过于混沌，则会变得效率低下。长期以来，密码学家的挑战一直在于寻找那个平衡点：既要足够复杂以抵御复杂的攻击，又要足够结构化以便快速实现。

宁夏大学的李帅开展的一项近期研究，通过几何对称性的视角，探讨了这一特定置换族。该研究聚焦于一个称为“局部弯曲度”（local crookedness）的属性，它描述了一个置换在输入被特定偏移量改变时的行为。作者引入了一类新的函数，其定义在于其输出变化方式的一种特定模式。通过将这些函数视为一个更大的群中的元素，且该群可以通过对数据的平移、旋转或交换进行变换，该研究绘制出了一幅可能性图谱。其目标是观察在这一图谱中移动是否能生成更优越的置换，从而提供更好的保护，以抵御差分分析攻击——这是一种攻击者通过研究输入的小幅变化如何影响输出，进而推导出密钥的方法。

这项工作的核心是一个构建链，它从一个已知且表现良好的置换开始，并应用一系列精确的代数运算来创建新的置换。作者定义了一套特定的规则，或称“D 类”（D-class），这些置换必须遵循这些规则以保持有效性。在这一集合内，研究人员证明了那些“提升”（lifted）置换——即从较小空间扩展到较大空间的置换——具有一种独特的刚性。如果试图仅使用一种操作（如简单的平移或线性旋转）来改变一个置敛，结果通常无法保持为一个有效的完全置换。然而，研究表明，通过特定顺序结合两种不同的操作可以打破这种刚性。这种组合允许研究人员在可能性空间中进行导航，在不丢失安全所需基本属性的前提下，从一个有效的置换移动到另一个。

为了使这一理论框架具备实用性，论文开发了两种不同的算法。第一种是回溯搜索，它从零开始构建一个完全置换，确保在每一步都满足双重排序要求。第二种是贪婪局部搜索，它从一个现有的置换开始，并通过应用前述的组合操作尝试对其进行改进。第二种算法就像一个寻求更高顶峰的攀登者：它测试各种微小的修改，但只有当修改能严格提升置换的密码学质量时，才会接受该变化。质量由两个主要指标衡量：差分均匀度（differential uniformity），它计算输出模式的最坏情况频率；以及非线性度（nonlinearity），它衡量函数偏离简单线性方程的程度。较低的差分均匀度和较高的非线性度通常意味着更好的安全性。

研究人员在大小为 32 的特定数学空间（对应于 5 位系统）上测试了这些方法。从一个已知较弱的简单线性置换开始，运行了贪婪搜索算法一百次。实验产生了几个差分均匀度为 4 的置换，相比初始值 32 有了显著提升。研究也从一百个随机生成的置换开始，并应用了相同的搜索过程。同样，算法一致地找到了差分均匀度为 4 的置换。结果不仅是找到了更好的数值，这些新生成的置换还拥有截然不同的“谱”（spectra），即输出频率的模式，它们彼此之间以及与起点之间都是不同的。这证明了该方法不仅仅是在产生同一对象的变体，而是真正发现了新的、不同类别的安全置换。

一个最引人注目的发现涉及这些新置换与一类著名的函数——APN（几乎完美非线性）函数之间的关系。历史上，许多安全置换的构建都依赖于从这些 APN 函数开始。然而，研究发现，通过这种新的局部共轭法生成的置换，虽然具有同样优秀的差分均匀度 4，但在 CCZ 不等价性上不同于那些源自经典 APN 方法的置换。事实上，一个基于已知 APN 函数的参考置换在本次特定测试中的表现较差，其差分均匀度为 8。这表明，新方法探索了数学图谱中一个不同的区域，挖掘出了标准构建技术此前无法触及的高质量置换。

论文最后提出了一个基于实验证据的猜想：认为这些提升置换的整个空间是连通的。换句话说，似乎可以通过遵循这些特定的局部修改路径，从该家族中的任何一个有效置换到达任何另一个。虽然这种连通性尚未得到数学证明，但搜索算法从多样化的起始点一致地找到了高质量解这一事实，为这一观点提供了强有力的初步支持。研究还留下了这样一个问题：这个特定的置换族是否包含比目前发现的更强大的函数，甚至可能达到被称为 APN 的理论安全极限。目前来看，这项工作提供了一套生成安全置换的强大新工具，证明了通过理解这些数学对象的局部对称性，我们可以为数字世界构建更好的防御。

技术摘要：通过局部弯曲置换的 D-类构造完全置换

问题陈述

本文研究了在有限域 $\mathbb{F}_{2^n}$ 上构造完全置换 (Complete Permutations, CPs) 的问题。若置换 $f$ 及其映射 $x \mapsto f(x) + x$ 均为置换，则称 $f$ 为 CP。CPs 在密码学中至关重要，特别是在 Lai–Massey 框架中作为 S-box 的构建模块，以及用于生成正交拉丁方阵。

虽然 CPs 通过 Shuai–Li 对应关系与 $\mathbb{F}_{2^{n+1}}$ 上的局部弯曲置换 (Locally Crooked Permutations, LCPs) 相关联，但以往的方法依赖于“弯曲函数 $\to$ LCP $\to$ CP”的路径。这种方法具有局限性，因为它不允许在 LCP 类内部进行自由移动或生成新的 LCP。本文旨在通过在 LCP 类内部利用内部群作用来直接生成新的 LCPs，从而扩展寻找强密码学置换的搜索空间。

方法论

1. D-类与不变性

作者引入了 D-类，定义为 $\mathbb{F}_{2^{n+1}}$ 上的置换集合 $f$ ，其在固定方向 $q_1 = 2^n$ 下的导数之像等于一个固定超平面 $H = \{x : x_n = 0\}$ 的补集。
$D = \{f \in S_q : \text{Im } \Delta_{q_1}f = K\}$
其中 $K = \mathbb{F}_{2^{n+1}} \setminus H$ 。

论文证明了 $D$ 对三种特定的群作用是封闭的：

左平移： 对于任何 $a \in \mathbb{F}_q$ ，为 $t_a \circ f$ 。
左乘法： 对于任何属于保持 $H$ 不变的广义线性群 ( $GL_H$ ) 的 $g$ ，为 $g \circ f$ 。
右乘法： 对于任何属于交换 $H$ 与 $K$ 的对合的中心化子 $C$ 中的 $h$ ，为 $f \circ h$ 。

此外，该类在特定的局部平移 $t_{a,X}$ （限制在子集 $X$ 上的平移）下也是封闭的，前提是 $X$ 是由平移和共轭对合生成的特定二面体群的轨道并集。

2. 刚性与构造链

作者定义了提升后的 CP 子类 $D^\uparrow \subset D$ ，该子类由在补集 $K$ 上表现为恒等映射的 $D$ 中置换组成。

刚性： 论文证明了 $D^\uparrow$ 在上述任何单一操作（平移、线性乘法或中心化子乘法）下都是“刚性”的。单一操作无法将一个提升后的 CP 映射为另一个提升后的 CP，除非该操作为恒等映射。
构造链： 为了生成新的 CPs，作者构造了一个涉及操作乘积的链：
$CP \xrightarrow{\text{提升}} LCP \xrightarrow{\text{局部平移}} LCP' \xrightarrow{\text{中心化子修正}} LCP'' \xrightarrow{\text{限制}} \text{新 } CP$
该链利用局部中心化子元素 ( $g_{a,X_1}$ 和 $g_{a,X_2}$ ) 来“修复”局部平移引入的缺陷，从而确保结果仍属于 $D^\uparrow$ 。

3. 局部共轭

该构造产生了两个定义在基域 $\mathbb{F}_{2^n}$ 上的特定局部共轭 $f_1$ 和 $f_2$ ：

$f_1$ ： 对 $f$ 在子集 $X_1 \subset H$ 上的修改，其中 $X_1$ 在二面体群下是不变的。
$f_2$ ： 涉及 $f$ 的逆在子集 $X_2$ 上的修改，其中 $X_2$ 在循环群下是不变的。
论文提供了这些修改后的映射仍为 CPs 的充分必要条件。

4. 算法

文中提出了两种实现该理论的算法：

随机回溯搜索： 通过维持对 $f(x)$ 和 $f(x)+x$ 的约束，从头开始生成随机 CPs。
贪婪局部搜索： 迭代地将局部共轭 ( $f_1, f_2$ ) 应用于种子 CP。它仅在移动能严格改善基于全微分谱 (DDT) 和 Walsh 谱的质量函数时才接受移动。

关键结果

理论贡献

不变性证明： 确立了 D-类在指定的群作用和局部平移下的不变性。
刚性定理： 证明了提升后的 CP 子类 $D^\uparrow$ 不能通过单一操作生成，因此需要复合构造链。
CCZ-不等价准则： 推导了判定新构造的 CPs 是否与种子在 CCZ-不等价意义上不同的准则。这依赖于检查微分分布表 (DDT) 或绝对 Walsh 系数的多重集是否发生变化。
密码学界限： 推导了局部修改下的微分均匀度 ( $\delta$ )、非线性度 ($nl $) 和代数次数 ($ \deg $) 的界限。具体而言，$ \delta $的变化最多为$ 2m $，其中$ m$ 是修改子集的大小。

实验发现

在 $H \cong \mathbb{F}_{2^5}$ （32 个元素）上进行了实验：

生成 $\delta=4$ 的 CPs： 从线性种子 ( $\delta=32$ ) 和随机种子出发，贪婪搜索成功找到了多个具有微分均匀度 $\delta=4$ 的完全置换。
不同的谱： 生成的 CPs 表现出与彼此以及与参考的 Dillon-基于 CP（其 $\delta=8$ ）不同的微分谱。
CCZ-不等价性： 不同的微分谱证实了该构造产生的是新的 CCZ-不等价类，而不仅仅是种子的仿射变体。
连通性证据： 从不同的随机种子出发，反复收敛到相似的指示分布，这为 $D^\uparrow$ 在局部共轭移动下可能是连通的提供了初步证据。

重要性与主张

本文声称通过利用 LCP 类的内部结构，提供了一个系统的代数框架来生成新的完全置换。

超越弯曲函数： 不同于以往依赖于从弯曲函数开始的方法，这种方法允许探索 LCP 空间本身以寻找 CPs。
密码学效用： 该方法成功产生了具有低微分均匀度 ( $\delta=4$ ) 的 CPs，这是 S-box 中理想的属性，而通过标准的弯曲函数对应关系实现这一目标此前较为困难。
结构洞察： 对 $D^\uparrow$ “刚性”的识别以及中心化子在“修复”局部平移中的特定作用，提供了对 LCP 与 CP 之间关系的更深层次理论理解。
开放问题： 作者谦逊地将 $D^\uparrow$ 的连通性和该类中 APN 函数的存在性归为开放问题，表明虽然实验支持连通性，但仍需形式化证明。他们还指出，虽然结果暗示了与 APN 置换的潜在联系，但本研究并未明确建立 APN 置换。