Memory adds no cost to lattice sieving for computers in 3 or more spatial dimensions
Authors
Samuel Jaques
Samuel Jaques
University of Waterloo, Waterloo, Canada
sejaques at uwaterloo dot ca
sejaques at uwaterloo dot ca
Abstract
The security of lattice-based crytography (LWE, NTRU, and FHE) depends on the hardness of the shortest-vector problem (SVP). Sieving algorithms give the lowest asymptotic runtime to solve SVP, but depend on exponential memory. Memory access costs much more in reality than in the RAM model, so we consider a computational model where processors, memory, and meters of wire are in constant proportions to each other. While this adds substantial costs to route data during lattice sieving, we modify existing algorithms to amortize these costs and find that, asymptotically, a classical computer can achieve the previous RAM model cost of $2^{0.2925d+o(d)}$ to sieve a $d$-dimensional lattice for a computer existing in 3 or more spatial dimensions, and can reach $2^{0.3113d+o(d)}$ in 2 spatial dimensions, where “spatial dimensions” are the dimensions of the physical geometry in which the computer exists.
Since this result implies an increased cost in 2 spatial dimensions, we make several assumptions about the constant terms of memory access and lattice attacks so that we can give bit security estimates for Kyber and Dilithium. These estimates support but do not increase the security categories claimed in the Kyber and Dilithium specifications, at least with respect to known attacks.
References
[ABD+21]
Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Kyber (version 3.02) – Submission to round 3 of the NIST post-quantum project. 2021.
[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, Advances in Cryptology – EUROCRYPT 2019, Part II, volume 11477 of Lecture Notes in Computer Science, pages 717–746, Darmstadt, Germany. 2019. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-17656-3_25
[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, Advances in Cryptology – ASIACRYPT 2020, Part II, volume 12492 of Lecture Notes in Computer Science, pages 583–613, Daejeon, South Korea. 2020. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-64834-3_20
[APS15]
Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of Learning with Errors. Journal of Mathematical Cryptology, 9(3):169–203, 2015. DOI: doi:10.1515/jmc-2015-0016
[BBG+13]
Robert Beals, Stephen Brierley, Oliver Gray, Aram W. Harrow, Samuel Kutin, Noah Linden, Dan Shepherd, and Mark Stather. Efficient distributed quantum computing. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 469(2153):20120686, May 2013. DOI: 10.1098/rspa.2012.0686
[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 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 10–24, Arlington, VA, USA. 2016. ACM-SIAM. DOI: 10.1137/1.9781611974331.ch2
[BDK+21]
Shi Bai, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Dilithium – Submission to round 3 of the NIST post-quantum project. 2021.
[Ber05]
Daniel J. Bernstein. Understanding brute force. Workshop Record of ECRYPT STVL Workshop in Symmetric Key Encryption, eSTREAM report 2005/036, 2005.
[Ber23]
Daniel J. Bernstein. Asymptotics of hybrid primal lattice attacks. Cryptology ePrint Archive, Report 2023/1892. 2023.
[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.
[BK81]
R. P. Brent and H. T. Kung. The Area-Time Complexity of Binary Multiplication. J. ACM, 28(3):521–534, July 1981. DOI: 10.1145/322261.322269
[BL13]
Daniel J. Bernstein and Tanja Lange. Non-uniform Cracks in the Concrete: The Power of Free Precomputation. In Kazue Sako and Palash Sarkar, editors, Advances in Cryptology – ASIACRYPT 2013, Part II, volume 8270 of Lecture Notes in Computer Science, pages 321–340, Bengalore, India. 2013. Springer, Berlin, Heidelberg, Germany. DOI: 10.1007/978-3-642-42045-0_17
[Cho22]
Charles Q. Choi. The Beating Heart of the World’s First Exascale Supercomputer. IEEE Spectrum. 2022.
[CL23]
André Chailloux and Johanna Loyer. Classical and Quantum 3 and 4-Sieves to Solve SVP with Low Memory. In Thomas Johansson and Daniel Smith-Tone, editors, Post-Quantum Cryptography - 14th International Workshop, PQCrypto 2023, pages 225–255, College Park, USA. 2023. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-40003-2_9
[CN11]
Yuanmi Chen and Phong Q. Nguyen. BKZ 2.0: Better Lattice Security Estimates. In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology – ASIACRYPT 2011, volume 7073 of Lecture Notes in Computer Science, pages 1–20, Seoul, South Korea. 2011. Springer, Berlin, Heidelberg, Germany. DOI: 10.1007/978-3-642-25385-0_1
[DSv21]
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, Advances in Cryptology – EUROCRYPT 2021, Part II, volume 12697 of Lecture Notes in Computer Science, pages 249–279, Zagreb, Croatia. 2021. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-77886-6_9
[Duc18]
Léo Ducas. Shortest Vector from Lattice Sieving: a Few Dimensions for Free. Presentation at Eurocrypt. 2018.
[Duc22]
Léo Ducas. Estimating the Hidden Overheads in the BDGL Lattice Sieving Algorithm. In Jung Hee Cheon and Thomas Johansson, editors, Post-Quantum Cryptography - 13th International Workshop, PQCrypto 2022, pages 480–497, Virtual Event. 2022. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-17234-2_22
[FHK+20]
Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Prest, Thomas Ricosset, Gregor Seiler, William Whyte, and Zhenfei Zhang. Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU (Specification v1.2) – Submission to round 3 of the NIST post-quantum project. 2020.
[HK17]
Gottfried Herold and Elena Kirshanova. Improved Algorithms for the Approximate $k$-List Problem in Euclidean Norm. In Serge Fehr, editor, PKC 2017: 20th International Conference on Theory and Practice of Public Key Cryptography, Part I, volume 10174 of Lecture Notes in Computer Science, pages 16–40, Amsterdam, The Netherlands. 2017. Springer, Berlin, Heidelberg, Germany. DOI: 10.1007/978-3-662-54365-8_2
[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: 21st International Conference on Theory and Practice of Public Key Cryptography, Part I, volume 10769 of Lecture Notes in Computer Science, pages 407–436, Rio de Janeiro, Brazil. 2018. Springer, Cham, Switzerland. DOI: 10.1007/978-3-319-76578-5_14
[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, Advances in Cryptology – ASIACRYPT 2019, Part I, volume 11921 of Lecture Notes in Computer Science, pages 521–551, Kobe, Japan. 2019. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-34578-5_19
[Kun87]
Manfred Kunde. Optimal sorting on multi-dimensionally mesh-connected computers. In Franz J. Brandenburg, Guy Vidal-Naquet, and Martin Wirsing, editors, STACS 87, pages 408–419, Berlin, Heidelberg. 1987. Springer Berlin Heidelberg. DOI: 10.1007/BFb0039623
[Laa15]
Thijs Laarhoven. Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing. In Rosario Gennaro and Matthew J. B. Robshaw, editors, Advances in Cryptology – CRYPTO 2015, Part I, volume 9215 of Lecture Notes in Computer Science, pages 3–22, Santa Barbara, CA, USA. 2015. Springer, Berlin, Heidelberg, Germany. DOI: 10.1007/978-3-662-47989-6_1
[Lc23]
L-com. Active Optical Cable QSFP28 100Gbps, 1 meter, Cisco Compatible. L-com product page. 2023.
[LWS21]
Patrick Longa, Wen Wang, and Jakub Szefer. The Cost to Break SIKE: A Comparative Hardware-Based Analysis with AES and SHA-3. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, Part III, volume 12827 of Lecture Notes in Computer Science, pages 402–431, Virtual Event. 2021. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-84252-9_14
[MAT22]
MATZOV. Report on the Security of LWE: Improved Dual Lattice Attack. 2022.
[{Nat}23a]
National Institute of Standards and Technologies. FAQ on Kyber512. 2023.
[{Nat}23b]
National Institute of Standards and Technology. Module-Lattice-Based Digital Signature Standard. Technical report number Federal Information Processing Standards Publications (FIPS PUBS) 203 (draft), U.S. Department of Commerce. 2023.
[{Nat}23c]
National Institute of Standards and Technology. Module-Lattice-Based Digital Signature Standard. Technical report number Federal Information Processing Standards Publications (FIPS PUBS) 204 (draft), U.S. Department of Commerce. 2023.
[NV08]
Phong Q. Nguyen and Thomas Vidick. Sieve algorithms for the shortest vector problem are practical. Journal of Mathematical Cryptology, 2(2), January 2008. DOI: 10.1515/jmc.2008.009
[{NVI}23]
NVIDIA Corporation. GeForce RTX 4090. NVIDIA product page. 2023.
[Sch23]
John M. Schanck. When sorting your data costs more than cracking AES-128. 2023.
[SS86]
Claus-Peter Schnorr and Adi Shamir. An Optimal Sorting Algorithm for Mesh Connected Computers. In 18th Annual ACM Symposium on Theory of Computing, pages 255–263, Berkeley, CA, USA. 1986. ACM Press. DOI: 10.1145/12130.12156
[Tho80]
C. D. Thompson. A Complexity Theory for VLSI. PhD thesis, Carnegie Mellon University, June 1980.
[Wie04]
Michael J. Wiener. The Full Cost of Cryptanalytic Attacks. Journal of Cryptology, 17(2):105–124, March 2004. DOI: 10.1007/s00145-003-0213-5
PDF
History
Submitted: 2024-06-23
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Samuel Jaques, Memory adds no cost to lattice sieving for computers in 3 or more spatial dimensions. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/ay4fbn2hd.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.