On the complexity of the BKW algorithm on LWE
From MaRDI portal
Publication:2256097
DOI10.1007/s10623-013-9864-xzbMath1331.94051OpenAlexW2123314859MaRDI QIDQ2256097
Carlos Cid, Jean-Charles Faugère, Ludovic Perret, Robert Fitzpatrick, Martin R. Albrecht
Publication date: 19 February 2015
Published in: Designs, Codes and Cryptography (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10623-013-9864-x
learning with errors (LWE)Blum-Kalai-Wasserman (BKW) algorithmfully homomorphic encryption scheme (FHE)learning parity with noise (LPN)
Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
On solving LPN using BKW and variants, Implementation and analysis, An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices, Making the BKW algorithm practical for LWE, \(\mathsf{Rubato}\): noisy ciphers for approximate homomorphic encryption, Estimation of the hardness of the learning with errors problem with a restricted number of samples, Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS, On the asymptotic complexity of solving LWE, Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds, 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, Finding and evaluating parameters for BGV, Revisiting security estimation for LWE with hints from a geometric perspective, On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL, Enhancing Goldreich, Goldwasser and Halevi's scheme with intersecting lattices, TFHE: fast fully homomorphic encryption over the torus, MPSign: a signature from small-secret middle-product learning with errors, On bounded distance decoding with predicate: breaking the ``lattice barrier for the hidden number problem, Parallel Implementation of BDD Enumeration for LWE, Algebraic Aspects of Solving Ring-LWE, Including Ring-Based Improvements in the Blum--Kalai--Wasserman Algorithm
Uses Software
Cites Work
- Discrete Gaussian Leftover Hash Lemma over Infinite Domains
- H-LLL
- Low-dimensional lattice basis reduction revisited
- Lattice Reduction Algorithms: Theory and Practice
- Algorithms for the Shortest and Closest Lattice Vector Problems
- New Algorithms for Learning in Presence of Errors
- Better Key Sizes (and Attacks) for LWE-Based Encryption
- BKZ 2.0: Better Lattice Security Estimates
- Polly Cracker, Revisited
- SWIFFT: A Modest Proposal for FFT Hashing
- An Improved LPN Algorithm
- Trapdoors for hard lattices and new cryptographic constructions
- Lattice Enumeration Using Extreme Pruning
- Lattice-based Cryptography
- Solving BDD by Enumeration: An Update
- Fully homomorphic encryption using ideal lattices
- Analyzing Blockwise Lattice Algorithms Using Dynamical Systems
- How Far Can We Go Beyond Linear Cryptanalysis?
- Efficient Fully Homomorphic Encryption from (Standard) LWE
- Classical hardness of learning with errors
- Noise-tolerant learning, the parity problem, and the statistical query model
- On lattices, learning with errors, random linear codes, and cryptography
