On the practicality of quantum sieving algorithms for the shortest vector problem

[2410.13759] On the practicality of quantum sieving algorithms for the shortest vector problem Skip to main content Search Submit Donate Log in Search arXiv Press Enter to search · Advanced search Quantum Physics arXiv:2410.13759 (quant-ph) [Submitted on 17 Oct 2024 ( v1 ), last revised 17 Feb 2025 (this version, v2)] Title: On the practicality of quantum sieving algorithms for the shortest vector problem Authors: Joao F. Doriguello , George Giapitzakis , Alessandro Luongo , Aditya Morolia View a PDF of the paper titled On the practicality of quantum sieving algorithms for the shortest vector problem, by Joao F. Doriguello and 3 other authors View PDF HTML (experimental) Abstract: One of the main candidates of post-quantum cryptography is lattice-based cryptography. Its cryptographic security against quantum attackers is based on the worst-case hardness of lattice problems like the shortest vector problem (SVP), which asks to find the shortest non-zero vector in an integer lattice. Asymptotic quantum speedups for solving SVP are known and rely on Grover's search. However, to assess the security of lattice-based cryptography against these Grover-like quantum speedups, it is necessary to carry out a precise resource estimation beyond asymptotic scalings. In this work, we perform a careful analysis on the resources required to implement several sieving algorithms aided by Grover's search for dimensions of cryptographic interests. For such, we take into account fixed-point quantum arithmetic operations, non-asymptotic Grover's search, the cost of using quantum random access memory (QRAM), different physical architectures, and quantum error correction. We find that even under very optimistic assumptions like circuit-level noise of $10^{-5}$, code cycles of 100 ns, reaction time of 1 $\mu$s, and using state-of-the-art arithmetic circuits and quantum error-correction protocols, the best sieving algorithms require $\approx 10^{13}$ physical qubits and $\approx 10^{31}$ years to solve SVP on a lattice of dimension 400, which is roughly the dimension for minimally secure post-quantum cryptographic standards currently being proposed by NIST. We estimate that a 6-GHz-clock-rate single-core classical computer would take roughly the same amount of time to solve the same problem. We conclude that there is currently little to no quantum speedup in the dimensions of cryptographic interest and the possibility of realising a considerable quantum speedup using quantum sieving algorithms would require significant breakthroughs in theoretical protocols and hardware development. Comments: 60+4 pages, 7+4 figures. v2: references added, extended the results up to lattice dimension 1000 Subjects: Quantum Physics (quant-ph) ; Cryptography and Security (cs.CR) Cite as: arXiv:2410.13759 [quant-ph] (or arXiv:2410.13759v2 [quant-ph] for this version) https://doi.org/10.48550/arXiv.2410.13759 Focus to learn more arXiv-issued DOI via DataCite Journal reference: PQCrypto 2026. Lecture Notes in Computer Science, vol 16491. Springer, Cham Related DOI : https://doi.org/10.1007/978-3-032-22695-2_1 Focus to learn more DOI(s) linking to related resources Submission history From: Joao F. Doriguello [ view email ] [v1] Thu, 17 Oct 2024 16:54:41 UTC (2,413 KB) [v2] Mon, 17 Feb 2025 22:16:30 UTC (3,608 KB) Full-text links: Access Paper: View a PDF of the paper titled On the practicality of quantum sieving algorithms for the shortest vector problem, by Joao F. Doriguello and 3 other authors View PDF HTML (experimental) TeX Source view license Current browse context: quant-ph < prev | next > new | recent | 2024-10 Change to browse by: cs cs.CR References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar export BibTeX citation Loading... BibTeX formatted citation × loading... Data provided by: Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer ( What is the Explorer? ) Connected Papers Toggle Connected Papers ( What is Connected Papers? ) Litmaps Toggle Litmaps ( What is Litmaps? ) scite.ai Toggle scite Smart Citations ( What are Smart Citations? ) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv ( What is alphaXiv? ) Links to Code Toggle CatalyzeX Code Finder for Papers ( What is CatalyzeX? ) DagsHub Toggle DagsHub ( What is DagsHub? ) GotitPub Toggle Gotit.pub ( What is GotitPub? ) Huggingface Toggle Hugging Face ( What is Huggingface? ) ScienceCast Toggle ScienceCast ( What is ScienceCast? ) Demos Demos Replicate Toggle Replicate ( What is Replicate? ) Spaces Toggle Hugging Face Spaces ( What is Spaces? ) Spaces Toggle TXYZ.AI ( What is TXYZ.AI? ) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower ( What are Influence Flowers? ) Core recommender toggle CORE Recommender ( What is CORE? ) Author Venue Institution Topic About arXivLabs arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs . Which authors of this paper are endorsers? | Disable MathJax ( What is MathJax? ) We gratefully acknowledge support from our major funders , member institutions , , and all contributors. About · Help · Contact · Subscribe · Copyright · Privacy · Accessibility · Operational Status (opens in new tab) Major funding support from

Related documents

• Complexity Amplification from Compression in Quantum Random Access Optimization#975154
• Classical-Quantum Algorithm for Solving Stochastic Programs#631401
• Constrained minimax approximation for quantum signal processing#818979
• Constrained minimax approximation for quantum signal processing#808987
• An Overview of Quantum Algorithms and their Impact#97292