Scaling Lattice Sieves across Multiple Machines

Martin R. Albrecht; Joe Rowell

doi:10.62056/a3wahey6b

Scaling Lattice Sieves across Multiple Machines

Authors

Martin R. Albrecht, Joe Rowell

Martin R. Albrecht

King's College London, London, United Kingdom
SandboxAQ, Palo Alto, United States
martin dot albrecht at kcl dot ac dot uk

Joe Rowell

Unaffiliated, United Kingdom
joe dot rowell dot 2015 at live dot rhul dot ac dot uk

Keywords: Lattices Lattice Reduction Distributed Computing

Abstract

Lattice sieves are algorithms for finding short vectors in lattices. We present an implementation of two such sieves – known as "BGJ1" and "BDGL" in the literature - that scales across multiple servers (with varying success). This class of algorithms requires exponential memory which had put into question their ability to scale across sieving nodes. We discuss our architecture and optimisations and report experimental evidence of the efficiency of our approach.

References

[ABF⁺20]

Martin R. Albrecht, Shi Bai, Pierre-Alain Fouque, Paul Kirchner, Damien Stehlé, and Weiqiang Wen. Faster Enumeration-Based Lattice Reduction: Root Hermite Factor $k^{1/(2k)}$ Time $k^{k/8+o(k)}$. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part II, volume 12171 of LNCS, pages 186–212. August 2020. Springer, Cham. DOI: 10.1007/978-3-030-56880-1_7

Google Scholar ePrint

[ABLR21]

Martin R. Albrecht, Shi Bai, Jianwei Li, and Joe Rowell. Lattice Reduction with Approximate Enumeration Oracles - Practical Algorithms and Concrete Performance. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part II, volume 12826 of LNCS, pages 732–759, Virtual Event. August 2021. Springer, Cham. DOI: 10.1007/978-3-030-84245-1_25

Google Scholar ePrint

[ADH⁺19]

Martin R. Albrecht, Léo 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, EUROCRYPT 2019, Part II, volume 11477 of LNCS, pages 717–746. May 2019. Springer, Cham. DOI: 10.1007/978-3-030-17656-3_25

Google Scholar ePrint

[ADRS15]

Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. Solving the Shortest Vector Problem in $2^n$ Time Using Discrete Gaussian Sampling: Extended Abstract. In Rocco A. Servedio and Ronitt Rubinfeld, editors, 47th ACM STOC, pages 733–742. June 2015. ACM Press. DOI: 10.1145/2746539.2746606

Google Scholar ePrint

[AG20]

Michal Andrzejczak and Kris Gaj. A Multiplatform Parallel Approach for Lattice Sieving Algorithms. In Algorithms and Architectures for Parallel Processing, pages 661-680, Cham. 2020. Springer International Publishing. DOI: 10.1007/978-3-030-60245-1_45

Google Scholar ePrint

[AGPS20]

Martin R. Albrecht, Vlad Gheorghiu, Eamonn W. Postlethwaite, and John M. Schanck. Estimating Quantum Speedups for Lattice Sieves. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part II, volume 12492 of LNCS, pages 583–613. December 2020. Springer, Cham. DOI: 10.1007/978-3-030-64834-3_20

Google Scholar ePrint

[Ajt98]

Miklós Ajtai. The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions (Extended Abstract). In 30th ACM STOC, pages 10–19. May 1998. ACM Press. DOI: 10.1145/276698.276705

Google Scholar ePrint

[AKS01]

Miklós Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the shortest lattice vector problem. In 33rd ACM STOC, pages 601–610. July 2001. ACM Press. DOI: 10.1145/380752.380857

Google Scholar ePrint

[AS17]

Jacob Alperin-Sheriff. NIST's PQC Standardization: Suggested Avenues for Lattice-Based Research. Talk, slides available at http://crypto-events.di.ens.fr/LATCA/program/alperin-sheriff.pdf. May 2017.

Google Scholar ePrint

[Bab85]

