Utilizing Circulant Structure to Optimize the Implementations of Linear Layers

想象你是一位试图用特定的一套乐高积木建造复杂机器的建筑大师。在密码学（秘密代码的科学）世界中，这些“机器”被称为线性层，它们是负责搅乱数据以保护其安全的主力军。

多年来，建筑大师们一直试图用最少的积木（以节省空间）和最短的时间（以节省速度）来建造这些机器。你提供的这篇论文介绍了一种设计这些机器新方法，其关键在于发现了蓝图中的隐藏模式。

以下是他们发现的简要说明，以通俗易懂的方式呈现：

1. 问题：复杂性的“砖墙”

将密码学的线性层想象成一面巨大的开关墙。为了搅乱一条消息，你必须按照非常特定的顺序翻转这些开关。

目标：你希望用最少的翻转动作（以节省能量/空间）和最少的步骤（以使其快速）来翻转这些开关。
旧方法：以前的方法将墙壁视为巨大且混乱的开关堆。它们使用试错算法来寻找最佳顺序，但由于墙壁过于庞大和杂乱，它们往往错过了最高效的路径。这就像试图通过随机撞墙来解决迷宫一样。

2. 发现：“旋转轮”模式

作者们注意到，许多这些密码墙壁实际上并非随机。它们具有循环结构。

类比：想象一个旋转木马。如果你给马匹拍张照片，然后旋转照片，马匹的图案看起来几乎一样，只是发生了位移。
用数学术语来说，矩阵（开关的蓝图）是通过不断平移单行构建而成的。这是一种重复的、旋转的模式。
洞察：以前的建筑大师忽略了这种“旋转木马”模式，将墙壁视为混乱的乱局。作者们意识到，如果你承认这种模式，就可以更高效地拆解这面墙。

3. 解决方案：“折叠”技巧

作者们开发了一种方法，将整个问题折叠起来，而不是试图一次性解决整面巨大的墙。

隐喻：想象你有一床带有重复图案的巨大、厚重的被子。与其试图一次性折叠整床被子，你意识到因为图案是重复的，你可以将左半部分折叠到右半部分，然后将上半部分折叠到下半部分。
通过使用这种“折叠”技术（在数学上转换矩阵），他们可以将一面巨大、复杂的墙变成一个更简单的三角形形状。
一旦墙壁被简化为这种三角形形状，标准工具就可以轻松完成工作。这就像在尝试打结之前，先将一团乱麻的毛线变成一条整齐的直线。

4. 结果：更快、更小的机器

作者们在流行安全系统中使用的真实密码机器上测试了这种新的“折叠”方法。结果令人印象深刻：

“旋风”机器：
- 速度：他们将机器运行所需的时间减少了39%。想象一辆以前需要 28 秒才能行驶一英里的汽车，现在只需 17 秒。
- 大小：他们将所需的“积木”（逻辑门）数量减少了约 30%。这意味着机器更小，功耗更低。
“AES"机器（黄金标准）：
- AES 是世界上最著名的加密标准。其“列混合”（MixColumn）部分是一个 notoriously 难以高效解决的难题。
- 成就：作者们构建了一个自动化系统，几乎像一位花费数周手动调整设计的人类专家一样解决了这个难题。
- 局限：人类专家的设计使用了 105 个“积木”。作者们的自动化设计使用了 107 个。这意味着仅为了获得一个自动化而非手工实现的结果，只多用了2 块积木。他们还追平了最快速度（深度）的记录。

5. 为什么这很重要

面向未来：随着计算机（包括量子计算机）变得越来越强大，这些“机器”需要更快、更小才能保持安全。
核心启示：通过简单地认识到蓝图具有重复、旋转的模式（像旋转木马一样），作者们找到了一条以前方法所遗漏的捷径。他们并没有发明一种新型积木；他们只是找到了一种更聪明的堆叠方式。

总结：这篇论文指出：“我们发现许多安全代码都是建立在重复模式之上的。通过首先利用该模式简化设计，我们可以比以往任何时候都更快、更小地构建安全系统，甚至超越了一些最优秀的人类专家。”

技术摘要：利用循环结构优化线性层的实现

问题陈述
线性层在对称密码学中的优化对于轻量级实现（受门数量和面积限制）和量子安全评估（受电路深度和 DW 成本限制）都至关重要。虽然现有的启发式算法可用于合成通用可逆矩阵的 CNOT 电路（量子）和 XOR 电路（经典），但它们往往未能充分利用密码学设计中固有的特定代数结构。许多广泛使用的矩阵，如 AES 的 MixColumn 和 Whirlwind 中的矩阵，都具有循环结构。现有的最先进方法（如 Shi 和 Feng [SF24] 提出的方法）将这些矩阵视为通用的 $n \times n$ 二进制矩阵，从而可能错失利用其底层循环特性来降低电路深度和门数量的机会。

