Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs

这篇论文题为《基于新样本 - 时间权衡的稀疏 LWE 和稀疏 LPN 攻击》（Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs），由印度理工学院德里分校（IIT Delhi）的 Shashwat Agrawal、Amitabha Bagchi 和 Rajendra Kumar 撰写。

该论文主要研究了稀疏学习带误差（Sparse LWE）和稀疏学习奇偶校验带噪声（Sparse LPN）问题在大模数 $q$ 下的安全性。作者扩展了 Wein 等人（2019）提出的 Kikuchi 方法，提出了两种新的攻击算法，建立了样本复杂度（Sample Complexity）与时间复杂度（Time Complexity）之间的新权衡关系。

以下是该论文的详细技术总结：

1. 研究背景与问题定义

• LWE 与 LPN：学习带误差（LWE）和学习奇偶校验带噪声（LPN）是现代密码学的核心困难假设。LWE 广泛用于构建同态加密等高级密码原语，而 LPN 则因其高效性受到关注。
• 稀疏性（Sparsity）：为了平衡安全性与效率，研究者考虑了稀疏版本的问题，即系数向量 $a$ 中只有 $k$ 个非零元素（$k \ll n$）。稀疏性可以显著提高密钥生成和计算的效率（约 $O(n/k)$ 倍）。
• 现有挑战：
  • 对于 $q=2$ 的情况，已有基于 Kikuchi 图（Kikuchi Graph）的算法（如 Wein et al. 2019, Gupta et al. 2026）给出了较好的样本 - 时间权衡。
  • 对于大模数 $q$（$q$ 是安全参数的多项式），稀疏 LWE/LPN 的安全性尚未被充分探索。
  • 近期 Jain, Lin, Saha (2024) 提出了稀疏 LWE 的两种攻击（核中的稀疏向量攻击、稠密子矩阵攻击），但分析表明在 $k \ge \Omega(\log n)$ 且样本数为多项式时，这些攻击需要指数时间。他们 conjecture（猜想）稀疏 LWE 在此参数下与标准 LWE 一样困难。
• 本文目标：针对大模数 $q$，提供更细粒度的复杂度分析，打破或验证上述猜想，并给出新的样本 - 时间权衡。

2. 核心方法论：Kikuchi 图的推广

论文的核心是将 $q=2$ 时的 Kikuchi 方法推广到 $q > 2$ 的情况。主要步骤包括：

1. 线性方程转乘积方程：
   • 将 $Z_q$ 上的线性方程 $a \cdot s = b$ 转化为复数域上的乘积方程。利用 $q$ 次单位根 $\omega_q = e^{2\pi i / q}$，将方程重写为 $\prod x_j^{a_j} = b'$，其中 $b' \in \Omega_q = \{1, \omega_q, \dots, \omega_q^{q-1}\}$。
2. 升维（Lifting）：
   • 将 $k$-稀疏方程转化为 $2$-稀疏方程组。
   • 对于 $q=2$，变量空间是 $[n]$ 的 $l$-子集（$l \ge k/2$）。
   • 对于 $q>2$，由于需要编码非零系数的值，变量空间扩展为 $([n] \times [q])$ 的 $l$-子集，即维度为 $\binom{n}{l} \times q^l$。
3. 构建 Kikuchi 图（Kikuchi Graph）：
   • 构建一个有向图，顶点代表上述升维后的子集。
   • 如果两个顶点 $T_1, T_2$ 的“广义对称差”对应于原方程的一个约束 $(S, b)$，则在 $T_1$ 和 $T_2$ 之间添加边。
   • 为了处理 $q>2$ 的不对称性，作者构造了有向图，并添加反向边以确保图的邻接矩阵是 Hermitian 的（用于谱方法）且入度等于出度（用于闭回路方法）。

3. 两种攻击算法

论文提出了两种基于 Kikuchi 图的区分算法（区分随机实例与“种植”实例）：

A. 谱方法 (Spectral Method)

• 原理：计算 Kikuchi 图邻接矩阵的谱范数（Spectral Norm）。
  • 随机实例：谱范数的期望接近 0。
  • 种植实例：谱范数的期望正比于平均度数 $\Delta$ 和噪声分布的矩 $\rho$。
• 技术细节：
  • 利用 Matrix Bernstein 不等式 来界定谱范数的尾部概率，区分随机和种植情况。
  • 不需要假设 $q$ 是素数，适用于任意噪声分布（只要噪声集中在 0 附近且对称）。
