Lower bounds on lattice sieving and information set decoding
From MaRDI portal
Publication:2128585
DOI10.1007/978-3-030-84245-1_27zbMath1486.94117OpenAlexW3186367696MaRDI QIDQ2128585
Thijs Laarhoven, Elena Kirshanova
Publication date: 22 April 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-84245-1_27
Quantum computation (81P68) Cryptography (94A60) Number-theoretic algorithms; complexity (11Y16) Quantum cryptography (quantum-theoretic aspects) (81P94)
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding shortest lattice vectors faster using quantum search
- Spherical rearrangements, subharmonic functions, and \(\ast\)-functions in \(n\)-space
- Decoding linear codes with high error rate and its impact for LPN security
- Shortest vector from lattice sieving: a few dimensions for free
- Speed-ups and time-memory trade-offs for tuple lattice sieving
- Lower bounds on lattice enumeration with extreme pruning
- Approximate Voronoi cells for lattices, revisited
- The randomized slicer for CVPP: sharper, faster, smaller, batchier
- Quantum algorithms for the approximate \(k\)-list problem and their application to lattice sieving
- The general sieve kernel and new records in lattice reduction
- Round5: compact and fast post-quantum public-key encryption
- Analysis of Information Set Decoding for a Sub-linear Error Weight
- Efficient (Ideal) Lattice Sieving Using Cross-Polytope LSH
- A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
- Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding
- Solving the Shortest Vector Problem in 2 n Time Using Discrete Gaussian Sampling
- Optimal Data-Dependent Hashing for Approximate Near Neighbors
- Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
- Faster Sieving for Shortest Lattice Vectors Using Spherical Locality-Sensitive Hashing
- On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes
- Tuple lattice sieving
- Decoding Random Linear Codes in $\tilde{\mathcal{O}}(2^{0.054n})$
- Improved Methods for Calculating Vectors of Short Length in a Lattice, Including a Complexity Analysis
- Extensions of Lipschitz mappings into a Hilbert space
- Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
- Sieve algorithms for the shortest vector problem are practical
- Lower Bounds on Locality Sensitive Hashing
- Trapdoors for hard lattices and new cryptographic constructions
- On Ideal Lattices and Learning with Errors over Rings
- Lattice Enumeration Using Extreme Pruning
- Entropy based nearest neighbor search in high dimensions
- Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere
- Efficient Public Key Encryption Based on Ideal Lattices
- A method for obtaining digital signatures and public-key cryptosystems
- New directions in nearest neighbor searching with applications to lattice sieving
- A Framework for Similarity Search with Space-Time Tradeoffs using Locality-Sensitive Filtering
- Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors
- Candidate Multilinear Maps from Ideal Lattices
- Sieve, Enumerate, Slice, and Lift:
- Fully homomorphic encryption using ideal lattices
- A sieve algorithm for the shortest lattice vector problem
- Beyond Locality-Sensitive Hashing
- Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
- The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1
- Improved Algorithms for the Approximate k-List Problem in Euclidean Norm
- On lattices, learning with errors, random linear codes, and cryptography