László Babai. On Lovász' Lattice Reduction and the Nearest Lattice Point Problem (Shortened Version). In Kurt Mehlhorn, editor, STACS '86, volume 82 of Lecture Notes in Computer Science, pages 13-20. 1985. Springer, Heidelberg. DOI: 10.1007/BF02579403

Google Scholar ePrint

[BBC⁺20]

Daniel J. Bernstein, Billy Bob Brumley, Ming-Shing Chen, Chitchanok Chuengsatiansup, Tanja Lange, Adrian Marotzke, Bo-Yuan Peng, Nicola Tuveri, Christine van Vredendaal, and Bo-Yin Yang. NTRU Prime. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions. 2020.

Google Scholar ePrint

[BBK19]

Michael Burger, Christian Bischof, and Juliane Krämer. p3Enum: A New Parameterizable and Shared-Memory Parallelized Shortest Vector Problem Solver. In Computational Science – ICCS 2019, pages 535-542. 2019. DOI: 10.1007/978-3-030-22750-0_48

Google Scholar ePrint

[BDGL16]

Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. New directions in nearest neighbor searching with applications to lattice sieving. In Robert Krauthgamer, editor, 27th SODA, pages 10–24. January 2016. ACM-SIAM. DOI: 10.1137/1.9781611974331.ch2

Google Scholar ePrint

[Ber16]

Daniel Bernstein. Re: Inaccurate security claims in NTRUprime. https://groups.google.com/g/cryptanalytic-algorithms/c/BoSRL0uHIjM/m/eB4G-dscCAAJ. Cryptanalytic algorithms mailing list. May 2016.

Google Scholar ePrint

[BGJ15]

Anja Becker, Nicolas Gama, and Antoine Joux. Speeding-up lattice sieving without increasing the memory, using sub-quadratic nearest neighbor search. Cryptology ePrint Archive, Report 2015/522. 2015.

Google Scholar ePrint

[BHK⁺97]

J. Bruck, Ching-Tien Ho, S. Kipnis, E. Upfal, and D. Weathersby. Efficient algorithms for all-to-all communications in multiport message-passing systems. IEEE Transactions on Parallel and Distributed Systems, 8(11):1143-1156, 1997. DOI: 10.1109/71.642949

Google Scholar ePrint

[BLS16]

Shi Bai, Thijs Laarhoven, and Damien Stehle. Tuple lattice sieving. LMS Journal of Computation and Mathematics, 19(A), 2016. DOI: 10.1112/S1461157016000292

Google Scholar ePrint

[BNP17]

Joppe W. Bos, Michael Naehrig, and Joop Van De Pol. Sieving for shortest vectors in ideal lattices: a practical perspective. International Journal of Applied Cryptography, 3(4):313-329, 2017. DOI: 10.1504/IJACT.2017.089353

Google Scholar ePrint

[Cha02]

Moses Charikar. Similarity estimation techniques from rounding algorithms. In 34th ACM STOC, pages 380–388. May 2002. ACM Press. DOI: 10.1145/509907.509965

Google Scholar ePrint

[CKP⁺93]

David Culler, Richard Karp, David Patterson, Abhijit Sahay, Klaus Erik Schauser, Eunice Santos, Ramesh Subramonian, and Thorsten von Eicken. LogP: Towards a Realistic Model of Parallel Computation. SIGPLAN Not., 28(7):1–12, July 1993. DOI: 10.1145/173284.155333

Google Scholar ePrint

[CMP⁺16]

Fábio Correia, Artur Mariano, Alberto Proença, Christian Bischof, and Erik Agrell. Parallel Improved Schnorr-Euchner Enumeration SE++ for the CVP and SVP. In 2016 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP), pages 596-603. 2016. DOI: 10.1109/PDP.2016.95

Google Scholar ePrint

[CS87]

J. H. Conway and N. J. A. Sloane. Sphere-packings, Lattices, and Groups. Springer 1987. DOI: 10.1007/978-1-4757-6568-7

Google Scholar ePrint

[DHPS10]

