Enhancing the Scalability and Memory Usage of Hashsieve on Multi-core CPUs
Enhancing the Scalability and Memory Usage of Hashsieve on Multi-core CPUs
复制标题
增强 Hashsieve 在多核 CPU 上的可扩展性和内存使用率
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
C. Bischof
中科院分区：
文献类型：
--
作者：
Artur Mariano;C. Bischof
最短向量问题(SVP)是格密码学和密码分析中的一个关键问题。虽然密码界从理论上积累了大量关于SVP解算器的知识，但这些算法的实际性能通常还没有被很好地理解。这种知识上的差距给密码学家带来了许多挑战，他们经常面临的算法在实践中的表现比理论上预期的要差。这是一个问题，因为最好的算法的渐近复杂性在密码系统的构造中起着关键作用，但在这个过程中只考虑实用的、有效的算法。因此，如果人们不能在实践中充分挖掘理论上强大的算法的潜力，那么高效的算法就可能被排除在外，并且在构造密码系统时会做出错误的假设。在本文中，我们进一步填补了这一空白，通过对HashSieve的计算分析，提供了迄今为止最实用的筛选SVP求解器，并展示了它的性能如何在实践中得到提高。为此，我们回顾了随机数的并行生成、内存分配和内存访问模式。通过使用可扩展的随机采样、对象内存池、可扩展的内存分配器和积极的内存预取，我们能够根据格的维度将HashSieve的当前最佳实现提高3倍和4倍，并创造了HashSieve算法的新记录，从而缩小了其理论复杂性与实际性能之间的差距。
The Shortest Vector Problem (SVP) is a key problem in lattice-based cryptography and cryptanalysis. While the cryptography community has accumulated a vast knowledge of SVP-solvers from a theoretical standpoint, the practical performance of these algorithms is commonly not well understood. This gap in knowledge poses many challenges to cryptographers, who are oftentimes confronted with algorithms that perform worse in practice then expected from theory. This is a problem because the asymptotic complexity of the best algorithms plays a key role in the construction of cryptosystems, but only practically appealing, validated algorithms are accounted for in this process. Thus, if one cannot extract the full potential of theoretically strong algorithms in practice, efficient algorithms might be ruled out and wrong assumptions are made when constructing cryptosystems. In this paper, we take a step forward to fill this gap, by providing a computational analysis of HashSieve, the most practical sieving SVP-solver to date, and showing how its performance can be enhanced in practice. To this end, we revisit the parallel generation of random numbers, memory allocation and memory access patterns. Employing scalable random sampling, object memory pools, scalable memory allocators and aggressive memory prefetching, we were able to improve the best current implementation of HashSieve by factors of 3x and 4x, depending on the lattice dimension, and set new records for the HashSieve algorithm, thereby shrinking the gap between its theoretical complexity and its performance in practice.