格问题的量子过滤：QFT 对偶性、LWE-like States 与参数边界

格上的 shortest/closest vector 问题支撑后量子密码。一般 SVP/CVP 没有已知多项式量子算法；Chen--Liu--Zhandry 的突破针对特定 average-case SIS、LWE 与 extrapolated dihedral coset 参数。核心是在 Regev-style Fourier duality 中加入非平凡量子 measurement filter，改变 error distribution，使原本差一点够用的 reduction 进入可解区域。

1. 格、对偶与基本问题

给满秩 basis \(B\in\mathbb R^{n\times n}\)：

\[ \mathcal L(B)=\{Bz:z\in\mathbb Z^n\}. \]

对偶格

\[ \mathcal L^* =\{y:\langle y,x\rangle\in\mathbb Z, \ \forall x\in\mathcal L\} =B^{-T}\mathbb Z^n. \]

SVP 找最短非零 lattice vector；CVP/BDD 给 target \(t\) 找最近 lattice point（BDD 另有 target 足够接近的 promise）。这些最坏问题的近似因子决定 hardness/密码关联。

2. QFT 为什么交换 primal 与 dual

连续 Poisson summation：周期 Gaussian

\[ \Psi_{\mathcal L,t}(x) =\sum_{v\in\mathcal L} e^{-\pi\|x-v-t\|^2/s^2} \]

的 Fourier transform 支持在 dual frequencies：

\[ \widehat\Psi(y) \propto \sum_{w\in\mathcal L^*} e^{-\pi s^2\|w\|^2} e^{-2\pi i\langle w,t\rangle} \delta(y-w). \]

宽度反转 \(s\leftrightarrow1/s\)，平移 \(t\) 变为 dual phase。离散量子寄存器上近似制备 periodic Gaussian/coset state 并做 QFT，就能在 primal nearest-vector information 与 dual short-vector/phase information 间转换。

Aharonov--Ta-Shma、Regev reductions 用这种结构把 lattice problems、dihedral coset、LWE-like samples 相互联系；参数损失来自 Gaussian tails、modulus 离散化和需要区分的 phase 精度。

3. LWE 与 quantum sample

Classical LWE sample：

\[ (a,b=\langle a,s\rangle+e\bmod q), \]

\(a\in\mathbb Z_q^n\)，secret \(s\)，error \(e\) 小。LWE-like quantum state 则保留 error/linear relation 的叠加，例如抽象写成

\[ |\psi_s\rangle \propto\sum_{a,e}\sqrt{D(e)} |a\rangle |\langle a,s\rangle+e\bmod q\rangle. \]

对 registers 做 QFT，理想无噪声线性关系会产生集中在 \(s\) 约束上的频率；error 的 characteristic function

\[ \widehat D(k)=\mathbb E_e[e^{2\pi ike/q}] \]

衰减有用频率。标准测量可能保留太多噪声或接受概率太小。

4. Quantum filter 的作用

在 error/register 上实现 POVM 或 basis rotation，使某结果的 acceptance amplitude 为函数 \(F(e)\)。条件于成功，error distribution 变为

\[ D'(e) \propto D(e)|F(e)|^2. \]

选择 \(F\) 的 Fourier profile：

  • 抑制妨碍 phase distinguishability 的 error tails；

  • 保留足够总成功概率（至少 inverse polynomial）；

  • 让后续 QFT state 接近可由已知解码/hidden-shift 子程序处理的分布。

这是本质量子步骤：filter 可在非计算基中利用 amplitudes/interference；先经典测出 \(e\) 会破坏与 secret 的相干关系。Amplitude amplification 可放大成功 filter，但其成本必须乘入。

5. 三类可解变体

Wide SIS\(_\infty\)

给

\[ A\in\mathbb Z_q^{n\times m} \]

非常宽，找非零 \(x\)：

\[ Ax=0\pmod q,\qquad \|x\|_\infty\le q/2-c \]

（常数 margin）。Bound 接近模数一半，比标准 cryptographic SIS 的“小范数”宽松得多。Filtering/QFT 生成满足 relation 的 bounded vector，wide \(m\) 保证足够熵与成功质量。

LWE with quantum samples

对 polynomial modulus 和 bounded-uniform/Laplace 等 error distributions，filter 整形成可 Fourier 解码的 state，从 polynomial 数量 quantum LWE-like states 恢复 secret。

EDCP

Extrapolated dihedral coset state 形如

\[ \sum_j\rho(j)|j\rangle|x+js\rangle. \]

过滤调整 \(j\)-window/phase resolution，稍微扩展已知 polynomial-time 参数，并通过 reduction 连到上述 LWE solver。

6. 为什么不破坏主流后量子方案

论文明确指出可解参数不在已知 worst-case-hard 标准 regime：

  • SIS bound 太接近 \(q/2\)、矩阵特别宽；

  • LWE 输入是相干 quantum states，而现实 public samples 是已测经典 pairs；

  • error/modulus family 有特定形状；

  • reductions 的 approximation factors 不覆盖主流安全参数。

因此这是首次在自然 lattice-related average-case variants 上的 quantum polynomial advantage，而不是 Shor-for-lattices。任何密码影响必须重新证明目标 scheme 能提供所需 quantum samples 与参数映射。

7. 与 decoding/DQI 的共同结构

Filtering 与 DQI 都在 Fourier-dual domain 做：

\[ \text{线性约束/coset} \xrightarrow{QFT} \text{dual syndrome/phase} \xrightarrow{measurement/decoder} \text{短误差或优解}. \]

差别是格算法的连续/模 Gaussian geometry 与 dual lattice，DQI 主要在有限域 code syndrome 上用可逆 decoder。两者都依赖“测量/解码前保持相干”。

8. 小结与习题

  • QFT 把 lattice periodicity 变成 dual-lattice frequencies，宽度反转、平移变 phase。

  • Quantum filter 通过条件 measurement 重塑 error amplitudes。

  • Polynomial algorithms 只覆盖 wide SIS\(_\infty\)、quantum-sample LWE 与特定 EDCP。

  • 标准 SVP/CVP 与主流 LWE/SIS 密码参数没有因此被破解。

  1. 对一维格 \(a\mathbb Z\) 写出 dual 与 Poisson Fourier peaks。

  2. 推导条件 filter 后 \(D'(e)\)。

  3. 比较 classical LWE sample 与 quantum LWE-like state 的信息。

  4. 解释 \(q/2-c\) 的 SIS bound 为什么远弱于 cryptographic small norm。

参考文献