Jérémie Detrey, Guillaume Hanrot, Xavier Pujol, and Damien Stehlé. Accelerating Lattice Reduction with FPGAs. In Michel Abdalla and Paulo S. L. M. Barreto, editors, LATINCRYPT 2010, volume 6212 of LNCS, pages 124–143. August 2010. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-14712-8_8

Google Scholar ePrint

[DS10]

Özgür Dagdelen and Michael Schneider. Parallel Enumeration of Shortest Lattice Vectors. In Euro-Par 2010 - Parallel Processing, pages 211-222. 2010. DOI: 10.1007/978-3-642-15291-7_21

Google Scholar ePrint

[DSvW21]

Léo Ducas, Marc Stevens, and Wessel P. J. van Woerden. Advanced Lattice Sieving on GPUs, with Tensor Cores. In Anne Canteaut and François-Xavier Standaert, editors, EUROCRYPT 2021, Part II, volume 12697 of LNCS, pages 249–279. October 2021. Springer, Cham. DOI: 10.1007/978-3-030-77886-6_9

Google Scholar ePrint

[dt23]

The FPLLL development team. fplll, a lattice reduction library, Version: 5.4.4. Available at https://github.com/fplll/fplll. 2023.

Google Scholar ePrint

[Duc18a]

Léo Ducas. Shortest Vector from Lattice Sieving: A Few Dimensions for Free. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part I, volume 10820 of LNCS, pages 125–145. 2018. Springer, Cham. DOI: 10.1007/978-3-319-78381-9_5

Google Scholar ePrint

[Duc18b]

Léo Ducas. Shortest Vector from Lattice Sieving: a Few Dimensions for Free. https://eurocrypt.iacr.org/2018/Slides/Monday/TrackB/01-01.pdf. Presentation at EUROCRYPT 2018. April 2018.

Google Scholar ePrint

[FBB⁺15]

Robert Fitzpatrick, Christian H. Bischof, Johannes Buchmann, Özgür Dagdelen, Florian Göpfert, Artur Mariano, and Bo-Yin Yang. Tuning GaussSieve for Speed. In Diego F. Aranha and Alfred Menezes, editors, LATINCRYPT 2014, volume 8895 of LNCS, pages 288–305. September 2015. Springer, Cham. DOI: 10.1007/978-3-319-16295-9_16

Google Scholar ePrint

[For12]

Message Passing Interface Forum. MPI: A Message-Passing Interface Standard. 2012.

Google Scholar ePrint

[FP83]

Ulrich Fincke and Michael Pohst. A procedure for determining algebraic integers of given norm. In J. A. van Hulzen, editor, EUROCAL, volume 162 of LNCS, pages 194-202. 1983. Springer. DOI: 10.1007/3-540-12868-9_103

Google Scholar ePrint

[FW78]

Steven Fortune and James Wyllie. Parallelism in random access machines. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pages 114–118. 1978. DOI: 10.1145/800133.804339

Google Scholar ePrint

[GNR10]

Nicolas Gama, Phong Q. Nguyen, and Oded Regev. Lattice Enumeration Using Extreme Pruning. In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 257–278. 2010. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-13190-5_13

Google Scholar ePrint

[HK17]

Gottfried Herold and Elena Kirshanova. Improved Algorithms for the Approximate $k$-List Problem in Euclidean Norm. In Serge Fehr, editor, PKC 2017, Part I, volume 10174 of LNCS, pages 16–40. March 2017. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-54365-8_2

Google Scholar ePrint

[HKL18]

Gottfried Herold, Elena Kirshanova, and Thijs Laarhoven. Speed-Ups and Time-Memory Trade-Offs for Tuple Lattice Sieving. In Michel Abdalla and Ricardo Dahab, editors, PKC 2018, Part I, volume 10769 of LNCS, pages 407–436. March 2018. Springer, Cham. DOI: 10.1007/978-3-319-76578-5_14

Google Scholar ePrint

[HR12]

Ishay Haviv and Oded Regev. Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors. Theory of Computing, 8(1):513-531, 2012. Preliminary version in Proceedings of STOC '07 DOI: 10.4086/toc.2012.v008a023

