7
$\begingroup$

Learning with Error (LWE) problem seems like a generalization of Learning Parity with Noise (LPN) problem, where in the latter one uses bits. But, this also makes LPN seem very related to the problem of decoding a random linear code. I was just wondering whether LPN is equivalent to the problem of decoding a random linear code? And whether there are some positive or negative results about the equivalence of LPN and LWE?

$\endgroup$
7
$\begingroup$

Yes, LPN is (essentially by definition) equivalent to the hardness of decoding a random linear code over $\mathbb{F}_2$. No, there is no known reductions between LPN and LWE. It is usually believed that LPN is (in some sense) "harder to break" than LWE, simply because we know much less attacks on LPN. It seems to have less structure that could be exploited in advanced attacks - but also, for the very same reason, has far less known applications. Yet, no formal reduction relating any of them is known. It should also be mentioned (thanks for TMM for pointing that out) that the best known attack on LPN takes time $2^{O(n/\log n)}$ (where $n$ is the dimension) while the best known attack on LWE takes time $2^{O(n)}$ - hence LWE appears stronger than LPN when considering solely the running time of the best known algorithms.

Note that while they clearly seem related, there is a fundamental difference: LWE uses a Gaussian noise, while LPN uses a Bernouilli noise. The first type crucially relies on some "non-black box" considerations on the field where it's implemented (since we need to be able to talk about "small" and "big" field elements), while the latter one is actually completely oblivious to the field (i.e., you can define LPN over a field in a way that makes a black-box use of the field).

To elaborate on your sentence "Learning with Error (LWE) problem seems like a generalization of Learning Parity with Noise (LPN) problem, where in the latter one uses bits": it's not really the case, actually. The natural generalization of LPN to a larger field $\mathbb{F}$ would be obtained by adding to each linear equation a noise which is a uniformly random element with some probability $p$, and $0$ with probability $1-p$ (this is the natural generalization of the Bernoulli noise over $\mathbb{F}$). LWE, instead, uses a small Gaussian noise everywhere, which is quite different.

EDIT: to clarify, the last paragraph above is my point of view, but not the formal "demonstration" that LWE is not a generalization of LPN. As pointed out by TMM and Chris Peikert in the comment, the Bernoulli distribution over $\mathbb{F}_2$ can technically be seen as a Gaussian distribution - hence LPN can be seen as LWE over $\mathbb{F}_2$ (or conversely, LWE can be seen as the generalization of LPN over larger fields). My point in the last paragraph is that this is not the only possible generalization, and the alternative one which I mention seems to me much closer in spirit to the original LPN assumption: under the "LPN over large fields with Bernoulli noise", one gets essentially the same implications as with standard LPN (e.g. public key encryption, but not collision resistance), and the same structural properties (i.e. the best known attacks on this generalization are the natural generalizations of the best known attacks on LPN over $\mathbb{F}_2$). LWE is technically a generalization of LPN over larger fields, but one with important differences compared to the original LPN assumption (different attacks, different (and much more "advanced") implications, non-black-box use of the field, etc).

$\endgroup$
  • 2
    $\begingroup$ Can't a Bernoulli distribution also be interpreted as a discrete Gaussian over $\{0, 1\}$? And true, there may be fewer attacks to consider for LPN, but the best attacks on LPN run in subexponential time in the dimension, compared to exponential for LWE with well-chosen parameters - saying that LPN is "harder to break" therefore needs a bit of an explanation to not mislead readers. $\endgroup$ – TMM Dec 21 '18 at 11:13
  • $\begingroup$ Yes, you can interpret is as such. It's technically correct, but obfuscates the fact that LPN is not "structurally" equivalent to LWE, in the sense that the vast majority of applications we know from LWE cannot (as far as we know) be realised from LPN. Regarding the attacks: you are right, there is a $2^{O(n/\log n)}$ attack on LPN, at least for the most standard tradeoffs between the parameters. It requires as much memory though (if we insist on having polynomially many samples, the cost drops to $2^{O(n/\log\log n)}$). I will update to clarify. $\endgroup$ – Geoffroy Couteau Dec 21 '18 at 11:23
  • 1
    $\begingroup$ So how are they not "structurally" equivalent, if LPN can essentially be seen as LWE instantiated with a fixed parameter $q=2$? And the best attacks for LWE also have exponential time and memory, or polynomial memory and superexponential time. (And at the end I suppose you meant the cost increases to $2^{O(n/\log \log n)}$, rather than drops to that.) $\endgroup$ – TMM Dec 21 '18 at 18:56
  • $\begingroup$ What I mean there is that the structure of LPN does not allow for the same applications: for example, there are natural constructions of additively homomorphic encryption schemes from LWE, or of collision-resistant hash functions; both are unknown from LPN. There are countless other examples, leading to the common intuition among cryptographers that there is some fundamental difference in the structure of LPN that makes it so much harder to use (a plausible angle to explain this difference is that the "Gaussian noise over the binary field" (i.e., Bernoulli) makes a blackbox use of the field). $\endgroup$ – Geoffroy Couteau Dec 21 '18 at 19:30
  • 2
    $\begingroup$ I disagree with the last paragraph: LWE does generalize LPN to larger moduli than 2 and to a broader choice of error distributions. Said another way, instantiating LWE with q=2 and a zero-heavy error distribution (e.g., a quite narrow discrete Gaussian) yields LPN. $\endgroup$ – Chris Peikert Dec 22 '18 at 3:14

Your Answer

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

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