Parallel Algorithms for the Shortest Vector Problem from a Discrete Perspective

Martin R. Albrecht, L ́eo Ducas, Gottfried Herold, Elena Kirshanova, Eamonn W. Postlethwaite, and Marc Stevens. The general sieve kernel and new records in lattice reduction. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology - EURO- CRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part II, volume 11477 of Lecture Notes in Computer Science, pages 717–746. Springer, 2019.

Michal Andrzejczak and Kris Gaj. A multiplatform parallel approach for lattice sieving algorithms. IACR Cryptol. ePrint Arch., 2021:973, 2020.

Yoshinori Aono and Phong Q. Nguyen. Random sampling revisited: Lattice enumeration with discrete pruning. In Jean-S ́ebastien Coron and Jesper Buus Nielsen, editors, Ad- vances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part II, volume 10211 of Lecture Notes in Computer Science, pages 65–102, 2017.

L ́aszl ́o Babai. On lov ́asz’ lattice reduction and the nearest lattice point problem. Combi- natorica, 6(1):1–13, 1986.

Joppe W. Bos, Michael Naehrig, and Joop van de Pol. Sieving for shortest vectors in ideal lattices: a practical perspective. Int. J. Appl. Cryptogr., 3(4):313–329, 2017.

O ̈zgu ̈r Dagdelen and Michael Schneider. Parallel enumeration of shortest lattice vectors. In Pasqua D’Ambra, Mario Rosario Guarracino, and Domenico Talia, editors, Euro-Par 2010 - Parallel Processing, 16th International Euro-Par Conference, Ischia, Italy, August31 - September 3, 2010, Proceedings, Part II, volume 6272 of Lecture Notes in Computer Science, pages 211–222. Springer, 2010.

TU Darmstadt. SVP Challenge. http://www.latticechallenge.org/svp-challenge/.

L ́eo Ducas, Marc Stevens, and Wessel van Woerden. Advanced lattice sieving on gpus, with tensor cores. Cryptology ePrint Archive, Report 2021/141, 2021. https://ia.cr/2021/141.

L ́eo Ducas. Shortest vector from lattice sieving: A few dimensions for free. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2018, pages 125–145, Cham, 2018. Springer International Publishing.

Masaharu Fukase and Kenji Kashiwabara. An accelerated algorithm for solving SVP based on statistical analysis. JIP, 23(1):67–80, 2015.

Nicolas Gama, Phong Q. Nguyen, and Oded Regev. Lattice enumeration using extreme pruning. In Henri Gilbert, editor, Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Tech- niques, French Riviera, May 30 - June 3, 2010. Proceedings, volume 6110 of Lecture Notes in Computer Science, pages 257–278. Springer, 2010.

C. Heckler and L. Thiele. Complexity analysis of a parallel lattice basis reduction algo- rithm. SIAM Journal on Computing, 27(5):1295–1302, 1998.

Jens Hermans, Michael Schneider, Johannes A. Buchmann, Frederik Vercauteren, and Bart Preneel. Parallel shortest lattice vector enumeration on graphics cards. In Daniel J. Bernstein and Tanja Lange, editors, Progress in Cryptology - AFRICACRYPT 2010, Third International Conference on Cryptology in Africa, Stellenbosch, South Africa, May 3-6, 2010. Proceedings, volume 6055 of Lecture Notes in Computer Science, pages 52–68. Springer, 2010.

J. Hoffstein, J. Pipher, and J.H. Silverman. An Introduction to Mathematical Cryptogra- phy. Undergraduate Texts in Mathematics. Springer New York, 2008.

Tsukasa Ishiguro, Shinsaku Kiyomoto, Yutaka Miyake, and Tsuyoshi Takagi. Parallel gauss sieve algorithm: Solving the svp challenge over a 128-dimensional ideal lattice. In Hugo Krawczyk, editor, Public-Key Cryptography – PKC 2014, pages 411–428, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.

Ravi Kannan. Improved algorithms for integer programming and related lattice problems. In David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, and Joel I. Seiferas, editors, Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 193–206. ACM, 1983.

Thijs Laarhoven and Artur Mariano. Progressive lattice sieving. In T. Lange and R. Steinwandt, editors, Post-Quantum Cryptography, Lecture Notes in Computer Science (includ- ing subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), pages 292–311, Germany, 2018. Springer. 9th International Conference on Post-Quantum Cryptography (PQCrypto 2018), PQCrypto 2018 ; Conference date: 09-04-2018 Through 11-04-2018.

Christoph Ludwig. Practical Lattice Basis Sampling Reduction. PhD thesis, Technische Universit ̈at Darmstadt Universit ̈ats, 2005.

Yoshitatsu Matsuda, Tadanori Teruya, and Kenji Kashiwabara. Efficient estimation of number of short lattice vectors in search space under randomness assumption. In Keita Emura and Takaaki Mizuki, editors, Proceedings of the 6th on ASIA Public-Key Cryp- tography Workshop, APKC@AsiaCCS 2019, Auckland, New Zealand, July 8, 2019, pages 13–22. ACM, 2019.

Yoshitatsu Matsuda, Tadanori Teruya, and Kenji Kashiwabara. Efficient estimation of number of short lattice vectors in search space under randomness assumption. In Proceed- ings of the 6th on ASIA Public-Key Cryptography Workshop, APKC ’19, pages 13–22, New York, NY, USA, 2019. ACM.

Phong Q. Nguyen and Thomas Vidick. Sieve algorithms for the shortest vector problem are practical. Journal of Mathematical Cryptology, 2(2):181–207, 2008.

Claus-Peter Schnorr. Lattice reduction by random sampling and birthday methods. In Helmut Alt and Michel Habib, editors, STACS 2003, 20th Annual Symposium on The- oretical Aspects of Computer Science, Berlin, Germany, February 27 - March 1, 2003, Proceedings, volume 2607 of Lecture Notes in Computer Science, pages 145–156. Springer, 2003.

Claus-Peter Schnorr and M. Euchner. Lattice basis reduction: Improved practical algo- rithms and solving subset sum problems. Math. Program., 66:181–199, 1994.

Tadanori Teruya, Kenji Kashiwabara, and Goichiro Hanaoka. Fast lattice basis reduction suitable for massive parallelization and its application to the shortest vector problem. In Michel Abdalla and Ricardo Dahab, editors, Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Rio de Janeiro, Brazil, March 25-29, 2018, Proceedings, Part I, volume 10769 of Lecture Notes in Computer Science, pages 437–460. Springer, 2018.

The FPLLL development team. fplll, a lattice reduction library. https://github.com/fplll/fplll, 2016.

The G6K development team. G6K, the general sieve kernel. https://github.com/fplll/g6k, 2018.

Gilles Villard. Parallel lattice basis reduction. In ISSAC ’92, 1992.