Google Scholar ePrint

[HSB⁺10]

Jens Hermans, Michael Schneider, Johannes Buchmann, Frederik Vercauteren, and Bart Preneel. Parallel Shortest Lattice Vector Enumeration on Graphics Cards. In Daniel J. Bernstein and Tanja Lange, editors, AFRICACRYPT 10, volume 6055 of LNCS, pages 52–68. May 2010. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-12678-9_4

Google Scholar ePrint

[IKMT14]

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, PKC 2014, volume 8383 of LNCS, pages 411–428. March 2014. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-54631-0_24

Google Scholar ePrint

[Jaq24]

Samuel Jaques. Memory adds no cost to lattice sieving for computers in 3 or more spatial dimensions. 2024.

Google Scholar ePrint

[Kan83]

Ravi Kannan. Improved Algorithms for Integer Programming and Related Lattice Problems. In 15th ACM STOC, pages 193–206. April 1983. ACM Press. DOI: 10.1145/800061.808749

Google Scholar ePrint

[Kho05]

Subhash Khot. Hardness of approximating the shortest vector problem in lattices. Journal of the ACM, 52(5):789-808, 2005. Preliminary version in Proceedings of FOCS '04 DOI: 10.1145/1089023.1089027

Google Scholar ePrint

[Kir16]

Paul Kirchner. Re: Inaccurate security claims in NTRUprime. https://groups.google.com/g/cryptanalytic-algorithms/c/BoSRL0uHIjM/m/wAkZQlwRAgAJ. Cryptanalytic algorithms mailing list. May 2016.

Google Scholar ePrint

[KMPM19]

Elena Kirshanova, Erik Mårtensson, Eamonn W. Postlethwaite, and Subhayan Roy Moulik. Quantum Algorithms for the Approximate k-List Problem and Their Application to Lattice Sieving. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part I, volume 11921 of LNCS, pages 521–551. December 2019. Springer, Cham. DOI: 10.1007/978-3-030-34578-5_19

Google Scholar ePrint

[KSD⁺11]

Po-Chun Kuo, Michael Schneider, Özgür Dagdelen, Jan Reichelt, Johannes Buchmann, Chen-Mou Cheng, and Bo-Yin Yang. Extreme Enumeration on GPU and in Clouds - - How Many Dollars You Need to Break SVP Challenges -. In Bart Preneel and Tsuyoshi Takagi, editors, CHES 2011, volume 6917 of LNCS, pages 176–191. 2011. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-23951-9_12

Google Scholar ePrint

[Laa15]

Thijs Laarhoven. Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing. In Rosario Gennaro and Matthew J. B. Robshaw, editors, CRYPTO 2015, Part I, volume 9215 of LNCS, pages 3–22. August 2015. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-47989-6_1

Google Scholar ePrint

[Lon24]

King's College London. King's Computational Research, Engineering and Technology Environment (CREATE). Retrieved May 6, 2024 from https://doi.org/10.18742/rnvf-m076. 2024.

Google Scholar ePrint

[LR24]

R. Lindner and M. Ruckert. TU Darmstadt lattice challenge. Available at http://www.latticechallenge.org/. 2024.

Google Scholar ePrint

[MBL15]

Artur Mariano, Christian Bischof, and Thijs Laarhoven. Parallel (Probable) Lock-Free Hash Sieve: A Practical Sieving Algorithm for the SVP. In 2015 44th International Conference on Parallel Processing, pages 590-599. 2015. DOI: 10.1109/ICPP.2015.68

Google Scholar ePrint

[MG13]

Zoltan Majo and Thomas R. Gross. (Mis)understanding the NUMA memory system performance of multithreaded workloads. In 2013 IEEE International Symposium on Workload Characterization (IISWC). 2013. DOI: 10.1109/IISWC.2013.6704666

Google Scholar ePrint

[Mic01]

Daniele Micciancio. The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant. SIAM Journal on Computing, 30(6):2008-2035, 2001. Preliminary version in Proceedings of FOCS '98 DOI: 10.1137/s0097539700373039