方法论
作者提出了一种新颖的框架，显式地利用矩阵的循环结构来指导高效电路的合成。核心方法论涉及一种递归分解策略，将扩展域（例如 $F_{2^k}$ 或 $GL(F_2, m)$ ）上的循环矩阵转化为更简单的形式，具体为上三角矩阵，然后再应用标准的启发式优化。

关键技术组件包括：

递归块变换：定理 3 表明， $F_2[x]$ 上的 $2^k \times 2^k$ 循环矩阵可以通过初等行和列操作转化为块上三角矩阵。该算法将矩阵递归地分割为块 $A$ 和 $B$ （其中 $M = \begin{smallmatrix} A & B \\ B & A \end{smallmatrix}$ ），并应用操作以消除特定块（例如，转化为 $\begin{smallmatrix} A+B & B \\ A+B & \dots \end{smallmatrix}$ ）。
变换路径探索：作者观察到，递归步骤中不同的行和列操作选择会导致不同的中间矩阵。该算法（算法 1）探索多种变换路径（对于较小的 $k$ ，可能性多达 $4^{2^k-1}$ 种），以找到能产生最高效后续电路的路径。
提前停止与回退：认识到递归在深度增加时效益递减，作者引入了一种策略（算法 2）以提前停止递归。该算法遍历不同的“块大小”，从而有效地改变递归深度。如果提前停止递归，生成的矩阵将被传递给标准启发式优化器（Heu）以进行通用的 CNOT/XOR 合成。这包括一种“回退”策略，其中递归深度为零，实际上将矩阵视为通用情况处理。
自动化优化：与以往的手工方法（例如 Zhang 等人 [ZSWS24] 针对 AES 的方法）不同，该方法自动化了寻找“更简单”矩阵形式及相应门序列的过程，无需人工干预。

主要贡献

新颖框架：这是首项系统性地利用线性层循环结构以优化电路实现的工作，填补了代数矩阵属性与电路合成启发式方法之间的空白。
自动化合成：作者提供了一种自动化算法，取代了手工的、特定案例的优化。它生成变换矩阵序列，使下游启发式方法能够发现更高效的实现方案。
双重优化：该框架既适用于量子电路（最小化 CNOT 数量和深度），也适用于经典电路（最小化 XOR 数量，特别是 g-XOR 和 s-XOR）。

结果
作者在来自分组密码（包括 AES、Whirlwind、Clefia、PRIDE 等）的线性层数据集以及构建的 MDS 矩阵上评估了他们的方法。

量子电路深度：
- Whirlwind M0：所提出的方法将电路深度从 28（[SF24] 之前的最先进结果）降低至17，提升了39%。门数量也从 286 减少到 200。
- AES MixColumn：自动化方法实现了10的深度，与 Zhang 等人 [ZSWS24] 手工优化的最先进结果持平。门数量为 107，仅比手工结果（105）多 2 个 CNOT，且显著优于 [SF24] 实现的 131 个 CNOT。
- 其他矩阵：对于高密度矩阵（如 Whirlwind、SKOP15 8x8），观察到了显著的深度降低；而对于启发式方法本身表现良好的稀疏矩阵，改进则微乎其微或不存在。
经典电路（XOR 数量）：
- Whirlwind M0：该方法实现了159 的 s-XOR 数量，比 Yuan 等人 [YWS+24] 之前的最佳结果 173 提高了约 8%。
- 整体表现：虽然该方法对许多矩阵通常会产生规模开销，但它成功地在特定高密度矩阵（如 Whirlwind M0 和 M1）上击败了最先进结果。

意义与主张
论文主张，利用循环结构是优化线性层的一个强大但此前未被充分利用的途径。作者断言他们的方法：

优于现有启发式方法：针对标准贪婪策略难以应对的特定高密度矩阵。
自动化手工优化：实现了与人工专家调优电路相当的结果（如 AES MixColumn 所示），而无需人工干预。
提供新的基准：为量子安全评估提供了新的基准，能够更准确地估算线性层的深度，这对于计算后量子安全评估中的 DW（深度 $\times$ 宽度）成本至关重要。

作者总结道，虽然该方法并非对所有类型的矩阵（特别是稀疏矩阵）都普遍优越，但它为具有循环结构和高密度的矩阵提供了显著优势，展示了将代数属性融入电路合成的潜力。

1. 问题：复杂性的“砖墙”

2. 发现：“旋转轮”模式

3. 解决方案：“折叠”技巧

4. 结果：更快、更小的机器

5. 为什么这很重要

类似论文