International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Dissection-BKW

Authors:
Andre Esser
Felix Heuer
Robert Kübler
Alexander May
Christian Sohler
Download:
DOI: 10.1007/978-3-319-96881-0_22 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2018
Abstract: The slightly subexponential algorithm of Blum, Kalai and Wasserman (BKW) provides a basis for assessing LPN/LWE security. However, its huge memory consumption strongly limits its practical applicability, thereby preventing precise security estimates for cryptographic LPN/LWE instantiations.We provide the first time-memory trade-offs for the BKW algorithm. For instance, we show how to solve LPN in dimension k in time $$2^{\frac{4}{3} \frac{k}{\log k} }$$ and memory $$2^{\frac{2}{3} \frac{k}{\log k} }$$. Using the Dissection technique due to Dinur et al. (Crypto ’12) and a novel, slight generalization thereof, we obtain fine-grained trade-offs for any available (subexponential) memory while the running time remains subexponential.Reducing the memory consumption of BKW below its running time also allows us to propose a first quantum version QBKW for the BKW algorithm.
Video from CRYPTO 2018
BibTeX
@inproceedings{crypto-2018-28828,
  title={Dissection-BKW},
  booktitle={Advances in Cryptology – CRYPTO 2018},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={10992},
  pages={638-666},
  doi={10.1007/978-3-319-96881-0_22},
  author={Andre Esser and Felix Heuer and Robert Kübler and Alexander May and Christian Sohler},
  year=2018
}