No exponential quantum speedup for $\mathrm{SIS}^\infty$ anymore

本文针对 Chen、Liu 和 Zhandry 于 2021 年提出的平均情况 $\ell_\infty$-短整数解（$\mathrm{SIS}^\infty$）问题的量子加速算法，提出了针对该问题及更广义约束整数解问题的有效经典算法，从而证明不再存在指数级量子加速。

要点

这篇论文讲述了一个关于**“破解密码难题”**的有趣故事，但它不是关于黑客攻击，而是关于数学家和计算机科学家如何发现：以前被认为只有超级量子计算机才能快速解决的问题，其实用普通的经典计算机（也就是我们现在的电脑）也能轻松搞定，甚至更快！

为了让你轻松理解，我们可以把这篇论文里的核心概念想象成一场**“寻找完美拼图”**的游戏。

1. 背景：一场看似不可能的拼图游戏

想象你有一大堆形状各异的积木（这些积木代表数学中的“向量”），你的目标是把它们拼在一起，让它们的总和正好抵消，变成“零”（也就是 $Hx=0$）。

• 规则很苛刻：你只能用特定形状的积木（比如只能用红色或蓝色的积木，或者只能用特定大小的积木）。
• 以前的认知：在 2021 年，有一群顶尖科学家（Chen, Liu, Zhandry）发现，在某种特定的、非常复杂的规则下，用量子计算机（一种理论上拥有超强算力的未来机器）可以像变魔术一样，瞬间找到这个“零和”的拼图方案。而用普通电脑，可能需要等到宇宙毁灭都算不出来。
• 为什么这很重要？ 因为很多未来的“防量子密码系统”（比如保护银行转账、国家机密的加密技术）就是基于“普通电脑找不到这个拼图方案”这个假设建立的。如果普通电脑也能找到，那些密码就不安全了。

2. 这篇论文的突破：我们找到了“作弊码”

这篇论文的作者（Robin Kothari, Ryan O'Donnell, Kewen Wu）说：“等等，我们不需要量子计算机！我们找到了一个更聪明的普通算法，不仅能找到拼图，而且比那个量子算法还要快！”

他们是怎么做到的呢？用了两个核心技巧，我们可以用生活化的比喻来解释：

技巧一：“减半魔法” (The Halving Trick)

想象你在找一堆乱糟糟的线头，想要把它们打结变成零。

• 旧方法：你可能需要把线头分成两半，分别处理，然后再合起来。如果线头很多，这个过程会非常慢，而且随着线头变多，难度会指数级上升。
• 新方法：作者发现了一个巧妙的数学规律。他们不需要把问题完全拆开，而是像**“切蛋糕”**一样。每切一刀，问题的难度就减半。通过这种“切半”的策略，他们发现即使积木（参数）的数量变得非常巨大，普通电脑也能在合理的时间内把它们拼好。这就像是你发现了一个捷径，不用把整座山搬走，只要把山削平一半，剩下的就好办了。

技巧二：“降维打击” (Dimension Reduction)

想象你在一个巨大的迷宫里找出口。

• 旧方法：你可能需要在迷宫的每一个路口都试一遍，因为你觉得每个方向都可能是对的。
• 新方法：作者发现，其实很多路是“死胡同”或者“重复路”。他们发明了一种方法，可以把这个巨大的 3D 迷宫压扁成 2D，甚至 1D 的平面。在平面上找路当然比在迷宫里容易多了！通过这种“降维”操作，他们把原本需要处理的海量数据，压缩成了计算机可以轻松处理的小数据。

3. 这意味着什么？（后果与影响）

这篇论文的结论非常震撼，可以总结为三点：

1. 量子优势消失了：以前大家以为在某个特定参数范围内，量子计算机能比经典计算机快亿万倍（指数级加速）。现在作者证明，这种“指数级加速”并不存在。普通电脑完全可以做到，而且效率更高。
2. 密码学需要重新评估：
   • 有些基于“短整数解”（SIS）问题的加密方案（比如 NIST 正在标准化的某些后量子密码），如果它们的参数设置得不够“大”（也就是积木不够多），那么它们可能并不安全，因为普通电脑能轻易破解。
   • 但这并不意味着所有密码都完了。作者也指出，如果参数设置得足够极端（比如积木数量是维度的平方级），普通电脑还是很难破解的。这就像告诉密码设计师：“嘿，别偷懒，把锁做得更复杂一点，现在的‘减半魔法’和‘降维打击’还不够破解它。”
3. 数学的胜利：这展示了人类数学直觉的强大。有时候，我们以为需要“魔法”（量子计算）才能解决的问题，其实只是因为我们还没找到那个巧妙的“数学钥匙”。

