## CryptoDB

### Robert Kübler

#### Publications

Year
Venue
Title
2018
CRYPTO
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.
2017
CRYPTO

#### Coauthors

Andre Esser (2)
Felix Heuer (1)
Alexander May (2)
Christian Sohler (1)