**Dissection-BKW**

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

**Category / Keywords: **Cryptanalysis, LPN, BKW algorithm, Dissection, Time-Memory Trade-Off

**Original Publication**** (with major differences): **IACR-CRYPTO-2018

**Date: **received 1 Jun 2018, last revised 5 Jun 2018

**Contact author: **andre esser at rub de

**Available format(s): **PDF | BibTeX Citation

**Version: **20180605:115013 (All versions of this report)

**Short URL: **ia.cr/2018/569

[ Cryptology ePrint archive ]