4. 总结：一场“去魅”之旅

如果把量子计算机比作**“拥有透视眼的超级侦探”，以前大家以为只有他能看清迷宫里的秘密。
这篇论文就像是一群“老练的侦探”**站出来说：“其实不需要透视眼！只要我们知道迷宫的构造规律（数学结构），用普通的放大镜（经典算法）和正确的地图（新算法），我们不仅能看清，还能跑得比超级侦探更快！”

一句话总结：
这篇论文打破了“量子计算机在特定数学问题上拥有绝对统治力”的神话，证明了普通电脑通过巧妙的数学技巧，也能高效解决这些难题，从而迫使密码学家们必须重新审视和加固他们的安全防线。

技术摘要

这篇论文题为《No exponential quantum speedup for SIS∞ anymore》（SIS∞不再具有指数级量子加速），由 Robin Kothari、Ryan O'Donnell 和 Kewen Wu 撰写。论文针对 Chen、Liu 和 Zhandry (CLZ) 在 2021 年提出的关于 $\ell_\infty$-Short Integer Solution ($SIS_\infty$) 问题的量子算法，提出了高效的经典算法，从而证明了在该参数范围内不存在指数级的量子加速。

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

1. 研究背景与问题定义

背景：

• SIS 问题：短整数解（Short Integer Solution, SIS）问题是后量子密码学的基础，许多候选方案（如 Dilithium, Wave）的安全性依赖于其困难性。
• CLZ 的突破 (2021)：Chen, Liu, 和 Zhandry 提出了一种高效的量子算法，用于解决平均情况下的 $SIS_\infty$ 问题（即在 $\ell_\infty$ 范数下的短解）。该算法在特定参数范围（$m \ge C q^4 \log q \cdot n^k$）内有效，且使用了不同于传统隐藏子群问题（HSP）的新颖技术（基于 Regev 的归约和量子解码）。
• 动机：由于该问题结构简单且无特殊结构，CLZ 的工作曾被视为可能发现新的指数级量子加速的候选者。

核心问题定义：

• $SIS_\infty$ 问题：给定矩阵 $H \in \mathbb{F}_q^{n \times m}$，寻找非零向量 $x \in \mathbb{F}_q^m$，使得 $Hx = 0$ 且 $\|x\|_\infty \le s$（即 $x$ 的分量绝对值较小）。
• 约束整数解 (CIS)：更一般的问题，要求 $x$ 的分量属于特定集合 $A \subseteq \mathbb{F}_q$。
• 子集和问题 ($F_q^n$-Subset-Sum)：$SIS_\infty$ 的特例，要求 $x \in \{0, 1\}^m$。

2. 核心方法论

作者提出了一系列经典的确定性算法，通过改进线性代数技巧和组合数学方法，解决了上述问题。主要技术包括：

2.1 减半技巧 (The Halving Trick)

• 灵感来源：受 Imran 和 Ivanyos (II24) 工作的启发，但进行了重大改进。
• 原理：如果存在一个非平凡的 $(\pm h)$-零和（即系数在 $[-h, h]$ 之间），可以通过构造“可约向量”（Reducible Vector），将解的权重（系数范围）减半，即从 $(\pm h)$ 降至 $(\pm \lfloor h/2 \rfloor)$。
• 关键改进：II24 的方法在 $m$ 的依赖关系中引入了 $q$ 的因子，导致 $q$ 很大时效率低下。本文通过更精细的维度缩减和稀疏性分析，消除了 $m$ 对 $q$ 的依赖，使得算法在 $q$ 指数级大于 $n$ 时依然高效。

2.2 广义归约与树状结构 (General Reductions & Tree Structures)

