I've been learning about lattice cryptography and have noticed that most resources such as this survey by Chris Peikart, the Winter School on Lattice Cryptography etc don't include material on LPN, and typically only discuss SIS and LWE. According to this post, Are LPN and LWE problems equivalent?, LWE is a generalization of LPN. From what I understand, SVP (derived from SIS), and LWE are common lattice trapdoors. Is LPN not an important lattice trapdoor worth discussing? If it isn't, why is that the case?


1 Answer 1


LPN is code-based problem, not a lattice problem. These are quite similar, but are defined with respect to different notions of "distance" (Hamming vs $\ell_p$-norm). In general while there are broad parallels between the worlds of lattices and codes, these parallels are not exact.

A particular example is the hardness of computing the "smallest element" of code/lattice. For codes it is the minimum distance problem, for lattices it is the shortest vector problem. Stronger hardness results are known for MDP (SVP's best hardness results require randomized reductions, MDP's are deterministic). Other mathematical problems can vary wildly in difficulty --- the "sphere packing" problem for codes is much simpler than for lattices.

Of relevance to cryptography are worst-case to average-case reductions. This has been a large motivating factor for lattice cryptography since its inception in the 90's, but similar results for codes were only developed last year (and I believe the results themselves are somewhat weaker, but am not an expert). This paper states that its the first construction of collision-resistant hash functions from $\mathsf{LPN}$, which might help highlight the technical difference in the state of the art for lattice-based cryptography vs. code-based cryptography (for the construction of certain primitives).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.