{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T17:04:52Z","timestamp":1753895092794,"version":"3.41.2"},"reference-count":63,"publisher":"International Association for Cryptologic Research","issue":"4","license":[{"start":{"date-parts":[[2024,9,29]],"date-time":"2024-09-29T00:00:00Z","timestamp":1727568000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,12,3]]},"abstract":"<jats:p>  Lattice sieves are algorithms for finding short vectors in lattices. We present an implementation of two such sieves \u2013 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. <\/jats:p>","DOI":"10.62056\/a3wahey6b","type":"journal-article","created":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T17:00:52Z","timestamp":1736787652000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Scaling Lattice Sieves across Multiple Machines"],"prefix":"10.62056","volume":"1","author":[{"given":"Martin","family":"Albrecht","sequence":"first","affiliation":[{"name":"King's College London","place":["London, United Kingdom"]},{"name":"SandboxAQ","place":["Palo Alto, CA, United States"]}]},{"given":"Joe","family":"Rowell","sequence":"additional","affiliation":[{"name":"Unaffiliated","place":["United Kingdom"]}]}],"member":"48349","published-online":{"date-parts":[[2025,1,13]]},"reference":[{"key":"ref1:STOC:Ajtai98","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/276698.276705","article-title":"The Shortest Vector Problem in L2 is NP-hard for\n  Randomized Reductions (Extended Abstract)","author":"Mikl\u00f3s Ajtai","year":"1998"},{"key":"ref2:Micciancio00","doi-asserted-by":"publisher","first-page":"2008","DOI":"10.1137\/s0097539700373039","article-title":"The Shortest Vector in a Lattice is Hard to Approximate to\n  within Some Constant","volume":"30","author":"Daniele Micciancio","year":"2001","journal-title":"SIAM Journal on Computing"},{"key":"ref3:Khot05","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1145\/1089023.1089027","article-title":"Hardness of approximating the shortest vector problem in\n  lattices","volume":"52","author":"Subhash Khot","year":"2005","journal-title":"Journal of the ACM"},{"key":"ref4:HavReg12","doi-asserted-by":"publisher","first-page":"513","DOI":"10.4086\/toc.2012.v008a023","article-title":"Tensor-based Hardness of the Shortest Vector Problem to\n  within Almost Polynomial Factors","volume":"8","author":"Ishay Haviv","year":"2012","journal-title":"Theory of Computing"},{"key":"ref5:Micciancio12","doi-asserted-by":"publisher","first-page":"487","DOI":"10.4086\/toc.2012.v008a022","article-title":"Inapproximability of the Shortest Vector Problem: Toward a\n  Deterministic Reduction","volume":"8","author":"Daniele Micciancio","year":"2012","journal-title":"Theory of Computing"},{"key":"ref6:STOC:Kannan83a","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1145\/800061.808749","article-title":"Improved Algorithms for Integer Programming and Related\n  Lattice Problems","author":"Ravi Kannan","year":"1983"},{"key":"ref7:FinPoh83","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/3-540-12868-9_103","article-title":"A procedure for determining algebraic integers of given\n  norm","volume":"162","author":"Ulrich Fincke","year":"1983"},{"key":"ref8:STOC:AjtKumSiv01","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1145\/380752.380857","article-title":"A sieve algorithm for the shortest lattice vector problem","author":"Mikl\u00f3s Ajtai","year":"2001"},{"key":"ref9:NguVid08","doi-asserted-by":"publisher","DOI":"10.1515\/JMC.2008.009","article-title":"Sieve Algorithms for the Shortest Vector Problem are\n  Practical","volume":"2","author":"Phong Q. Nguyen","year":"2008","journal-title":"J. of Mathematical Cryptology"},{"key":"ref10:EC:GamNguReg10","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-642-13190-5_13","article-title":"Lattice Enumeration Using Extreme Pruning","volume":"6110","author":"Nicolas Gama","year":"2010"},{"key":"ref11:STOC:MicVou10","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1145\/1806689.1806738","article-title":"A deterministic single exponential time algorithm for most\n  lattice problems based on voronoi cell computations","author":"Daniele Micciancio","year":"2010"},{"key":"ref12:SODA:MicWal15","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1137\/1.9781611973730.21","article-title":"Fast Lattice Point Enumeration with Minimal Overhead","author":"Daniele Micciancio","year":"2015"},{"key":"ref13:C:Laarhoven15","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-662-47989-6_1","article-title":"Sieving for Shortest Vectors in Lattices Using Angular\n  Locality-Sensitive Hashing","volume":"9215","author":"Thijs Laarhoven","year":"2015"},{"key":"ref14:SODA:BDGL16","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1137\/1.9781611974331.ch2","article-title":"New directions in nearest neighbor searching with\n  applications to lattice sieving","author":"Anja Becker","year":"2016"},{"key":"ref15:EC:Ducas18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-319-78381-9_5","article-title":"Shortest Vector from Lattice Sieving: A Few Dimensions for\n  Free","volume":"10820","author":"L\u00e9o Ducas","year":"2018"},{"key":"ref16:EC:ADHKPS19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/978-3-030-17656-3_25","article-title":"The General Sieve Kernel and New Records in Lattice\n  Reduction","volume":"11477","author":"Martin R. Albrecht","year":"2019"},{"key":"ref17:C:ABFKSW20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/978-3-030-56880-1_7","article-title":"Faster Enumeration-Based Lattice Reduction: Root Hermite\n  Factor $k^{1\/(2k)}$ Time $k^{k\/8+o(k)}$","volume":"12171","author":"Martin R. Albrecht","year":"2020"},{"key":"ref18:C:ABLR21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"732","DOI":"10.1007\/978-3-030-84245-1_25","article-title":"Lattice Reduction with Approximate Enumeration Oracles -\n  Practical Algorithms and Concrete Performance","volume":"12826","author":"Martin R. Albrecht","year":"2021"},{"key":"ref19:SODA:MicVou10","doi-asserted-by":"publisher","first-page":"1468","DOI":"10.1137\/1.9781611973075.119","article-title":"Faster Exponential Time Algorithms for the Shortest Vector\n  Problem","author":"Daniele Micciancio","year":"2010"},{"key":"ref20:STOC:ADRS15","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1145\/2746539.2746606","article-title":"Solving the Shortest Vector Problem in $2^n$ Time Using\n  Discrete Gaussian Sampling: Extended Abstract","author":"Divesh Aggarwal","year":"2015"},{"volume-title":"Speeding-up lattice sieving without increasing the memory,\n  using sub-quadratic nearest neighbor search","year":"2015","author":"Anja Becker","key":"ref21:EPRINT:BecGamJou15"},{"key":"ref22:PKC:HerKir17","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-662-54365-8_2","article-title":"Improved Algorithms for the Approximate $k$-List Problem\n  in Euclidean Norm","volume":"10174","author":"Gottfried Herold","year":"2017"},{"volume-title":"TU Darmstadt lattice challenge","year":"2024","author":"R. Lindner","key":"ref23:DarmChal"},{"key":"ref24:EC:DucStevWo21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/978-3-030-77886-6_9","article-title":"Advanced Lattice Sieving on GPUs, with Tensor Cores","volume":"12697","author":"L\u00e9o Ducas","year":"2021"},{"volume-title":"BGJ15 Revisited: Sieving with Streamed Memory Access","year":"2024","author":"Ziyu Zhao","key":"ref25:EPRINT:ZhaDinYan24"},{"volume-title":"Re: Inaccurate security claims in NTRUprime","year":"2016","author":"Daniel Bernstein","key":"ref26:Bernstein16"},{"volume-title":"NTRU Prime","year":"2020","author":"Daniel J. Bernstein","key":"ref27:NISTPQC-R3:NTRUPrime20"},{"volume-title":"NIST's PQC Standardization: Suggested Avenues for\n  Lattice-Based Research","year":"2017","author":"Jacob Alperin-Sheriff","key":"ref28:Alperin-Sheriff17"},{"volume-title":"FAQ on Kyber512","year":"2023","author":"NIST","key":"ref29:Nist23"},{"key":"ref30:EPRINT:Jaques24","doi-asserted-by":"publisher","DOI":"10.62056\/ay4fbn2hd","volume-title":"Memory adds no cost to lattice sieving for computers in 3 or\n  more spatial dimensions","volume":"1","author":"Samuel Jaques","year":"2024","journal-title":"IACR Communications in Cryptology","ISSN":"https:\/\/id.crossref.org\/issn\/3006-5496","issn-type":"electronic"},{"volume-title":"An Update on Lattice Cryptanalysis vol. 2","year":"2024","author":"John Schanck","key":"ref31:Schanck24"},{"key":"ref32:AFRICACRYPT:HSBVP10","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/978-3-642-12678-9_4","article-title":"Parallel Shortest Lattice Vector Enumeration on Graphics\n  Cards","volume":"6055","author":"Jens Hermans","year":"2010"},{"key":"ref33:LC:DHPS10","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1007\/978-3-642-14712-8_8","article-title":"Accelerating Lattice Reduction with FPGAs","volume":"6212","author":"J\u00e9r\u00e9mie Detrey","year":"2010"},{"key":"ref34:CHES:KSDRBC11","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-642-23951-9_12","article-title":"Extreme Enumeration on GPU and in Clouds - - How Many\n  Dollars You Need to Break SVP Challenges -","volume":"6917","author":"Po-Chun Kuo","year":"2011"},{"key":"ref35:EUROPAR:DagSch10","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/978-3-642-15291-7_21","article-title":"Parallel Enumeration of Shortest Lattice Vectors","author":"\u00d6zg\u00fcr Dagdelen","year":"2010"},{"key":"ref36:PDP:CMPBA16","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1109\/PDP.2016.95","article-title":"Parallel Improved Schnorr-Euchner Enumeration SE++ for the\n  CVP and SVP","author":"F\u00e1bio Correia","year":"2016"},{"key":"ref37:ICCS:BurBisKra19","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/978-3-030-22750-0_48","article-title":"p3Enum: A New Parameterizable and Shared-Memory\n  Parallelized Shortest Vector Problem Solver","author":"Michael Burger","year":"2019"},{"volume-title":"Lattice Enumeration on GPUs for fplll","year":"2021","author":"Simon Pohmann","key":"ref38:PSZ21"},{"key":"ref39:PKC:TerKasHan18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/978-3-319-76578-5_15","article-title":"Fast Lattice Basis Reduction Suitable for Massive\n  Parallelization and Its Application to the Shortest Vector Problem","volume":"10769","author":"Tadanori Teruya","year":"2018"},{"key":"ref40:MAP-SVP","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/SC41405.2020.00064","article-title":"Massive Parallelization for Finding Shortest Lattice Vectors\n  Based on Ubiquity Generator Framework","author":"Nariaki Tateiwa","year":"2020"},{"volume-title":"fplll, a lattice reduction library, Version: 5.4.4","year":"2023","author":"The FPLLL development team","key":"ref41:fplll"},{"key":"ref42:PACT:MilSch11","isbn-type":"print","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1007\/978-3-642-23178-0_40","article-title":"A Parallel Implementation of GaussSieve for the Shortest\n  Vector Problem in Lattices","author":"Benjamin Milde","year":"2011","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642231780"},{"key":"ref43:PKC:IKMT14","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/978-3-642-54631-0_24","article-title":"Parallel Gauss Sieve Algorithm: Solving the SVP Challenge\n  over a 128-Dimensional Ideal Lattice","volume":"8383","author":"Tsukasa Ishiguro","year":"2014"},{"key":"ref44:ICPP:MarBisLaa15","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1109\/ICPP.2015.68","article-title":"Parallel (Probable) Lock-Free Hash Sieve: A Practical\n  Sieving Algorithm for the SVP","author":"Artur Mariano","year":"2015"},{"key":"ref45:ICALP:GajAnd20","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/978-3-030-60245-1_45","article-title":"A Multiplatform Parallel Approach for Lattice Sieving\n  Algorithms","author":"Michal Andrzejczak","year":"2020"},{"key":"ref46:BNvDP14","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1504\/IJACT.2017.089353","article-title":"Sieving for shortest vectors in ideal lattices: a practical\n  perspective","volume":"3","author":"Joppe W. Bos","year":"2017","journal-title":"International Journal of Applied Cryptography"},{"key":"ref47:CMAP-LAP","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1109\/HiPC53243.2021.00018","article-title":"CMAP-LAP: Configurable Massively Parallel Solver for\n  Lattice Problems","author":"Nariaki Tateiwa","year":"2021"},{"volume-title":"Shortest Vector from Lattice Sieving: a Few Dimensions for\n  Free","year":"2018","author":"L\u00e9o Ducas","key":"ref48:Ducas18"},{"volume-title":"Re: Inaccurate security claims in NTRUprime","year":"2016","author":"Paul Kirchner","key":"ref49:Kirchner16"},{"key":"ref50:AC:KMPM19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/978-3-030-34578-5_19","article-title":"Quantum Algorithms for the Approximate k-List Problem and\n  Their Application to Lattice Sieving","volume":"11921","author":"Elena Kirshanova","year":"2019"},{"key":"ref51:ANTS:BaiLaaSte16","doi-asserted-by":"publisher","DOI":"10.1112\/S1461157016000292","article-title":"Tuple lattice sieving","volume":"19","author":"Shi Bai","year":"2016","journal-title":"LMS Journal of Computation and Mathematics"},{"key":"ref52:PKC:HerKirLaa18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/978-3-319-76578-5_14","article-title":"Speed-Ups and Time-Memory Trade-Offs for Tuple Lattice\n  Sieving","volume":"10769","author":"Gottfried Herold","year":"2018"},{"key":"ref53:ConSlo87","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-6568-7","volume-title":"Sphere-packings, Lattices, and Groups","author":"J. H. Conway","year":"1987"},{"key":"ref54:STOC:Charikar02","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1145\/509907.509965","article-title":"Similarity estimation techniques from rounding algorithms","author":"Moses Charikar","year":"2002"},{"key":"ref55:LC:FBBDGM14","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/978-3-319-16295-9_16","article-title":"Tuning GaussSieve for Speed","volume":"8895","author":"Robert Fitzpatrick","year":"2015"},{"key":"ref56:AC:AGPS20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/978-3-030-64834-3_20","article-title":"Estimating Quantum Speedups for Lattice Sieves","volume":"12492","author":"Martin R. Albrecht","year":"2020"},{"key":"ref57:STACS:Babai85","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF02579403","article-title":"On Lov\u00e1sz' Lattice Reduction and the Nearest Lattice\n  Point Problem (Shortened Version)","volume":"82","author":"L\u00e1szl\u00f3 Babai","year":"1985","ISBN":"https:\/\/id.crossref.org\/isbn\/3540139125"},{"key":"ref58:logP","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/173284.155333","article-title":"LogP: Towards a Realistic Model of Parallel Computation","volume":"28","author":"David Culler","year":"1993","journal-title":"SIGPLAN Not.","ISSN":"https:\/\/id.crossref.org\/issn\/0362-1340","issn-type":"electronic"},{"key":"ref59:STOC:ForWyl78","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/800133.804339","article-title":"Parallelism in random access machines","author":"Steven Fortune","year":"1978"},{"key":"ref60:CREATE","doi-asserted-by":"publisher","DOI":"10.18742\/rnvf-m076","volume-title":"King's Computational Research, Engineering and Technology\n  Environment (CREATE)","author":"King's College London","year":"2024"},{"volume-title":"MPI: A Message-Passing Interface Standard","year":"2012","author":"Message Passing Interface Forum","key":"ref61:mpi-standard"},{"key":"ref62:BHKUW97","doi-asserted-by":"publisher","first-page":"1143","DOI":"10.1109\/71.642949","article-title":"Efficient algorithms for all-to-all communications in\n  multiport message-passing systems","volume":"8","author":"J. Bruck","year":"1997","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"ref63:IISWC:ZolGro13","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2013.6704666","article-title":"(Mis)understanding the NUMA memory system performance of\n  multithreaded workloads","author":"Zoltan Majo","year":"2013"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T17:11:17Z","timestamp":1736788277000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/4\/11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,13]]},"references-count":63,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2025,1,13]]}},"URL":"https:\/\/doi.org\/10.62056\/a3wahey6b","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"type":"electronic","value":"3006-5496"}],"subject":[],"published":{"date-parts":[[2025,1,13]]},"assertion":[{"value":"2024-09-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-4-12"}}