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

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 and dimension n. The BKW solves it with space complexity 2(1+ϵ)nlog(n) and time/sample complexity 2(1+ϵ)nlog(n)·2Ω(n11+ϵ) for small constant ϵ→ 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: 1.(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 2 ≤ c∈ N, our algorithm solves the LPN problem with time complexity 2log(c)(1+ϵ)nlog(n)·2Ω(n11+ϵ) and space complexity 2log(c)(1+ϵ)n(c-1)log(n) for ϵ→ 0 ⁺, where one can use Grover’s quantum algorithm or Dinur et al.’s dissection technique (Crypto 2012) to further accelerate/optimize the time complexity.2.(Time/sample optimization). A further adjusted variant of our algorithm solves the LPN problem with sample, time and space complexities all kept at 2(1+ϵ)nlog(n), saving factor 2Ω(n11+ϵ) for ϵ→ 0 ⁺ in time/sample compared to the original BKW, and the variant of Devadas et al. (TCC 2017).3.(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 Q= n^1+ϵ (resp., Q=2nϵ ) samples for any constant ϵ> 0, our algorithm saves a factor of 2Ω(n)/log(n)1-κ (resp., 2Ω(nκ) ) for constant κ→ 1 ^- in running time while consuming roughly the same space, compared with Lyubashevsky’s algorithm. In particular, the time/sample optimization benefits from a careful analysis of the error distribution among the correlated candidates, which was not studied by previous rigorous approaches such as the analysis of Minder and Sinclair (J.Cryptology 2012) or Devadas et al. (TCC 2017).