Paper 2018/569

Dissection-BKW

Andre Esser, Felix Heuer, Robert Kübler, Alexander May, and 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.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in CRYPTO 2018
Keywords
CryptanalysisLPNBKW algorithmDissectionTime-Memory Trade-Off
Contact author(s)
andre esser @ rub de
History
2018-06-05: received
Short URL
https://ia.cr/2018/569
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/569,
      author = {Andre Esser and Felix Heuer and Robert Kübler and Alexander May and Christian Sohler},
      title = {Dissection-{BKW}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/569},
      year = {2018},
      url = {https://eprint.iacr.org/2018/569}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.