量子科技中心_量科网

格点上的离散高斯采样是格基密码学中的一个基本问题。它既出现在数字签名等基础密码原语中，也是解决困难格问题的重要密码分析基础模块。本文提出了一种基于量子拒绝采样技术的量子算法，其复杂度在渐近意义上比 [Wang & Ling, IEEE Trans. Inf. Theory 2019] 中的经典算法快二次方。该采样器输出一个量子态，既可以测量以获得所需分布，也可以直接用于其他量子算法。基于此，研究人员推导出两个版本的量子对偶攻击，改进了 [Pouly & Shen, EUROCRYPT 2024] 中的先前方案。这两个版本不可比较，各有优势（速度与内存需求不同）。第二个版本尤其值得关注，因为它仅需要多项式规模的经典和量子内存，排除了离散高斯采样器预处理步骤中使用的经典内存。该量子离散高斯采样器还可用于加速 [Bollauf, Pouly & Shen, ePrint 2026/225] 中求解任意范数下的短整数解问题的算法。