Parallel Improved Schnorr-Euchner Enumeration SE++ for the CVP and SVP
Parallel Improved Schnorr-Euchner Enumeration SE++ for the CVP and SVP
复制标题
CVP 和 SVP 的并行改进 Schnorr-Euchner 枚举 SE
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
E. Agrell
中科院分区：
文献类型：
--
作者：
Fábio Correia;Artur Mariano;A. Proença;C. Bischof;E. Agrell
最近向量问题（CVP）和最短向量问题（SVP）是基于格密码分析中的主要问题，因为它们是许多基于格密码系统安全性的基础。尽管这些问题很重要，但只有少数几个CVP求解器是公开的，而且它们的可扩展性从未被研究过。本文提出了一种可扩展的实现基于枚举的CVP求解器的多核，它可以很容易地适应解决SVP。特别是，当求解50维网格上的CVP时，在某些情况下，它在多达8个核心上实现了超线性加速，在16个核心上实现了几乎线性加速。我们的研究结果表明，基于枚举的CVP求解器可以有效地并行化为基于枚举的求解器的SVP，基于比较与最先进的SVP求解器。此外，我们表明，我们可以优化我们的求解器的SVP变体，使其比迄今为止最快的基于枚举的SVP求解器快35%-60%。
The Closest Vector Problem (CVP) and the Shortest Vector Problem (SVP) are prime problems in lattice-based cryptanalysis, since they underpin the security of many lattice-based cryptosystems. Despite the importance of these problems, there are only a few CVP-solvers publicly available, and their scalability was never studied. This paper presents a scalable implementation of an enumeration-based CVP-solver for multi-cores, which can be easily adapted to solve the SVP. In particular, it achieves super-linear speedups in some instances on up to 8 cores and almost linear speedups on 16 cores when solving the CVP on a 50-dimensional lattice. Our results show that enumeration-based CVP-solvers can be parallelized as effectively as enumeration-based solvers for the SVP, based on a comparison with a state of the art SVP-solver. In addition, we show that we can optimize the SVP variant of our solver in such a way that it becomes 35%-60% faster than the fastest enumeration-based SVP-solver to date.