Finding shortest lattice vectors faster using quantum search
From MaRDI portal
Recommendations
- Solving the shortest vector problem in lattices faster using quantum search
- Quantum algorithms for the approximate \(k\)-list problem and their application to lattice sieving
- Lattice Sieving via Quantum Random Walks
- Algorithms and Computation
- On the shortness of vectors to be found by the ideal-SVP quantum algorithm
Cites work
- (Leveled) fully homomorphic encryption without bootstrapping
- A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations
- A hierarchy of polynomial time lattice basis reduction algorithms
- A sieve algorithm based on overlattices
- A sieve algorithm for the shortest lattice vector problem
- A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
- A three-level sieve algorithm for the shortest vector problem
- Accelerated Verification of ECDSA Signatures
- Algorithms and Computation
- Algorithms for the shortest and closest lattice vector problems
- Beyond locality-sensitive hashing
- BKZ 2.0: Better lattice security estimates
- Computing Logarithms in Finite Fields of Characteristic Two
- Constructing elliptic curve isogenies in quantum subexponential time
- Encyclopedia of Complexity and Systems Science
- Exponentiation in Pairing-Friendly Groups Using Homomorphisms
- Factoring polynomials with rational coefficients
- Faster exponential time algorithms for the shortest vector problem
- Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing
- Fully homomorphic encryption using ideal lattices
- Hardness of approximating the shortest vector problem in lattices
- Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes
- How significant are the known collision and element distinctness quantum algorithms?
- scientific article; zbMATH DE number 1186948 (Why is no real title available?)
- scientific article; zbMATH DE number 3633251 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 691485 (Why is no real title available?)
- scientific article; zbMATH DE number 1962809 (Why is no real title available?)
- scientific article; zbMATH DE number 1775383 (Why is no real title available?)
- scientific article; zbMATH DE number 954401 (Why is no real title available?)
- scientific article; zbMATH DE number 1842492 (Why is no real title available?)
- scientific article; zbMATH DE number 2103524 (Why is no real title available?)
- Improved low-density subset sum algorithms
- Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
- Lattice basis reduction: Improved practical algorithms and solving subset sum problems
- Lattice enumeration using extreme pruning
- Lattice signatures and bimodal Gaussians
- Lattice signatures without trapdoors
- On lattices, learning with errors, random linear codes, and cryptography
- On the computation of lattice vectors of minimal length, successive minima and reduced bases with applications
- Optimal data-dependent hashing for approximate near neighbors
- Parallel Gauss sieve algorithm: solving the SVP challenge over a 128-dimensional ideal lattice
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
- Predicting Lattice Reduction
- Quantum algorithms for algebraic problems
- Quantum Algorithms for Element Distinctness
- Quantum cryptanalysis of hash and claw-free functions
- Quantum random access memory
- Quantum Walk Based Search Algorithms
- Short RSA keys and their generation
- Sieve algorithms for the shortest vector problem are practical
- Sieving for shortest vectors in ideal lattices
- Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
- Similarity estimation techniques from rounding algorithms
- Small solutions to polynomial equations, and low exponent RSA vulnerabilities
- Solving low-density subset sum problems
- Solving the shortest vector problem in 2ⁿ time using discrete Gaussian sampling (extended abstract)
- Solving the shortest vector problem in lattices faster using quantum search
- Strengths and Weaknesses of Quantum Computing
- Trapdoors for hard lattices and new cryptographic constructions
- Trapdoors for lattices: simpler, tighter, faster, smaller
Cited in
(33)- NTRU prime: reducing attack surface at low cost
- Optimization of search space for finding very short lattice vectors
- 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
- On the shortness of vectors to be found by the ideal-SVP quantum algorithm
- Quantum algorithms for the approximate \(k\)-list problem and their application to lattice sieving
- Pseudorandom functions in NC class from the standard LWE assumption
- Quantum LLL with an application to Mersenne number cryptosystems
- 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
- Estimating quantum speedups for lattice sieves
- Improved classical and quantum algorithms for subset-sum
- Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing
- Solving the shortest vector problem in lattices faster using quantum search
- Algorithms and Computation
- Lattice Sieving via Quantum Random Walks
- Finding shortest vector using quantum NV sieve on Grover
- Concrete analysis of approximate ideal-SIVP to decision ring-LWE reduction
- Further improvements of the estimation of key enumeration with applications to solving LWE
- Estimates of implementation complexity for quantum cryptanalysis of post-quantum lattice-based cryptosystems
- Post-quantum cryptosystems: open problems and solutions. Lattice-based cryptosystems
- PolarKyber: polished Kyber with smaller ciphertexts, greater security redundancy, and lower decryption failure rate
- Development and comparison of quantum oracle models for the hybrid attack on post-quantum lattice-based cryptosystems
- Development and analysis of oracle for the hibrid attack on a cryptographic system NTRU using a quantum search algorithm
- Current paradigms for construction of lattice-based digital signature schemes
- A new quantum oracle model for a hybrid quantum-classical attack on post-quantum lattice-based cryptosystems
- Improved classical and quantum algorithms for the shortest vector problem via bounded distance decoding
- Improved (provable) algorithms for the shortest vector problem via bounded distance decoding
- On the practicality of quantum sieving algorithms for the shortest vector problem
- Quantum procedures for nested search problems -- with applications in cryptanalysis
- SoK: how (not) to design and implement post-quantum cryptography
This page was built for publication: Finding shortest lattice vectors faster using quantum search
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q887421)
