{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,29]],"date-time":"2026-07-29T00:05:25Z","timestamp":1785283525614,"version":"3.55.0"},"reference-count":0,"publisher":"Universitatsbibliothek der Ruhr-Universitat Bochum","issue":"2","license":[{"start":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T00:00:00Z","timestamp":1741046400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["TCHES"],"abstract":"<jats:p>We implement an optimized BGJ (Becker\u2013Gama\u2013Joux 2015) sieve and analyze its behavior in a study of RAM access overheads (and their minimization) in sieving algorithms for large lattice problems. Both experiment and theory points to BGJ\u2019s inherent structure being much more memory-efficient than the BDGL (Becker\u2013Ducas\u2013 Gama\u2013Laahoven 2016) sieve, which uses asymptotically the fewest logical operations. In particular, a dimension-n BGJ sieve uses only 20.2075n+o(n) streaming (non-random) main memory accesses. A key insight: Bucket sizes decrease by orders of magnitude after each BGJ filtering layer, so that sub-buckets fit into successively much smaller (hence faster) storage areas. Our refined BGJ is competitive at cryptographic sizes and should outperform BDGL for all practically achievable dimensions.The above is corroborated by the results from our efficient CPU-based BGJ implementation in an optimized framework, which saves about 40% RAM footprint and is \u2265 24.5x more efficient gate-count-wise compared to the Ducas\u2013Stevens\u2013van Woerden 2021 4-GPU implementation, which like most prior sieving-based SVP computations is a HK3 (Herold\u2013Kirshanova 2017) sieve. Notably, we solved the 183-dimensional SVP Darmstadt Challenge in 30 days on a 112-core server and 0.87 TB of RAM; similarly we also found a short vector in the 796-dimensional Ideal-SVP Challenge. Our implementation may offer further insights into the behavior of asymptotically \u201cfast\u201d sieving algorithms when applied to large-scale problems. Moreover, our refined cost estimation of SVP based on this implementation suggests that some NIST PQC candidates (e.g. Falcon-512), are not sure to meet NIST\u2019s security requirements.<\/jats:p>","DOI":"10.46586\/tches.v2025.i2.362-384","type":"journal-article","created":{"date-parts":[[2025,3,5]],"date-time":"2025-03-05T11:02:44Z","timestamp":1741172564000},"page":"362-384","source":"Crossref","is-referenced-by-count":5,"title":["Sieving with Streaming Memory Access"],"prefix":"10.46586","volume":"2025","author":[{"given":"Ziyu","family":"Zhao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jintai","family":"Ding","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bo-Yin","family":"Yang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"25480","published-online":{"date-parts":[[2025,3,4]]},"container-title":["IACR Transactions on Cryptographic Hardware and Embedded Systems"],"original-title":[],"link":[{"URL":"https:\/\/tches.iacr.org\/index.php\/TCHES\/article\/download\/12051\/11895","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/tches.iacr.org\/index.php\/TCHES\/article\/download\/12051\/11895","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,5]],"date-time":"2025-03-05T11:02:44Z","timestamp":1741172564000},"score":1,"resource":{"primary":{"URL":"https:\/\/tches.iacr.org\/index.php\/TCHES\/article\/view\/12051"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,4]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,3,4]]}},"URL":"https:\/\/doi.org\/10.46586\/tches.v2025.i2.362-384","relation":{},"ISSN":["2569-2925"],"issn-type":[{"value":"2569-2925","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,4]]}}}