Google Scholar ePrint

[Mic12]

Daniele Micciancio. Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction. Theory of Computing, 8(22):487-512, 2012. DOI: 10.4086/toc.2012.v008a022

Google Scholar ePrint

[MS11]

Benjamin Milde and Michael Schneider. A Parallel Implementation of GaussSieve for the Shortest Vector Problem in Lattices. In Parallel Computing Technologies, pages 452-458. 2011. DOI: 10.1007/978-3-642-23178-0_40

Google Scholar ePrint

[MV10a]

Daniele Micciancio and Panagiotis Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. In Leonard J. Schulman, editor, 42nd ACM STOC, pages 351–358. June 2010. ACM Press. DOI: 10.1145/1806689.1806738

Google Scholar ePrint

[MV10b]

Daniele Micciancio and Panagiotis Voulgaris. Faster Exponential Time Algorithms for the Shortest Vector Problem. In Moses Charika, editor, 21st SODA, pages 1468–1480. January 2010. ACM-SIAM. DOI: 10.1137/1.9781611973075.119

Google Scholar ePrint

[MW15]

Daniele Micciancio and Michael Walter. Fast Lattice Point Enumeration with Minimal Overhead. In Piotr Indyk, editor, 26th SODA, pages 276–294. January 2015. ACM-SIAM. DOI: 10.1137/1.9781611973730.21

Google Scholar ePrint

[{NIS}23]

NIST. FAQ on Kyber512. https://csrc.nist.gov/csrc/media/Projects/post-quantum-cryptography/documents/faq/Kyber-512-FAQ.pdf. December 2023.

Google Scholar ePrint

[NV08]

Phong Q. Nguyen and Thomas Vidick. Sieve Algorithms for the Shortest Vector Problem are Practical. J. of Mathematical Cryptology, 2(2), 2008. DOI: 10.1515/JMC.2008.009

Google Scholar ePrint

[PSZ21]

Simon Pohmann, Marc Stevens, and Jens Zumbrägel. Lattice Enumeration on GPUs for fplll. https://eprint.iacr.org/2021/430. Cryptology ePrint Archive, Paper 2021/430. 2021.

Google Scholar ePrint

[Sch24]

John Schanck. An Update on Lattice Cryptanalysis vol. 2. https://na.eventscloud.com/website/65452/presentations-and-video-/. Invited talk delivered at RWPQC'24. March 2024.

Google Scholar ePrint

[TKH18]

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, PKC 2018, Part I, volume 10769 of LNCS, pages 437–460. March 2018. Springer, Cham. DOI: 10.1007/978-3-319-76578-5_15

Google Scholar ePrint

[TSN⁺20]

Nariaki Tateiwa, Yuji Shinano, Satoshi Nakamura, Akihiro Yoshida, Shizuo Kaji, Masaya Yasuda, and Katsuki Fujisawa. Massive Parallelization for Finding Shortest Lattice Vectors Based on Ubiquity Generator Framework. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1-15. 2020. DOI: 10.1109/SC41405.2020.00064

Google Scholar ePrint

[TSY⁺21]

Nariaki Tateiwa, Yuji Shinano, Keiichiro Yamamura, Akihiro Yoshida, Shizuo Kaji, Masaya Yasuda, and Katsuki Fujisawa. CMAP-LAP: Configurable Massively Parallel Solver for Lattice Problems. In 2021 IEEE 28th International Conference on High Performance Computing, Data, and Analytics (HiPC), pages 42-52. 2021. DOI: 10.1109/HiPC53243.2021.00018

Google Scholar ePrint

[ZDY24]

Ziyu Zhao, Jintai Ding, and Bo-Yin Yang. BGJ15 Revisited: Sieving with Streamed Memory Access. Cryptology ePrint Archive, Report 2024/739. 2024.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a3wahey6b

History

Submitted: 2024-09-29
Accepted: 2024-12-03
Published: 2025-01-13

How to cite

Martin R. Albrecht and Joe Rowell, Scaling Lattice Sieves across Multiple Machines. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/a3wahey6b.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.