量子科技中心_量科网

在本工作中，该团队重新审视了对偶攻击与GPV陷门采样，重点关注格高斯采样项，该项往往是整体复杂度的主要瓶颈。该团队证明，通过将Wang与Ling分析Klein算法时所依据的下界与Ozols等人提出的量子拒绝采样框架相结合，可以对该采样步骤实现量子加速。具体而言，当给定对截断Klein提议分布的相干预言机访问时，该下界恰好提供了量子拒绝采样所需的逐点支配条件，从而产生一种量子过程，能以二次降低采样复杂度的方式制备截断对偶\(q\)元格高斯分布。截断半径的选择使得截断分布与完整格高斯分布之间的总变差距离可忽略不计。将这一采样器代入对偶攻击框架后，整体攻击成本估计值有所降低。在与Pouly与Shen的现代对偶攻击采用相同参数设置的情况下，该团队的估计将Kyber-512、Kyber-768和Kyber-1024的攻击成本分别降低了9位、4位和13位。该团队还报告了采用模数切换时的相应估计值。最后，通过将马尔可夫链蒙特卡洛采样器替换为量子拒绝采样算法，该团队在GPV签名过程中实现了类似的二次加速提升。