Title: A Probabilistic Computing Approach to the Closest Vector Problem for Lattice-Based Factoring Show Chinese title

Title: 基于概率计算方法的格基因式分解最邻近向量问题

Abstract: The closest vector problem (CVP) is a fundamental optimization problem in lattice-based cryptography and its conjectured hardness underpins the security of lattice-based cryptosystems. Furthermore, Schnorr's lattice-based factoring algorithm reduces integer factoring (the foundation of current cryptosystems, including RSA) to the CVP. Recent work has investigated the inclusion of a heuristic CVP approximation `refinement' step in the lattice-based factoring algorithm, using quantum variational algorithms to perform the heuristic optimization. This coincides with the emergence of probabilistic computing as a hardware accelerator for randomized algorithms including tasks in combinatorial optimization. In this work we investigate the application of probabilistic computing to the heuristic optimization task of CVP approximation refinement in lattice-based factoring. We present the design of a probabilistic computing algorithm for this task, a discussion of `prime lattice' parameters, and experimental results showing the efficacy of probabilistic computing for solving the CVP as well as its efficacy as a subroutine for lattice-based factoring. The main results found that (a) this approach is capable of finding the maximal available CVP approximation refinement in time linear in problem size and (b) probabilistic computing used in conjunction with the lattice parameters presented can find the composite prime factors of a semiprime number using up to 100x fewer lattice instances than similar quantum and classical methods. Show Chinese abstract

Abstract: 最近的向量问题（CVP）是基于格的密码学中的基本优化问题，其假设的难度支撑着基于格的密码系统的安全性。此外，Schnorr的基于格的因式分解算法将整数因式分解（当前密码系统的基础，包括RSA）转化为CVP。最近的研究探讨了在基于格的因式分解算法中包含一个启发式的CVP近似“精炼”步骤，使用量子变分算法进行启发式优化。这与概率计算作为随机算法的硬件加速器的出现相吻合，包括组合优化任务。在这项工作中，我们研究了概率计算在基于格的因式分解中CVP近似精炼的启发式优化任务中的应用。我们提出了该任务的概率计算算法设计，对“素数格”参数的讨论以及实验结果，显示了概率计算在解决CVP以及作为基于格的因式分解子程序的有效性。主要结果发现（a）这种方法能够在问题规模线性时间内找到最大可用的CVP近似精炼（b）与所提出的格参数结合使用时，概率计算可以使用比类似量子和经典方法少至100倍的格实例来找到半素数的复合素数因子。