Sieving with Streaming Memory Access
Abstract: We implement an optimized BGJ (Becker–Gama–Joux 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’s inherent structure being much more memory-efficient than the BDGL (Becker–Ducas– Gama–Laahoven 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 ≥ 24.5x more efficient ga.... https://tches.iacr.org/index.php/TCHES/article/view/12051
- Location
-
Deutsche Nationalbibliothek Frankfurt am Main
- Extent
-
Online-Ressource
- Language
-
Englisch
- Bibliographic citation
-
Sieving with Streaming Memory Access ; volume:2025 ; number:2 ; year:2025
IACR transactions on cryptographic hardware and embedded systems ; 2025, Heft 2 (2025)
- Creator
-
Zhao, Ziyu
Ding, Jintai
Yang, Bo-Yin
- DOI
-
10.46586/tches.v2025.i2.362-384
- URN
-
urn:nbn:de:101:1-2503121759509.815448972809
- Rights
-
Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
- Last update
-
15.08.2025, 7:32 AM CEST
Data provider
Deutsche Nationalbibliothek. If you have any questions about the object, please contact the data provider.
Associated
- Zhao, Ziyu
- Ding, Jintai
- Yang, Bo-Yin
Other Objects (12)
Tunable video streaming for wireless access networks
Wheeler Winston Dixon: Streaming: Movies, Media, and Instant Access
Pimo: memory-efficient privacy protection in video streaming and analytics
Memory access integrity: detecting fine-grained memory access errors in binary code
Streaming Analytics with PostgreSQL
Protoplasmic Streaming
Protoplasmic Streaming
Streaming Media
All Nonmetal Resistive Random Access Memory
Quick-and-dirty memory access tracing with instruction-based sampling
Quality of experience and access network traffic management of HTTP adaptive video streaming
Quality of experience and access network traffic management of HTTP adaptive video streaming
Tunable video streaming for wireless access networks
Wheeler Winston Dixon: Streaming: Movies, Media, and Instant Access
Pimo: memory-efficient privacy protection in video streaming and analytics
Memory access integrity: detecting fine-grained memory access errors in binary code
Streaming Analytics with PostgreSQL
Protoplasmic Streaming
Protoplasmic Streaming
Streaming Media
All Nonmetal Resistive Random Access Memory
Quick-and-dirty memory access tracing with instruction-based sampling
Quality of experience and access network traffic management of HTTP adaptive video streaming
Quality of experience and access network traffic management of HTTP adaptive video streaming
Tunable video streaming for wireless access networks
Wheeler Winston Dixon: Streaming: Movies, Media, and Instant Access
Pimo: memory-efficient privacy protection in video streaming and analytics
Memory access integrity: detecting fine-grained memory access errors in binary code
Streaming Analytics with PostgreSQL
Protoplasmic Streaming
Protoplasmic Streaming
Streaming Media
All Nonmetal Resistive Random Access Memory
Quick-and-dirty memory access tracing with instruction-based sampling
Quality of experience and access network traffic management of HTTP adaptive video streaming