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

• URL: http://arxiv.org/abs/2410.13759v1
• Date: Thu, 17 Oct 2024 16:54:41 GMT
• Title: On the practicality of quantum sieving algorithms for the shortest vector problem
• Authors: Joao F. Doriguello, George Giapitzakis, Alessandro Luongo, Aditya Morolia,
• Abstract summary: lattice-based cryptography is one of the main candidates of post-quantum cryptography. cryptographic security against quantum attackers is based on lattice problems like the shortest vector problem (SVP) Asymptotic quantum speedups for solving SVP are known and rely on Grover's search.
• Score: 42.70026220176376
• License:
• 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.

Related papers

• Grover's oracle for the Shortest Vector Problem and its application in hybrid classical-quantum solvers [0.38366697175402226]
  Finding the shortest vector in a lattice is a problem that is believed to be hard both for classical and quantum computers. Finding the best classical, quantum or hybrid classical-quantum algorithms for SVP is necessary to select cryptosystem parameters that offer sufficient level of security. Grover's search quantum algorithm provides a generic quadratic speed-up. We analyze how to combine Grover's quantum search for small SVP instances with state-of-the-art classical solvers.
  arXiv  Detail & Related papers  (2024-02-21T16:05:49Z)
• Variational Quantum Search with Shallow Depth for Unstructured Database Search [0.0]
  Variational Quantum Search (VQS) is a novel algorithm based on variational quantum algorithms and parameterized quantum circuits. We show that a depth-10 Ansatz can amplify the total probability of $k$ out of $2n$ elements represented by $n$+1 qubits. We demonstrate that a depth-56 circuit in VQS can replace a depth-270,989 circuit in Grover's algorithm.
  arXiv  Detail & Related papers  (2022-12-16T17:16:54Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• The NISQ Complexity of Collision Finding [2.9405711598281536]
  A fundamental primitive in modern cryptography, collision-resistant hashing ensures there is no efficient way to find inputs that produce the same hash value. Quantum adversaries now require full-scale computers equipped with the power of NISQ. In this paper, we investigate three different models for NISQ algorithms achieve tight bounds for all of them.
  arXiv  Detail & Related papers  (2022-11-23T13:55:28Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCS aims at index searching and counting in a quantum-classical hybrid system. We implement IQuCS with Qiskit and conduct intensive experiments. Results demonstrate that it reduces qubits consumption by up to 66.2%.
  arXiv  Detail & Related papers  (2022-09-22T21:54:28Z)
• Quantum Speedup for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection [2.5272389610447856]
  We propose a quantum algorithm that supports a real-valued higher-order unconstrained binary optimization problem. The proposed algorithm is capable of reducing the query complexity in the classical domain and providing a quadratic speedup in the quantum domain.
  arXiv  Detail & Related papers  (2022-05-31T00:14:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Lattice sieving via quantum random walks [0.0]
  lattice-based cryptography is one of the leading proposals for post-quantum cryptography. Shortest Vector Problem (SVP) is arguably the most important problem for the cryptanalysis of lattice-based cryptography. We present an algorithm that has a (heuristic) running time of $20.2570 d + o(d)$ where $d$ is the lattice dimension.
  arXiv  Detail & Related papers  (2021-05-12T11:59:30Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.