Welcome to the resource topic for 2018/569
Title:
Dissection-BKW
Authors: Andre Esser, Felix Heuer, Robert Kübler, Alexander May, Christian Sohler
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 43\frac k{\log k}} and memory 2^{\frac 23\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.
ePrint: https://eprint.iacr.org/2018/569
Talk: https://www.youtube.com/watch?v=3Or3Puh7O0M
Slides: https://crypto.iacr.org/2018/slides/Dissection-BKW.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .