I have a question regarding the relationship between the (search) LPN problem and the GapSVP problem.

I have read a related problem that explains the main theorem in Reg05: the GapSVP problem can be reduced to a search LWE problem (especially, the modulus $p>2\sqrt{n}$).

What is the direct connection between LWE and GapSVP?

However, regarding the hardness of the search LPN problem, I noticed that some papers just introduce that the known fastest algorithm that solves the search LPN problem needs $2^{O(n/\log n)}$ time (i.e. BKW algorithm).

I was wondering, whether there are some similar mature results about the relation between the search LPN problem and the GapSVP problem? Or, we believe the search LPN problem is hard, SOLELY because there is no known attack in polynomial time?

Many thanks.

  • 1
    $\begingroup$ There is no known reduction from GapSVP (or any other conjectured-hard worst-case lattice problem) to LPN, like there is for LWE. The conjectured hardness of LPN is mainly due to known algorithms for it being so inefficient. $\endgroup$ – Chris Peikert Feb 23 at 20:05
  • $\begingroup$ Many thanks for your answer! $\endgroup$ – M.Z. Feb 24 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.