Paper 2021/1343
A Nonheuristic Approach to Timespace Tradeoffs and Optimizations for BKW
Abstract
Blum, Kalai and Wasserman (JACM 2003) gave the first subexponential 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+\epsilon)n}{\log n}}$ and time/sample complexity $2^{\frac{(1+\epsilon)n}{\log n}}\cdot 2^{O(n^{\frac{1}{1+\epsilon}})}$ for small constant $\epsilon\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: (Timespace tradeoff). We obtain the same timespace tradeoffs for LPN and LWE as those given by Esser et al. (Crypto 2018), but without resorting to any heuristics. For any $2\leq c\in\mathbb{N}$, our algorithm solves the LPN problem with time/sample complexity $2^{\frac{\log c(1+\epsilon)n}{\log n}}\cdot 2^{O(n^{\frac{1}{1+\epsilon}})}$ and space complexity $2^{\frac{\log c(1+\epsilon)n}{(c1)\log n}}$, 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 $2^{\frac{(1+\epsilon)n}{\log n}}$ for $\epsilon\to 0^+$, saving factor $2^{\Omega(n^{\frac{1}{1+\epsilon}})}$ 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 $2^{\Omega(n^{\frac{1}{1+\epsilon}})}$ 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 $Q=n^{1+\epsilon}$ (resp., $Q=2^{n^{\epsilon}}$) samples, our algorithm saves a factor of $2^{\Omega(n)/(\log n)^{1\kappa}}$ (resp., $2^{\Omega(n^{\kappa})}$) for constant $\kappa \to 1^$ 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).
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A major revision of an IACR publication in ASIACRYPT 2022
 Keywords
 Learning Parity with Noise BKW
 Contact author(s)

hans1024 @ sjtu edu cn
yuyuathk @ gmail com  History
 20220908: last of 4 revisions
 20211007: received
 See all versions
 Short URL
 https://ia.cr/2021/1343
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1343, author = {Hanlin Liu and Yu Yu}, title = {A Nonheuristic Approach to Timespace Tradeoffs and Optimizations for BKW}, howpublished = {Cryptology ePrint Archive, Paper 2021/1343}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/1343}}, url = {https://eprint.iacr.org/2021/1343} }