Finding shortest lattice vectors faster using quantum search
From MaRDI portal
Publication:887421
DOI10.1007/s10623-015-0067-5zbMath1356.94069OpenAlexW1992938819WikidataQ59410708 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
Quantum computation (81P68) Cryptography (94A60) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items (12)
SoK: how (not) to design and implement post-quantum cryptography ⋮ Lower bounds on lattice sieving and information set decoding ⋮ Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing ⋮ Estimation of the hardness of the learning with errors problem with a restricted number of samples ⋮ Lattice Sieving via Quantum Random Walks ⋮ Improved classical and quantum algorithms for subset-sum ⋮ NTRU prime: reducing attack surface at low cost ⋮ Pseudorandom functions in NC class from the standard LWE assumption ⋮ Approximate Voronoi cells for lattices, revisited ⋮ Quantum binary search algorithm ⋮ Practical \(\mathsf{MP} \text{- }\mathsf{LWE}\)-based encryption balancing security-risk versus efficiency ⋮ A new post-quantum multivariate polynomial public key encapsulation algorithm
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
This page was built for publication: Finding shortest lattice vectors faster using quantum search
