技术摘要：群环中的量子单位求逆

1. 问题陈述

基于群环的公钥密码体制依赖于在群环 $R[G]$ 中求取单位 $u$ 的逆元的计算难度。其安全前提假设从公开数据中恢复 $u^{-1}$ 是困难的，特别是当 $G$ 是一个非交换群时。在近期对交换群环方案（其中量子傅里叶变换 (QFT) 使问题对角化）进行量子破解后，设计者转向了非交换平台，特别是二面体群 ($D_n$)。这种迁移是基于一种信念，即二面体隐子群问题 (HSP) 的难度将提供保护。

本文对这一前提提出了挑战。它指出，单位求逆与 HSP 是两个不同的计算问题。虽然两者都利用了广义傅里叶变换，但单位求逆并不需要从陪集态中恢复隐藏的子群——而这正是被认为在非交换群中很难的一步。核心问题在于：HSP 的难度是否与群环中单位求逆的任务相关。

2. 研究方法

本文结合了代数理论、复杂度分析和量子电路工程，旨在分离这两个问题并分析单位求逆的可行性。

• 代数分解： 核心方法依赖于 Artin–Wedderburn 定理。对于分裂域 $F$ 上的半单群代数 $F[G]$，该代数同构于矩阵代数的直和：
  $$\Phi: F[G] \cong \bigoplus_{t=1}^h M_{d_t}(F)$$
  其中 $\Phi$ 是广义傅里叶变换，$d_t$ 是不可约表示的维度。
• 算法归约： 本文证明了对单位 $u$ 求逆可以归约为以下步骤：
  1. 应用 $\Phi$ 将 $u$ 映射为矩阵元组 $(\Phi_1(u), \dots, \Phi_h(u))$。
  2. 单独对每个矩阵块求逆（这是一个标准的线性代数任务）。
  3. 应用 $\Phi^{-1}$ 来重构 $u^{-1}$。
     至关重要的是，这一过程从未形成陪集态，也未尝试恢复隐藏的子群。
• 复杂度分析： 该归约的可行性并非由交换性决定，而是由最大不可约维度 ($d_{\max}$) 和变换 $\Phi$ 的效率所控制。
• 量子实现： 作者构建了一个显式的、可逆的量子电路用于执行“相干块求逆”步骤。该电路在不使用中间测量或纠缠辅助比特泄漏的情况下，相干地对有限域矩阵进行求逆，确保整个过程保持在 BQP 复杂度类内。
• 边界分析： 本文推导出了一个精确的迹形式判据（$\det T = \pm |G|^{|G|}$），用于高效检查半单性边界。如果域的特征整除群阶（即 $p \mid |G|$），则代数不是半单的，此时 Wedderburn 分解（以及随之而来的攻击）将失效。

3. 核心贡献

概念贡献

• HSP 与求逆的分离： 本文证明了单位求逆完全通过广义傅里叶变换进行分解，并不涉及隐藏子群问题。因此，二面体 HSP 的难度（属于亚指数级）并不会转移到单位求逆任务上。
• 块维度作为主导参数： 作者确定 $d_{\max}$（最大矩阵块的大小）是决定密码分析可行性的关键参数。研究表明，交换性并不重要；具有较小 $d_{\max}$ 的非交换群（如二面体群）是脆弱的，而具有超多项式 $d_{\max}$ 的群（如对称群 $S_m$）可能仍然是困难的。

理论贡献

• 复杂度二分性：
  • 易方向（已证明）： 如果 $F[G]$ 是半单的，拥有高效的广义变换，且 $d_{\max} = \text{poly}(\log |G|)$，则单位求逆可以在多项式时间内解决（经典和量子均可）。
  • 难方向（有证据支持）： 有证据表明，当 $d_{\max}$ 为超多项式时（例如对称群），在通过输出规模分离、预言机模型查询界限以及涉及 immanant 的条件 #P-困难性结果进行分析后，单位求逆是困难的。