• 结果：
  • 时间复杂度：$\tilde{O}\left( \binom{n}{l} q^l \right)$。
  • 样本复杂度：$m \ge \tilde{O}\left( \left(\frac{n}{l}\right)^k \right)$ 或 $\tilde{O}\left( \left(\frac{qn}{l}\right)^{k/2} \right)$（取决于 $q$ 的大小）。
  • 量子加速：该方法存在量子加速版本，时间复杂度可降至 $\tilde{O}\left( \left(\frac{n}{l} q^l \right)^{1/4} \right)$（基于 Schmidhuber et al. 的工作）。

B. $q$-ary Cover 方法 (Closed Walk Method)

• 原理：在 Kikuchi 图中寻找非平凡的闭回路（Closed Walks），这些回路对应于原实例的 $q$-ary cover（即约束的线性组合，使得左侧系数之和模 $q$ 为 0）。
• 技术细节：
  • LPN 情况：利用闭回路构造一个多项式，分析其值的抗集中性（Anti-concentration）。在随机情况下，多项式值集中在 0 附近；在种植情况下，由于噪声的特殊分布，值会显著偏离。
  • LWE 情况：利用噪声的有界性（Bounded Error）。对于找到的 $q$-ary cover $c$，计算 $|c^T \beta|$。在种植情况下，该值受噪声界限制；在随机情况下，该值均匀分布。
• 限制：
  • 需要 $q$ 是素数。
  • 对于 LWE，需要 $q$ 足够大（$q \gg r(l \log n)^{3/2}$）。
• 优势：
  • 在 $l \gg k$ 时，相比谱方法有近二次加速（时间复杂度约为谱方法的平方根）。
  • 适用于左侧向量（LHS）任意分布的情况（不要求均匀分布）。

4. 主要贡献与结果

1. 新的样本 - 时间权衡：

   • 论文给出了针对稀疏 LWE/LPN 的算法，参数 $l$ ($k/2 \le l \le n$) 用于在样本复杂度和时间复杂度之间进行权衡。
   • 定理 1.1 (LWE)：存在算法在 $\tilde{O}(\binom{n}{l} q^l)$ 时间内解决决策性问题，样本需求为 $m \ge \binom{n}{l} q^l$ 量级。
   • 定理 1.2 (LPN)：存在算法在 $\tilde{O}(\binom{n}{l} q^l)^{1/2+\epsilon}$ 时间内解决决策性问题（$q$-ary cover 方法），样本需求类似。

2. 对 Jain et al. (2024) 猜想的验证：

   • Jain 等人猜想：当 $k = \Omega(\log n)$ 且样本数 $m = \text{poly}(n)$ 时，稀疏 LWE 与标准 LWE 一样困难。
   • 本文结果表明：如果允许时间复杂度为 $\exp(\delta n)$（$\delta$ 任意小），则只需多项式或略多于多项式的样本即可破解。
   • 具体而言，如果 $k = O(\log n / \log \log n)$，多项式样本足以在亚指数时间内破解；如果 $k = O(\log n)$，则需要 $(\log n)^{O(\log n)}$ 样本。这表明 Jain 等人的猜想在严格的多项式时间假设下是成立的，但在亚指数时间假设下，稀疏 LWE 的困难性边界被更精确地刻画了。

3. 与现有工作的对比：

   • 相比 Wein et al. (2019) 和 Gupta et al. (2026) 的 $q=2$ 结果，本文成功推广到了大模数 $q$。
   • 相比 Manohar (2024) 的博士论文工作，本文的构造更通用（不要求 $q$ 为素数，样本复杂度要求更低，特别是对于大 $q$）。

5. 意义与影响

• 密码学安全性评估：为基于稀疏 LWE/LPN 构建的密码方案（如轻量级同态加密）提供了更精确的安全性边界。设计者需要谨慎选择参数 $k$ 和 $q$，以避免落入本文攻击的有效范围。
• 算法理论进展：展示了如何将谱方法和组合方法（闭回路）有效地推广到高维、大模数的代数结构上，特别是处理 $q$-ary cover 和 Kikuchi 图的有向化构造。
• 权衡分析：清晰地展示了在稀疏 LWE/LPN 问题中，通过增加样本量可以显著降低时间复杂度，反之亦然，为参数选择提供了理论依据。

总结

该论文通过推广 Kikuchi 方法，解决了大模数下稀疏 LWE 和 LPN 的区分问题。提出的谱方法和 $q$-ary cover 方法分别在不同参数区域（如 $q$ 是否为素数、噪声类型、$l$ 与 $k$ 的关系）提供了最优或次优的样本 - 时间权衡。这些结果不仅推进了对稀疏 LWE 困难性的理解，也对相关密码原语的安全性分析具有重要参考价值。