The theory and practice of HashSieve – Part I and II

15.10.2015, 13:00 – 15:00

2015/10/15 13:00-15:00

Speaker: Thijs Laarhoven, Artur Mariano | Location: Mornewegstraße 32 (S4|14), Room 5.3.01, Darmstadt

Organizer: Christian Bischof

Abstract Part I

Thijs Laarhoven: The theory and practice of HashSieve

By replacing the brute-force list search in sieving algorithms with angular locality-sensitive hashing, we get both theoretical and practical speed-ups for finding shortest vectors in lattices. Optimizing for time, we obtain a heuristic time and space complexity for solving SVP of 2^(0.3366n). Preliminary experiments show that the proposed HashSieve algorithm already outperforms the GaussSieve in low dimensions, and that the practical increase in the space complexity is much smaller than the asymptotic bounds suggest. Using probing we show how we can further reduce the space complexity at the cost of slightly increasing the time complexity.

Abstract Part II

Artur Mariano: The theory and practice of HashSieve

We assess the practicability of HashSieve on multi-core shared memory systems. We devised a parallel implementation that scales well, and is based on a probable lock-free system to handle concurrency. The probable lock-free system, implemented with spin-locks and compare-and-swap operations, acts, likely, as a lock-free mechanism, since threads spin only when strictly required and chances are that they are not required to spin, because resource contention is very low. With our implementation, we were able to solve the SVP on an arbitrary lattice in dimension 96, in less than 17.5 hours, using 16 physical cores. The least squares fit of the execution times of our implementation, in seconds, lies between 2(0.32n−15) or 2(0.33n−16), which indicates that sieving algorithms are indeed way more practical than believed.

Short Bio

Website of Thijs Laarhoven.

Artur Mariano graduated from the University of Minho, Braga, Portugal, in 2010 (BSc) and 2012 (MSc). As part of his MSc, he did a curricular research internship at the University of Texas at Austin, Texas, USA, sponsored by the UTAustin|Portugal program. Currently, he is a 4th-year PhD candidate at the Institute for Scientific Computing (TUDarmstadt), where he works in high-performance lattice-based cryptanalysis.