技术摘要：针对素数幂模数的分圆陪集、隐藏子群与量子筛法

1. 问题背景与动机

学习误差问题（LWE）是后量子密码学的基石假设。虽然 Regev 建立了从 LWE 到二面体陪集问题（DCP）的量子归约，且 Brakerski 等人随后引入了扩展二面体陪集问题（EDCP）以证明其与 LWE 的等价性，但存在一个显著的结构性限制。与 DCP 不同，一般的 EDCP 并不具备精确的隐藏子群结构，因为平移集合并不构成一个子群。这一局限性阻碍了高效隐藏子群技术的直接应用，特别是对于非 2 的幂次的模数。

Bai 等人（CRYPTO 2025）最近的工作通过利用特定的 2-进理想链，实现了针对 2 的幂次模数（$q=2^t$）下 EDCP 和高斯 $S|LWE\rangle$ 的拟多项式时间量子算法。然而，将此推广到任意素数幂模数（$q=p^t$）已被证明非常困难，因为当 $q$ 不是 2 的幂次时，阶数为 $2q$ 的二面体群仅为幂零群。因此，标准的幂零群筛法（如 Imran 和 Ivanyos 的方法）无法直接应用于非 2 的幂次模数的 EDCP 或 DCP。

2. 方法论与核心构造

2.1 分圆陪集问题 (CCP)

为了克服 EDCP 在一般素数幂情况下缺乏隐藏子群结构的问题，作者引入了分圆陪集问题（Cyclotomic Coset Problem, CCP）。该问题定义在分圆环 $R_q = \mathbb{Z}_q[\zeta_p]$ 上，其中 $p$ 为素数，$q=p^t$，$\zeta_p$ 是一个本原 $p$ 次单位根。

作者定义了一个半直积群 $G_{n,q,p} = R_q^n \rtimes \mathbb{F}_p$。他们证明该群是幂零的，其幂零类为 $t(p-1)$。在该群内，他们识别出一个由 $(s, 1)$ 生成的隐藏子群 $H_s$，其中 $s$ 是秘密向量。与该子群相关的陪集态形式为：
$$|\phi_{x,s}\rangle = \frac{1}{\sqrt{p}} \sum_{j \in \mathbb{F}_p} |j\rangle |x + \lambda_j s \rangle$$
其中 $\lambda_j = \sum_{i=0}^{j-1} \zeta_p^i$。当 $p=2$ 时，此构造精确退化为标准的 DCP。

2.2 分圆环上的量子傅里叶变换 (QFT)

一个关键的技术组成部分是定义并高效实现环 $R_L = R/\pi^L R$（其中 $\pi = \zeta_p - 1$）上的量子傅里叶变换。利用域迹（field trace）和理想 $(p) = (\pi)^{p-1}$ 的 $\pi$-进分解，作者构造了一个将 CCP 样本映射到**相位态（phase states）**的 QFT。

该变换将从陪集态中恢复 $s$ 的问题转化为相位态问题（Phase-State Problem, PSP），其中秘密被编码在量子态的相位中：
$$|\psi_y\rangle = \frac{1}{\sqrt{p}} \sum_{j \in \mathbb{F}_p} \chi_y(\lambda_j s) |j\rangle$$
这里 $\chi_y$ 是环加法群的一个特征。

2.3 量子筛法算法

作者将“Simon 遇上 Kuperberg”的框架适配到分圆设置中。算法通过利用 $\pi$-进理想链迭代地降低模数层级：
$$R_q \cong R_{\pi^L} \to R_{\pi^{L-1}} \to \dots \to R_{\pi} \cong \mathbb{F}_p$$

筛法过程包括：

1. 零和搜索（Zero-Sum Search）： 给定一组带有标签 $y_i$ 的相位态样本，算法寻找一个子序列，使得 $\sum y_i \equiv 0 \pmod \pi$。这通过将基于 Imran 和 Ivanyos 方法的确定性零和搜索算法应用于模 $\pi$ 的剩余类来实现。
2. 状态组合： 通过对相应的量子态进行张量积运算并执行特定的基变换与测量，算法产生一个新的、标签位于较低环 $R_{\pi^{L-1}}$ 中的相位态样本。
3. 迭代： 重复此过程 $L-1$ 次，直到将问题简化为基于 $\mathbb{F}_p$ 的基础情况，随后可通过线性代数恢复秘密。
4. 提升（Lifting）： 一旦求得 $s \pmod p$，算法递归地求解更高次幂的 $p$，从而恢复完整的秘密 $s \in \mathbb{Z}_q^n$。

3. 核心贡献

1. 引入 CCP 与 CyLWE： 本文定义了分圆陪集问题（CCP）和分圆 LWE（CyLWE）。作者证明，对于常数 $p$，这些问题与其经典对应物（DCP 和 LWE）是等价的，并且在幂零群上具有隐藏子群结构，这与一般的 EDCP 不同。
2. 分圆 QFT 与相位态： 作者严格定义了分圆环 $R_q$ 上的 QFT，并展示了如何将 CCP 样本转换为相位态，从而能够应用筛法技术。
3. 拟多项式时间量子筛法算法： 他们提出了一种量子算法（算法 1），在提供拟多项式数量样本的前提下，以拟多项式时间（$2^{O(\log n \log q)}$）和多项式量子空间解决 CCP。
4. 对先前结果的推广： 该工作将 Bai 等人的拟多项式时间结果（受限于 $q=2^t$）推广到了任何素数幂模数 $q=p^t$。
5. 等价性证明： 论文提供了量子归约，表明：
   • 均匀 EDCP 和高斯 $S|LWE\rangle$（在素数幂模数下）可以归约为 CCP。
   • 因此，当 $q=p^t$ 时，存在求解均匀 EDCP 和高斯 $S|LWE\rangle$ 的拟多项式时间量子算法。

4. 结果与复杂度

• 复杂度： 所提算法使用多项式量子空间，以 $2^{O(\log n \log q)}$ 的时间与样本复杂度解决 CCP。
• 范围： 结果适用于任何 $q = p^t$ 的情况，其中 $p$ 是一个固定的素数。
• 归约： 论文确立了解决 CCP 可以在相同的参数约束下，以拟多项式时间解决均匀 EDCP 和高斯 $S|LWE\rangle$。

5. 意义与局限性

作者强调，尽管这项工作显著推进了对素数幂模数下格问题的量子算法理解，但它并未产生针对标准 LWE 的拟多项式时间算法。

其局限性源于如下归约链：

1. 标准 LWE 归约为 DCP（或 EDCP）。
2. DCP/EDCP 归约为 CCP。
3. CCP 求解器需要拟多项式数量的样本。

从 LWE 到 DCP/EDCP 的已知归约仅产生有限（多项式）数量的近似态。由于 CCP 求解器所需的样本数量超过了 LWE 归约所能提供的样本数量，解决标准 LWE 的整体复杂度仍然是指数级的。

因此，本文的主要贡献是理论性的：它将幂零群筛法的能力扩展到了更广泛的模数类，并为分圆环上的陪集问题提供了一个统一的框架，同时对解决标准 LWE 的直接威胁保持了审慎的态度。