改进的SPECK和LowMC量子分析

### 改进的 SPECK 和 LowMC 量子分析 #### 1. 引言 当前，最先进的量子计算机资源非常有限，无法运行 Grover 算法。若攻击密码所需的量子成本较高，即便在量子时代，该密码也有望在不增加密钥长度的情况下提供所需的安全保障（即 n 比特安全）。因此，评估和分析各种密码的量子攻击成本至关重要。 #### 2. 相关工作 Grassl 等人首次提出使用 Grover 搜索算法恢复 AES 密钥所需的量子资源估计。此后，研究界对 AES 进行了多种实现，致力于高效实现量子电路，以降低运行 Grover 搜索算法的资源成本。除 AES 外，众多其他密码也接受了量子分析，如 SIMON、SPECK、SKINNY 等。 #### 3. 量子门 常见的用于将密码实现为量子电路的量子门包括 X（非）、CNOT 和 Toffoli（CCNOT）门： - **X 门**：反转量子比特的值，可替代经典的非操作，即 X(a) = ∼a。 - **CNOT 门**：作用于两个量子比特，目标量子比特的值根据控制量子比特的值确定。若控制量子比特的值为 1，则目标量子比特反转；若为 0，则保持不变，即 CNOT(a, b) = (a, a ⊕ b)，可替代经典的异或操作。 - **Toffoli 门**：作用于三个量子比特，有两个控制量子比特和一个目标量子比特。仅当两个控制量子比特的值都为 1 时，目标量子比特的值反转，即 Toffoli(a, b, c) = (a, b, c ⊕ ab)，可替代经典的与操作。 从优化角度看，减少 Toffoli 门的数量很重要，因为它由 T 门（决定 T 深度）和 Clifford 门（如 CNOT、H 或 X 门）组合实现，成本相对较高。本文采用将一个 Toffoli 门分解为 7 个 T 门 + 8 个 Clifford 门的方法，T 深度为 4，全深度为 8。 #### 4. NIST 安全级别 NIST 为描述密码对量子对手的安全性，规定了以下安全级别： - **级别 1**：密码至少与 AES - 128 一样难以破解。 - **级别 2**：密码至少与 SHA - 256 一样难以破解。 - **级别 3**：密码至少与 AES - 192 一样难以破解。 - **级别 4**：密码至少与 SHA - 384 一样难以破解。 - **级别 5**：密码至少与 AES - 256 一样难以破解。 NIST 建议密码至少达到级别 1、2 和/或 3，以在量子时代提供足够的安全性。 #### 5. 目标密码 ##### 5.1 SPECK 家族 SPECK 是美国国家安全局（NSA）在 2013 年开发的轻量级分组密码家族，采用类似 Feistel 的结构，包含 10 种变体。其参数如下表所示： | 字长 (n) | 密钥字 (m) | 块大小 (2n) | 密钥大小 (nm) | α | β | 轮数 (T) | | --- | --- | --- | --- | --- | --- | --- | | 16 | 4 | 32 | 64 | 7 | 2 | 22 | | 24 | 3 | 48 | 72 | 8 | 3 | 22 | | 24 | 4 | 48 | 96 | 8 | 3 | 23 | | 32 | 3 | 64 | 96 | 8 | 3 | 26 | | 32 | 4 | 64 | 128 | 8 | 3 | 27 | | 48 | 2 | 96 | 96 | 8 | 3 | 28 | | 48 | 3 | 96 | 144 | 8 | 3 | 29 | | 64 | 2 | 128 | 128 | 8 | 3 | 32 | | 64 | 3 | 128 | 192 | 8 | 3 | 33 | | 64 | 4 | 128 | 256 | 8 | 3 | 34 | **轮函数**：由模加法、按位旋转和异或（XOR）组成。在第 i 轮，将 2n 位输入 (x2i + 1, x2i) 更新： 1. 将 x2i + 1 的位循环右移 α 位，然后与 x2i 进行模 2n 加法，即 x2i + 1 = x2i + 1 + x2i。 2. 将 n 位轮密钥与 x2i + 1 异或，同时将 x2i 的位循环左移 β 位。 3. 将 x2i + 1 与 x2i 异或，完成轮函数更新。 **密钥调度**：子密钥的扩展方式与每轮的状态更新类似。通过轮函数生成第 (i + 1) 轮子密钥。 ##### 5.2 LowMC 家族 LowMC 是基于 SPN 结构的分组密码家族，旨在降低非线性门的使用，以适用于多方计算（MPC）、全同态加密（FHE）和零知识证明（ZK）等应用。其推荐实例由块大小 n、密钥大小 k、非线性层的 S 盒数量 m、允许的攻击数据复杂度 d 和轮数 r 等参数表征。 **轮函数**：加密从在 F2 上进行白化密钥加法开始，然后进行 r 次轮函数迭代，轮函数由 KeyAddition、ConstantAddition、LinearLayer 和 SboxLayer 组成。 - **SboxLayer**：采用 3 位 S 盒，仅对状态的前 3m 位进行处理。 - **LinearLayer**：是 F2 上的矩阵乘法。 - **ConstantAddition**：通过 F2 上的加法将轮常量与状态异或。 - **KeyAddition**：将密钥调度生成的 n 位轮密钥与每轮后的状态异或。 **密钥调度**：轮密钥通过与满秩随机矩阵相乘从主密钥派生。 #### 6. SPECK 的量子实现 ##### 6.1 SPECK 的量子加法器 之前的 SPECK 实现使用基于进位传播的量子加法器，Anand 等人采用不同的量子加法器改进了深度性能并节省了一个辅助量子比特。本文使用基于进位传播方法改进的 Cuccaro–Draper–Kutin–Moulton（CDKM）加法器，当 n ≥ 4 时，可应用于所有 SPECK 变体。该加法器需要一个辅助量子比特、(2n - 3) 个 Toffoli 门、(5n - 7) 个 CNOT 门、(2n - 6) 个 X 门，电路深度为 (2n + 3)。 ```python # 改进的 n 位 CDKM 加 ```