arXiv:2509.12341quant-phcs.CL2025-09被引 1

提出精确采样方法,提升量子格算法后处理效率与准确性

Exact Coset Sampling for Quantum Lattice Algorithms

  • 用残差测量和相位抵消替代原复杂步骤
  • 在特定条件下实现共振概率趋近1,结果均匀分布于对偶超平面
  • 适用于量子格密码分析,无需完整偏移信息

我们重新审视陈(2024)提出的Karst-wave量子格算法在学习误差(LWE)参数下的后处理阶段。给定传输记录 $E$,第7步后的坐标态在 $(/mathbb{Z}_M)^n$ 上支持于仿射网格线 $\{\, jΔ+ v^{\ast}(E) + M_2 k \bmod M : j \in \mathbb{Z},\ k \in \mathcal{K} \,\}$,其中 $Δ= 2D^2 b$,$M = 2M_2 = 2D^2 Q$,$Q$ 为奇数。振幅包含二次Karst-wave啁啾 $\exp(-2πi j^2 / Q)$ 及未知的运行相关偏移 $v^{\ast}(E)$。我们证明,陈的第8-9步可被单个精确后处理程序替代:测量确定性残差 $τ:= X_1 \bmod D^2$,获取运行局部类 $v_{1,Q} := v_1^{\ast}(E) \bmod Q$ 作为显式辅助信息,施加依赖于 $v_{1,Q}$ 的对角二次相位以抵消啁啾,再对坐标寄存器应用 $\mathrm{QFT}_{\mathbb{Z}_M}^{\otimes n}$。该过程无需完整偏移 $v^{\ast}(E)$。在前段附加条件AC1-AC5下,测得的傅里叶结果 $u \in \mathbb{Z}_M^n$ 满足共振 $\langle b, u \rangle \equiv 0 \pmod Q$ 的概率为 $1 - o(1)$。此外,在共振条件下,约化结果 $u \bmod Q$ 在对偶超平面 $H = \{\, v \in \mathbb{Z}_Q^n : \langle b, v \rangle \equiv 0 \pmod Q \,\}$ 上恰好均匀分布。

原文摘要 · Abstract (English)

We revisit the post-processing phase of Chen's Karst-wave quantum lattice algorithm (Chen, 2024) in the Learning with Errors (LWE) parameter regime. Conditioned on a transcript $E$, the post-Step 7 coordinate state on $(\mathbb{Z}_M)^n$ is supported on an affine grid line $\{\, jΔ+ v^{\ast}(E) + M_2 k \bmod M : j \in \mathbb{Z},\ k \in \mathcal{K} \,\}$, with $Δ= 2D^2 b$, $M = 2M_2 = 2D^2 Q$, and $Q$ odd. The amplitudes include a quadratic Karst-wave chirp $\exp(-2πi j^2 / Q)$ and an unknown run-dependent offset $v^{\ast}(E)$. We show that Chen's Steps 8-9 can be replaced by a single exact post-processing routine: measure the deterministic residue $τ:= X_1 \bmod D^2$, obtain the run-local class $v_{1,Q} := v_1^{\ast}(E) \bmod Q$ as explicit side information in our access model, apply a $v_{1,Q}$-dependent diagonal quadratic phase on $X_1$ to cancel the chirp, and then apply $\mathrm{QFT}_{\mathbb{Z}_M}^{\otimes n}$ to the coordinate registers. The routine never needs the full offset $v^{\ast}(E)$. Under Additional Conditions AC1-AC5 on the front end, a measured Fourier outcome $u \in \mathbb{Z}_M^n$ satisfies the resonance $\langle b, u \rangle \equiv 0 \pmod Q$ with probability $1 - o(1)$. Moreover, conditioned on resonance, the reduced outcome $u \bmod Q$ is exactly uniform on the dual hyperplane $H = \{\, v \in \mathbb{Z}_Q^n : \langle b, v \rangle \equiv 0 \pmod Q \,\}$.

量子算法格密码后处理

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。