On the asymptotic complexity of solving LWE
From MaRDI portal
Publication:1692148
DOI10.1007/s10623-016-0326-0zbMath1381.94071OpenAlexW2574098266MaRDI QIDQ1692148
Gottfried Herold, Elena Kirshanova, Alexander May
Publication date: 26 January 2018
Published in: Designs, Codes and Cryptography (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10623-016-0326-0
Related Items (8)
Dual lattice attacks for closest vector problems (with preprocessing) ⋮ Making the BKW algorithm practical for LWE ⋮ Fiat-Shamir and correlation intractability from strong KDM-secure encryption ⋮ A non-heuristic approach to time-space tradeoffs and optimizations for BKW ⋮ Modeling and simulating the sample complexity of solving LWE using BKW-style algorithms ⋮ Limits on the efficiency of (ring) LWE-based non-interactive key exchange ⋮ On bounded distance decoding with predicate: breaking the ``lattice barrier for the hidden number problem ⋮ Algebraic Aspects of Solving Ring-LWE, Including Ring-Based Improvements in the Blum--Kalai--Wasserman Algorithm
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the concrete hardness of learning with errors
- New bounds in some transference theorems in the geometry of numbers
- Lattice basis reduction: Improved practical algorithms and solving subset sum problems
- On the limits of nonapproximability of lattice problems
- On the complexity of the BKW algorithm on LWE
- Parallel Implementation of BDD Enumeration for LWE
- Key-Private Proxy Re-encryption under LWE
- A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
- Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
- Low Noise LPN: KDM Secure Public Key Encryption and Sample Amplification
- Solving the Shortest Vector Problem in 2 n Time Using Discrete Gaussian Sampling
- Better Algorithms for LWE and LWR
- New Algorithms for Learning in Presence of Errors
- Better Key Sizes (and Attacks) for LWE-Based Encryption
- On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem
- Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems
- Sieving for Shortest Vectors in Lattices Using Angular Locality-Sensitive Hashing
- Coded-BKW: Solving LWE Using Lattice Codes
- An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices
- An Improved LPN Algorithm
- Trapdoors for hard lattices and new cryptographic constructions
- Lattice Enumeration Using Extreme Pruning
- Factorization of a 768-Bit RSA Modulus
- Improved Analysis of Kannan’s Shortest Lattice Vector Algorithm
- Lattice-based Cryptography
- Minkowski's Convex Body Theorem and Integer Programming
- New directions in nearest neighbor searching with applications to lattice sieving
- Solving BDD by Enumeration: An Update
- Public-key cryptosystems from the worst-case shortest vector problem
- A sieve algorithm for the shortest lattice vector problem
- Analyzing Blockwise Lattice Algorithms Using Dynamical Systems
- Lazy Modulus Switching for the BKW Algorithm on LWE
- Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
- Predicting Lattice Reduction
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Classical hardness of learning with errors
- A Theorem on the Geometry of Numbers
- Noise-tolerant learning, the parity problem, and the statistical query model
- On lattices, learning with errors, random linear codes, and cryptography
- Selecting cryptographic key sizes
This page was built for publication: On the asymptotic complexity of solving LWE
