Finding shortest lattice vectors faster using quantum search
From MaRDI portal
Publication:887421
DOI10.1007/s10623-015-0067-5zbMath1356.94069WikidataQ59410708 ScholiaQ59410708MaRDI QIDQ887421
Michele Mosca, Joop van de Pol, Thijs Laarhoven
Publication date: 26 October 2015
Published in: Designs, Codes and Cryptography (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10623-015-0067-5
81P68: Quantum computation
94A60: Cryptography
68Q12: Quantum algorithms and complexity in the theory of computing
Related Items
Lattice Sieving via Quantum Random Walks, SoK: how (not) to design and implement post-quantum cryptography, NTRU prime: reducing attack surface at low cost, Approximate Voronoi cells for lattices, revisited, A new post-quantum multivariate polynomial public key encapsulation algorithm, Lower bounds on lattice sieving and information set decoding, Pseudorandom functions in NC class from the standard LWE assumption, Quantum binary search algorithm, Practical \(\mathsf{MP} \text{- }\mathsf{LWE}\)-based encryption balancing security-risk versus efficiency, Estimation of the hardness of the learning with errors problem with a restricted number of samples, Improved classical and quantum algorithms for subset-sum, Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing
Uses Software
Cites Work
- A hierarchy of polynomial time lattice basis reduction algorithms
- Factoring polynomials with rational coefficients
- Improved low-density subset sum algorithms
- Lattice basis reduction: Improved practical algorithms and solving subset sum problems
- Small solutions to polynomial equations, and low exponent RSA vulnerabilities
- Short RSA keys and their generation
- (Leveled) fully homomorphic encryption without bootstrapping
- Lattice Signatures and Bimodal Gaussians
- A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
- A sieve algorithm based on overlattices
- Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
- Lattice Signatures without Trapdoors
- Solving the Shortest Vector Problem in 2 n Time Using Discrete Gaussian Sampling
- Optimal Data-Dependent Hashing for Approximate Near Neighbors
- Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing
- A Three-Level Sieve Algorithm for the Shortest Vector Problem
- Algorithms for the Shortest and Closest Lattice Vector Problems
- Quantum algorithms for algebraic problems
- BKZ 2.0: Better Lattice Security Estimates
- Quantum Random Access Memory
- Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
- Computing Logarithms in Finite Fields of Characteristic Two
- Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes
- Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
- Quantum Walk Based Search Algorithms
- Sieve algorithms for the shortest vector problem are practical
- Hardness of approximating the shortest vector problem in lattices
- Trapdoors for hard lattices and new cryptographic constructions
- Lattice Enumeration Using Extreme Pruning
- Similarity estimation techniques from rounding algorithms
- Exponentiation in Pairing-Friendly Groups Using Homomorphisms
- Solving low-density subset sum problems
- On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Strengths and Weaknesses of Quantum Computing
- Sieving for Shortest Vectors in Ideal Lattices
- Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search
- Fully homomorphic encryption using ideal lattices
- A sieve algorithm for the shortest lattice vector problem
- Algorithms and Computation
- Quantum Algorithms for Element Distinctness
- Beyond Locality-Sensitive Hashing
- Constructing elliptic curve isogenies in quantum subexponential time
- Parallel Gauss Sieve Algorithm: Solving the SVP Challenge over a 128-Dimensional Ideal Lattice
- Accelerated Verification of ECDSA Signatures
- Predicting Lattice Reduction
- A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
- Quantum cryptanalysis of hash and claw-free functions
- Encyclopedia of Complexity and Systems Science
- Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
- On lattices, learning with errors, random linear codes, and cryptography
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