• 超越减半：为了处理更一般的参数（不仅仅是 $k$ 为 2 的幂次），作者在第 4 节提出了更通用的归约方法。
• 可约向量构造：定义 $(H \to H')$-可约向量，允许将系数集合 $H$ 划分为多个部分，并利用排列（Permutations）和行列式性质的抵消机制，将高权重的零和转化为低权重的零和。
• 树状算法：构建深度为 $k+1$ 的树，递归地应用零和算法，将问题分解为更小的子问题，最终在单次迭代中完成归约，避免了多次迭代带来的指数级开销。

2.3 算术组合学工具

• 利用算术组合学中的结果（如 Lev 的定理、Szemerédi 定理的量化版本），证明在允许系数集合 $A$ 足够大时，必然包含长算术级数（AP）或特定的对称结构（如 $\pm x, 0, \pm y$）。
• 这些结构保证了可以通过仿射变换（平移和缩放）将任意允许集合 $A$ 映射到算法已知的标准形式（如区间或对称集），从而应用上述归约算法。

3. 主要贡献与结果

作者针对 $SIS_\infty$、$F_q^n$-Subset-Sum 和 CIS 问题，给出了多项式时间的经典确定性算法，其样本复杂度（所需向量数 $m$）显著优于 CLZ 的量子算法。

3.1 针对 $SIS_\infty$ 的结果

• CLZ 量子算法：需要 $m \ge C q^4 \log q \cdot n^k$。
• 本文经典算法：
  • 对于任意常数 $k \ge 2$，当 $m \ge C n^k$ 时，即可找到解。
  • 优势：
    1. 去除了 $q$ 的依赖：$m$ 不再随 $q$ 的多项式增长，即使 $q$ 是 $n$ 的指数级，算法依然有效。
    2. 更严格的“短”定义：能处理更小的 $s$（例如 $s \approx q/2k$），而 CLZ 需要更大的 $s$。
    3. 最坏情况：算法在最坏情况下（而非仅平均情况）均有效。
    4. 确定性：算法是确定性的，而非概率性的。

3.2 针对 $F_q^n$-Subset-Sum 的结果

• CLZ 量子算法：平均情况下需要 $m \ge C n^{q-1}$。
• 本文经典算法：平均情况下需要 $m \ge C n^{\lceil q/2 \rceil}$。
• 优势：指数从 $q-1$ 降低到了 $q/2$，且算法是确定性的。

3.3 针对 CIS (Constrained Integer Solution) 的结果

• CLZ 量子算法：$m \ge C q^4 \log q \cdot n^k$。
• 本文经典算法：
  • 当 $q$ 很大时，$m \ge C \log q \cdot n^2$。
  • 一般情况，$m \ge C \log q \cdot n^{k-1}$（对于 $k \ge 3$）。
• 优势：在几乎所有参数设置下，$n$ 的指数依赖关系都优于或等于量子算法，且完全去除了 $q$ 的高次多项式依赖。

4. 结果对比总结表

问题类型	CLZ (量子) 样本复杂度 $m$	本文 (经典) 样本复杂度 $m$	改进点
$A$-CIS (平均情况)	$C q^4 \log q \cdot n^k$	$C \log q \cdot n^k$ (一般 $q$)	去除 $q^4$ 依赖，降低 $n$ 指数
$F_3^n$-Subset-Sum (最坏情况)	$C n^2$ (平均)	$C n^2/3$ (最坏)	最坏情况有效，指数更小
$F_q^n$-Subset-Sum (平均)	$C n^{q-1}$	$C n^{\lceil q/2 \rceil}$	指数从 $q-1$ 降至 $q/2$
$SIS_\infty$ (最坏情况)	$C q^4 \log q \cdot n^k$	$C n^k$	去除 $q$ 依赖，最坏情况有效

5. 意义与影响

1. 否定指数级量子加速：论文证明了 Chen-Liu-Zhandry 提出的 $SIS_\infty$ 量子算法所依赖的参数范围，实际上可以通过高效的经典算法解决。因此，在该问题上不存在指数级的量子加速。
2. 后量子密码学安全性：
   • 虽然本文算法要求 $m \ge \Omega(n^2)$（即向量数量远大于维度），而实际密码系统（如 Dilithium, Wave）通常设置 $m \approx 2n$，因此不会直接破解现有的 NIST 后量子密码标准。
   • 然而，这一结果消除了对该特定参数区域存在“意外”量子加速的担忧，并表明在 $m$ 较大时，经典计算机比量子计算机更具优势。
3. 算法技术突破：
   • 提出的“减半技巧”及其推广（广义归约、树状结构）为处理线性方程组中的稀疏解和约束解问题提供了新的强大工具。
   • 展示了经典算法在处理看似需要量子解码的问题时，可以通过巧妙的组合数学和线性代数技巧实现超越。
4. 对其他问题的启示：
   • 论文讨论了 Yamakawa-Zhandry 问题和 OPI (Optimal Polynomial Intersection) 问题。虽然本文未能完全去量子化这些问题（主要因为它们的 $m=O(n)$ 且集合 $A$ 无结构），但指出了 $m$ 的大小是区分经典与量子优势的关键因素。

结论

这篇论文通过设计高效的经典确定性算法，成功“去量子化”（Dequantize）了 Chen, Liu, 和 Zhandry 在 $SIS_\infty$ 及相关问题上的工作。它表明，在 $m$ 足够大（$m \ge \Omega(n^2)$）的参数范围内，经典计算机不仅能解决这些问题，而且在样本复杂度和运行时间上甚至优于之前的量子算法。这消除了该特定问题作为量子优势候选者的可能性，并丰富了经典算法在格密码和组合数学领域的工具箱。