Lattice sieving via quantum random walks
- URL: http://arxiv.org/abs/2105.05608v1
- Date: Wed, 12 May 2021 11:59:30 GMT
- Title: Lattice sieving via quantum random walks
- Authors: Andr\'e Chailloux and Johanna Loyer
- Abstract summary: 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.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Lattice-based cryptography is one of the leading proposals for post-quantum
cryptography. The Shortest Vector Problem (SVP) is arguably the most important
problem for the cryptanalysis of lattice-based cryptography, and many
lattice-based schemes have security claims based on its hardness. The best
quantum algorithm for the SVP is due to Laarhoven [Laa16 PhD] and runs in
(heuristic) time $2^{0.2653d + o(d)}$. In this article, we present an
improvement over Laarhoven's result and present an algorithm that has a
(heuristic) running time of $2^{0.2570 d + o(d)}$ where $d$ is the lattice
dimension. We also present time-memory trade-offs where we quantify the amount
of quantum memory and quantum random access memory of our algorithm. The core
idea is to replace Grover's algorithm used in [Laa16 PhD] in a key part of the
sieving algorithm by a quantum random walk in which we add a layer of local
sensitive filtering.
Related papers
- On the practicality of quantum sieving algorithms for the shortest vector problem [42.70026220176376]
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.
arXiv Detail & Related papers (2024-10-17T16:54:41Z) - Quantum Sieving for Code-Based Cryptanalysis and Its Limitations for ISD [0.0]
We introduce the first quantum algorithms for code sieving by designing quantum variants of the aforementioned sieving subroutine.
Our quantum-walk algorithm exploits the structure of the underlying search problem by adding a layer of locality-sensitive filtering.
Our analysis highlights that the framework should be adapted in order to outperform the state-of-the-art of quantum ISD algorithms.
arXiv Detail & Related papers (2024-08-29T11:47:33Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
We first examine the hardness of solving various search problems by hybrid quantum-classical strategies.
We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
arXiv Detail & Related papers (2023-11-07T04:59:02Z) - Finding dense sub-lattices as low-energy states of a Hamiltonian [1.2183430883527995]
Lattice-based cryptography is one of the most prominent candidates for post-quantum cryptography.
Shortest Vector Problem (SVP) is to find the shortest non-zero vector in a given lattice.
We study a natural generalization of the SVP known as the $K$-Densest Sub-lattice Problem ($K$-DSP): to find the densest $K$-dimensional sub-lattice of a given lattice.
arXiv Detail & Related papers (2023-09-28T08:48:38Z) - Homomorphic Encryption of the k=2 Bernstein-Vazirani Algorithm [0.4511923587827301]
We find an application of this scheme to quantum homomorphic encryption (QHE) which is an important cryptographic technology useful for delegated quantum computation.
We develop QHE schemes with perfect security, $mathcalF$-homomorphism, no interaction between server and client, and quasi-compactness bounded by $O(M)$ where M is the number of gates $T$ in the circuit.
arXiv Detail & Related papers (2023-03-30T14:49:15Z) - Distributed exact quantum algorithms for Bernstein-Vazirani and search
problems [9.146620606615889]
We give a distributed Bernstein-Vazirani algorithm (DBVA) with $t$ computing nodes, and a distributed exact Grover's algorithm (DEGA) that solve the search problem with only one target item in the unordered databases.
We provide situations of our DBVA and DEGA on MindQuantum (a quantum software) to validate the correctness and practicability of our methods.
arXiv Detail & Related papers (2023-03-19T14:18: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) - A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
We propose a variational quantum attack algorithm (VQAA) for classical AES-like symmetric cryptography.
In the VQAA, the known ciphertext is encoded as the ground state of a Hamiltonian that is constructed through a regular graph.
arXiv Detail & Related papers (2022-05-07T03:15:15Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$.
This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
arXiv Detail & Related papers (2021-06-11T09:43:09Z) - 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.