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

MAKE IMPACT

João F. Doriguello , George Giapitzakis , Alessandro Luongo , Aditya Morolia · YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2410.13759

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 $μ$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.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2410.13759

PDF

https://arxiv.org/pdf/2410.13759

OA Status

green

Cited By

1

Related Works

10

OpenAlex ID

https://openalex.org/W4403580081

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4403580081

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2410.13759

Digital Object Identifier

Title

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

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2024

Year of publication

Publication date

2024-10-17

Full publication date if available

Authors

João F. Doriguello, George Giapitzakis, Alessandro Luongo, Aditya Morolia

List of authors in order

Landing page

https://arxiv.org/abs/2410.13759

Publisher landing page

PDF URL

https://arxiv.org/pdf/2410.13759

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2410.13759

Direct OA link when available

Concepts

Computer science, Quantum, Algorithm, Mathematical optimization, Theoretical computer science, Mathematics, Physics, Quantum mechanics

Top concepts (fields/topics) attached by OpenAlex

Cited by

1

Total citation count in OpenAlex

Citations by year (recent)

2025: 1

Per-year citation counts (last 5 years)

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload