量子科技中心_量科网

高维格中最短向量问题（SVP）的假设硬度是后量子密码学的基石之一。目前已知最快的启发式攻击方法是通过所谓的“筛法”。虽然这些方法在维度d上仍需要指数级时间，但比非启发式方法快得多，且其启发性假设已通过大量实验验证。k元组筛法是一种迭代方法，每次迭代输入大量特定范数的格向量，通过对k个输入向量进行加减运算，生成相同数量但范数略小的格向量。经过足够多次“筛选步骤”迭代后，即可产生短格向量。现有最快攻击（经典与量子）均采用k=2，但增大k值能降低攻击所需内存。本论文通过预处理的二级振幅放大技术——将给定格向量与邻近“中心点”关联来聚焦搜索范围，将三元组筛法的量子时间复杂度从2^(0.3098d)优化至2^(0.2846d)。该算法使用2^(0.1887d)经典比特与QCRAM比特，以及2^o(d)量子比特。当总内存限制在2^(0.1887d)时，这是目前已知最快的SVP量子算法。