Paper 2018/279
WorstCase Hardness for LPN and Cryptographic Hashing via Code Smoothing
Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, and Daniel Wichs
Abstract
We present a worst case decoding problem whose hardness reduces to that of solving the Learning Parity with Noise (LPN) problem, in some parameter regime. Prior to this work, no worst case hardness result was known for LPN (as opposed to syntactically similar problems such as Learning with Errors). The caveat is that this worst case problem is only mildly hard and in particular admits a quasipolynomial time algorithm, whereas the LPN variant used in the reduction requires extremely high noise rate of $1/21/poly(n)$. Thus we can only show that ``very hard'' LPN is harder than some ``very mildly hard'' worst case problem. We note that LPN with noise $1/21/poly(n)$ already implies symmetric cryptography. Specifically, we consider the (n,m,w)nearest codeword problem ($(n,m,w)$NCP) which takes as input a generating matrix for a binary linear code in $m$ dimensions and rank $n$, and a target vector which is very close to the code (Hamming distance at most $w$), and asks to find the codeword nearest to the target vector. We show that for balanced (unbiased) codes and for relative error $w/m \approx {\log^2 n}/{n}$, $(n,m,w)$NCP can be solved given oracle access to an LPN distinguisher with noise ratio $1/21/poly(n)$. Our proof relies on a smoothing lemma for codes which we show to have further implications: We show that $(n,m,w)$NCP with the aforementioned parameters lies in the complexity class $\text{SearchBPP}^{SZK}$ (i.e. reducible to a problem that has a statistical zero knowledge protocol) implying that it is unlikely to be $\mathcal{NP}$hard. We then show that LPN with very low noise rate $\log^2(n)/n$ implies the existence of collision resistant hash functions (our aforementioned result implies that in this parameter regime LPN is also in $\text{BPP}^\text{SZK})$.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published by the IACR in EUROCRYPT 2019
 Keywords
 LPNWorstCase to Average Case ReductionsCollisionResistant Hashing
 Contact author(s)
 vadim lyubash @ gmail com
 History
 20190227: last of 3 revisions
 20180322: received
 See all versions
 Short URL
 https://ia.cr/2018/279
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/279, author = {Zvika Brakerski and Vadim Lyubashevsky and Vinod Vaikuntanathan and Daniel Wichs}, title = {WorstCase Hardness for LPN and Cryptographic Hashing via Code Smoothing}, howpublished = {Cryptology ePrint Archive, Paper 2018/279}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/279}}, url = {https://eprint.iacr.org/2018/279} }