Paper 2021/1343

A Non-heuristic Approach to Time-space Tradeoffs and Optimizations for BKW

Abstract

Blum, Kalai and Wasserman (JACM 2003) gave the first sub-exponential algorithm to solve the Learning Parity with Noise (LPN) problem. In particular, consider the LPN problem with constant noise $\mu =(1-\gamma )/2$. The BKW solves it with space complexity $2^{\frac{(1+ϵ)n}{\log n}}$ and time/sample complexity $2^{\frac{(1+ϵ)n}{\log n}}\cdot 2^{O(n^{\frac{1}{1+ϵ}})}$ for small constant $ϵ\to 0^{+}$. We propose a variant of the BKW by tweaking Wagner's generalized birthday problem (Crypto 2002) and adapting the technique to a $c$-ary tree structure. In summary, our algorithm achieves the following: (Time-space tradeoff). We obtain the same time-space tradeoffs for LPN and LWE as those given by Esser et al. (Crypto 2018), but without resorting to any heuristics. For any $$, our algorithm solves the LPN problem with time/sample complexity $$ and space complexity $$, where one can use Grover's quantum algorithm or Dinur et al.'s dissection technique (Crypto 2012) to further accelerate/optimize the time complexity. (Time/sample optimization). A further adjusted variant of our algorithm solves the LPN problem with sample, time and space complexities all kept at $$ for $$, saving factor $$ in time/sample compared to the original BKW, and the variant of Devadas et al. (TCC 2017). This benefits from a careful analysis of the error distribution among the correlated candidates, and therefore avoids repeating the same process $$ times on fresh new samples. (Sample reduction) Our algorithm provides an alternative to Lyubashevsky's BKW variant (RANDOM 2005) for LPN with a restricted amount of samples. In particular, given $$ (resp., $$) samples, our algorithm saves a factor of $$ (resp., $$) for constant $$ in running time while consuming roughly the same space, compared with Lyubashevsky's algorithm. We seek to bridge the gaps between theoretical and heuristic LPN solvers, but take a different approach from Devadas et al. (TCC 2017). We exploit weak yet sufficient conditions (e.g., pairwise independence), and the analysis uses only elementary tools (e.g., Chebyshev's inequality).