• 精确边界判据： 提供了一个高效可检查的见证（定理 12）用于判定半单性边界。如果迹形式的行列式（模 $p$）为零，则该方法停止。

密码分析贡献

• 对二面体安全性的证伪： 本文证明，基于二面体群环 ($F[D_n]$) 的方案在域特征不整除群阶的情况下，容易受到多项式时间量子攻击。基于二面体-HSP 难度的安全逻辑被证明与求逆任务是正交的。
• 随机预言机不变性： 本文证明，应用随机预言机变换（如 FO$\perp$）并不能恢复安全性，因为底层的陷门（单位求逆）在代数层面已被破解。攻击可以在零预言机查询的情况下恢复密钥。

工程贡献

• 相干块求逆电路： 设计并验证了一个可复用的、可逆的量子原语。它能相干地执行有限域矩阵求逆，并具备清晰的辅助比特管理。
• 可复现的制品： 本文包含一个环境锁定的软件制品，能够重新生成所有定理、图表和表格，包括攻击的寄存器级模拟。

4. 结果

• 高效求逆算法： 作者提出了一个算法（定理 7），可在 $O(|G| d_{\max}^{\omega})$ 次域运算内完成经典求逆，并在存在高效 QFT 的情况下实现多项式时间量子求逆。
• 二面体脆弱性： 对于二面体群 $D_n$，所有不可约表示的维度均满足 $d_t \le 2$。由于 $D_n$ 存在高效 QFT，单位求逆相对于输入规模是多项式时间的，这使得基于二面体的方案在上述条件下对量子对手是不安全的（推论 9）。
• 实验验证：
  • 正确性： 该算法在多种群（$D_3, D_5, D_7, S_3$）和域上的随机单位上进行了验证，实现了 100% 的精确逆元恢复成功率。
  • 性能： 基准测试显示，对于受限块，Wedderburn 块求逆方法的扩展性接近线性，显著优于稠密矩阵求逆（$O(|G|^3)$）。
  • 资源估算： 提供了容错执行的逻辑资源投影。例如，破解一个 $D_{1024}$ 实例估计需要 $\approx 2 \times 10^7$ 个物理比特，大约比破解 RSA-2048 的估算值低一个数量级。
• 幸存区间： 该攻击不适用于以下情况：
  1. 模运算区间： 当域特征整除群阶（$p \mid |G|$）时，代数不是半单的。
  2. 大块维度区间： 当 $d_{\max}$ 呈超多项式增长时（例如对称群 $S_m$），使得块求逆步骤变得难以处理。
     注：论文明确指出这些区间是“潜在的安全避风港”，但并未证明其安全性；它提出了将“激进恢复”（Radical Recovery）作为模运算情况下的一个研究方向。

5. 意义与主张

本文的主要意义在于重新定义了群环密码学的设计空间。作者认为，该领域从交换群向非交换（二面体）群的迁移，是基于对隐藏子群问题（HSP）与单位求逆这两个不同问题的混淆。

• 适度的主张： 作者谨慎地指出，他们仅证明了易方向是无条件的。关于大块维度或模运算平台是安全的说法，是以部分证据（输出规模、查询复杂度、#P-困难性）支持的猜想（猜想 17），而非证明。
• 并非提出新的硬度假设： 本文并未声称破解了某个特定的、标准化的后量子标准（许多引用的方案本身缺乏形式化归约）。相反，它证明了在这些特定代数结构下，预期的硬度假设（单位求逆）在量子计算下是不成立的。
• 实际影响： 这项工作为设计者提供了明确的清单：安全性取决于块维度和变换效率，而非交换性。它建议，凡是仅依赖于在半单、有界维度代数（包括二面体群）上进行单位求逆的方案，都不应被视为具有后量子安全性。

总而言之，本文确立了块维度而非非交换性决定了群环中单位求逆的难度。它针对一类广泛的拟议方案，提供了一种建设性的、经过验证的量子攻击，同时划定了该攻击失效的精确代数边界。