RS: Thijs Laarhoven, Artur Mariano: The theory and practice of HashSieve - Part I and II

Start date:15. October 2015
Start time:13:30 Uhr
End time:15:00 Uhr
Organizer:Christian Bischof, P1
Speaker:Thijs Laarhoven (TU Eindoven, Netherlands ) & Artur Mariano (CROSSING P1)
Location:CASED 5.3.01

Talk 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.


Short Bio:



Talk 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:

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.


Afterwards talk and cake with and from Professor Bischof!


A A A | Drucken Print | Impressum Impressum | Sitemap Sitemap | Kontakt Contact | Website Analysis: More Information
zum Seitenanfangzum Seitenanfang