An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices
From MaRDI portal
Publication:3457104
DOI10.1007/978-3-662-47989-6_3zbMath1336.94058arXiv1506.02717OpenAlexW2962941363MaRDI QIDQ3457104
Paul Kirchner, Pierre-Alain Fouque
Publication date: 10 December 2015
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1506.02717
Related Items (32)
Noisy Simon period finding ⋮ On the hardness of module-LWE with binary secret ⋮ How to meet ternary LWE keys ⋮ Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN ⋮ Making the BKW algorithm practical for LWE ⋮ Fiat-Shamir and correlation intractability from strong KDM-secure encryption ⋮ Tightly secure ring-LWE based key encapsulation with short ciphertexts ⋮ Predicting the concrete security of LWE against the dual attack using binary search ⋮ Faster Dual Lattice Attacks for Solving LWE with Applications to CRYSTALS ⋮ On the hardness of module learning with errors with short distributions ⋮ Efficient FHEW bootstrapping with small evaluation keys, and applications to threshold homomorphic encryption ⋮ On the asymptotic complexity of solving LWE ⋮ Optimization of $$\mathsf {LPN}$$ Solving Algorithms ⋮ A non-heuristic approach to time-space tradeoffs and optimizations for BKW ⋮ On the hardness of the NTRU problem ⋮ Modeling and simulating the sample complexity of solving LWE using BKW-style algorithms ⋮ A Practical Post-Quantum Public-Key Cryptosystem Based on $$\textsf {spLWE}$$ ⋮ An Experimental Study of Kannan’s Embedding Technique for the Search LWE Problem ⋮ LP Solutions of Vectorial Integer Subset Sums – Cryptanalysis of Galbraith’s Binary Matrix LWE ⋮ Revisiting Lattice Attacks on Overstretched NTRU Parameters ⋮ 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 ⋮ Solving LPN using covering codes ⋮ On bounded distance decoding with predicate: breaking the ``lattice barrier for the hidden number problem ⋮ Parallel Implementation of BDD Enumeration for LWE ⋮ On the success probability of solving unique SVP via BKZ ⋮ Towards Sound Fresh Re-keying with Hard (Physical) Learning Problems ⋮ A Subfield Lattice Attack on Overstretched NTRU Assumptions ⋮ Unnamed Item ⋮ Algebraic Aspects of Solving Ring-LWE, Including Ring-Based Improvements in the Blum--Kalai--Wasserman Algorithm ⋮ Lattice-Based SNARGs and Their Application to More Efficient Obfuscation ⋮ Quantum key search for ternary LWE
Uses Software
Cites Work
- Advances in cryptology -- CRYPTO 2009. 29th annual international cryptology conference, Santa Barbara, CA, USA, August 16--20, 2009. Proceedings
- Factoring polynomials with rational coefficients
- Improved low-density subset sum algorithms
- New bounds in some transference theorems in the geometry of numbers
- On the complexity of the BKW algorithm on LWE
- Hardness of SIS and LWE with Small Parameters
- Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based
- New Algorithms for Learning in Presence of Errors
- Better Key Sizes (and Attacks) for LWE-Based Encryption
- BKZ 2.0: Better Lattice Security Estimates
- Public-Key Cryptographic Primitives Provably as Secure as Subset Sum
- An Improved LPN Algorithm
- Solving low-density subset sum problems
- Quantization
- Solving BDD by Enumeration: An Update
- Lossy Codes and a New Variant of the Learning-With-Errors Problem
- On Ideal Lattices and Learning with Errors over Rings
- Lazy Modulus Switching for the BKW Algorithm on LWE
- Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$
- On lattices, learning with errors, random linear codes, and cryptography
- Noise-tolerant learning, the parity problem, and the statistical query model
This page was built for publication: An Improved BKW Algorithm for LWE with Applications to Cryptography and Lattices
