<p>The LPN problem is indeed believed to be hard, but like most problems we believe are hard, the main reason for it is that many smart people have tried to find an efficient algorithm and failed.</p>

<p>The best "evidence" for LPN's hardness comes from the high statistical query dimension of the parity problem.  Statistical queries capture most known learning algorithms, except for gaussian elimination (which fails whenever noise is introduced), hashing, and techniques similar to these two.  It is hard to design non statistical-query algorithms, and this is the main bottleneck.  Other evidence of LPN's hardness is its relationship to other hard problems (like LWE, SVP as you've pointed out).</p>

<p>For the SQ-hardness, here is the <a href="http://www.cis.upenn.edu/~mkearns/papers/sq-journal.pdf" rel="nofollow">link</a> to Kearns's ('98) paper. </p>

<p>For progress on the upper bounds on this problem, there are several results:</p>

<ul>
<li>Probably the most famous is the Blum-Kalai-Wasserman ('00) result which beats the $2^N$ SQ barrier by a little, giving an algorithm that runs in time $2^{n / \log n}$. (<a href="http://www.google.com/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=3&amp;ved=0CE0QFjAC&amp;url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.1696&amp;rep=rep1&amp;type=pdf&amp;ei=LC6-UOLZHqik2gXMtoHACQ&amp;usg=AFQjCNFvv5tEgKSHF7UrwmvHlW-DiPCvYA&amp;sig2=U3Qh04GHuPGBFHhnDMqm2g" rel="nofollow">link</a>)</li>
<li>Lyubashevsky ('05) found an algorithm with worse running time $O(2^{n / \log\log n})$ but better sample complexity of $O(n^{1 + \epsilon})$. (<a href="http://www.di.ens.fr/~lyubash/papers/parityproblem.pdf" rel="nofollow">link</a>)</li>
<li>In the sparse case, where we know the parity is on $k$ variables, Grigorescu-Reyzin-Vempala ('11) gave a $\approx O(n^{0.5 k})$ algorithm, beating the $O(n^k)$ brute-force.  However, this bound decays toward $O(n^k)$ as the noise rate $\eta$ approaches $1/2$. (<a href="http://www.levreyzin.com/papers/GrigorescuRV11.pdf" rel="nofollow">link</a>)</li>
<li>Valiant ('12) recently gave a $\approx O(n^{0.8 k})$ algorithm for the sparse case.  This bound is stronger because it does not decay in the exponent with the noise rate (unlike the GRV result). (<a href="http://www.cs.berkeley.edu/~gvaliant/papers/corrFOCS.pdf" rel="nofollow">link</a>)</li>
</ul>

CC BY-SA 3.0
2012-12-04T17:22:44.063Z
This is a very nice answer; thanks! I'll let the bounty float for bit (in case someone manages to dredge up some odd-ball lower bound), but this appears to be complete from my point of view.
Daniel Apon
CC BY-SA 4.0
2023-06-07T21:37:35.180Z
@LevReyzin In LWE type schemes if we know shortest vector or the secret to the trapdoor we can recover the message. 1) If we know shortest vector, can we recover the secret to the trapdoor? 2) If we know the secret to the trapdoor, can we recover the shortest vector?
Turbo
CC BY-SA 3.0
2012-12-04T17:14:37.953Z
2012-12-04T19:39:21.483Z
2012-12-04T19:39:21.483Z
Lev Reyzin
<p><strong>Some background:</strong></p>

<p>I'm interested in finding "lesser-known" lower bounds (or hardness results) for the Learning with Errors (LWE) problem, and generalizations thereof like Learning with Errors over Rings. For specific definitions, etc., here is a nice survey by Regev: <a href="http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf">http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf</a></p>

<p>The standard type of (R)LWE-style assumption is via (perhaps, quantum) reduction to the Shortest Vector Problem on (perhaps, ideal) lattices. The usual formulation of SVP is known to be NP-hard, and it's BELIEVED to be hard to approximate to small polynomial factors. (Related: It's hard to approximate CVP to within /almost-polynomial/ factors: <a href="http://dl.acm.org/citation.cfm?id=1005180.1005182">http://dl.acm.org/citation.cfm?id=1005180.1005182</a> ) I've also heard it mentioned that (in terms of quantum algorithms) approximating certain lattice problems (like SVP) to small polynomial approximation factors is related to the non-Abelian hidden subgroup problem (which is believed to be hard for its own reasons), though I've never seen an explicit, formal source for this.</p>

<p>I'm more interested, however, in hardness results (of any type) that come as a result of the Noisy Parity problem from Learning Theory. These could be <em>complexity class hardness results, concrete algorithmic lower bounds, sample complexity bounds, or even proof size lower bounds</em> (e.g. Resolution). It is known (perhaps, obvious) that LWE can be viewed as a generalization of the Noisy Parity/Learning Parity with Noise (LPN) problem, which (from Googling) appears to have been used in hardness reductions in areas like coding theory and PAC learning.</p>

<p>From looking around myself, I've only found (mildly subexponential) UPPER BOUNDS on the LPN problem, e.g. <a href="http://www.di.ens.fr/~lyubash/papers/parityproblem.pdf">http://www.di.ens.fr/~lyubash/papers/parityproblem.pdf</a></p>

<p><strong>Question:</strong></p>

<p>I know LPN is BELIEVED HARD in the learning community. My question is: <strong>Why?</strong></p>

<p>Is it because everyone tried really hard, but no one's found a good algorithm yet? Are there known lower bounds of the <em>italicized variety above</em> (or others I left out)?</p>

<p>If the answer is very clear-cut, a succinct summary of what's known and/or references to surveys/lecture notes would be great.</p>

<p>If much is unknown, the more "state-of-the-art" papers, the better. :) (Thanks ahead of time!)</p>

<cc.complexity-theory><reference-request><cr.crypto-security><machine-learning><lg.learning>
Noisy Parity (LWE) lower bounds/hardness results
Daniel Apon
# Noisy Parity (LWE) lower bounds/hardness results

(Asked by: username_0 on 2012-12-02)

**Some background:**

I'm interested in finding "lesser-known" lower bounds (or hardness results) for the Learning with Errors (LWE) problem, and generalizations thereof like Learning with Errors over Rings. For specific definitions, etc., here is a nice survey by Regev: <http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf>

The standard type of (R)LWE-style assumption is via (perhaps, quantum) reduction to the Shortest Vector Problem on (perhaps, ideal) lattices. The usual formulation of SVP is known to be NP-hard, and it's BELIEVED to be hard to approximate to small polynomial factors. (Related: It's hard to approximate CVP to within /almost-polynomial/ factors: <http://dl.acm.org/citation.cfm?id=1005180.1005182> ) I've also heard it mentioned that (in terms of quantum algorithms) approximating certain lattice problems (like SVP) to small polynomial approximation factors is related to the non-Abelian hidden subgroup problem (which is believed to be hard for its own reasons), though I've never seen an explicit, formal source for this.

I'm more interested, however, in hardness results (of any type) that come as a result of the Noisy Parity problem from Learning Theory. These could be *complexity class hardness results, concrete algorithmic lower bounds, sample complexity bounds, or even proof size lower bounds* (e.g. Resolution). It is known (perhaps, obvious) that LWE can be viewed as a generalization of the Noisy Parity/Learning Parity with Noise (LPN) problem, which (from Googling) appears to have been used in hardness reductions in areas like coding theory and PAC learning.

From looking around myself, I've only found (mildly subexponential) UPPER BOUNDS on the LPN problem, e.g. <http://www.di.ens.fr/~lyubash/papers/parityproblem.pdf>

**Question:**

I know LPN is BELIEVED HARD in the learning community. My question is: **Why?**

Is it because everyone tried really hard, but no one's found a good algorithm yet? Are there known lower bounds of the *italicized variety above* (or others I left out)?

If the answer is very clear-cut, a succinct summary of what's known and/or references to surveys/lecture notes would be great.

If much is unknown, the more "state-of-the-art" papers, the better. :) (Thanks ahead of time!)

**Tags:** cc.complexity-theory, reference-request, cr.crypto-security, machine-learning, lg.learning


---

## 1 answers

### Answer by username_1 on 2012-12-04. Score: 7 | Accepted answer

The LPN problem is indeed believed to be hard, but like most problems we believe are hard, the main reason for it is that many smart people have tried to find an efficient algorithm and failed.

The best "evidence" for LPN's hardness comes from the high statistical query dimension of the parity problem. Statistical queries capture most known learning algorithms, except for gaussian elimination (which fails whenever noise is introduced), hashing, and techniques similar to these two. It is hard to design non statistical-query algorithms, and this is the main bottleneck. Other evidence of LPN's hardness is its relationship to other hard problems (like LWE, SVP as you've pointed out).

For the SQ-hardness, here is the [link](http://www.cis.upenn.edu/~mkearns/papers/sq-journal.pdf) to Kearns's ('98) paper.

For progress on the upper bounds on this problem, there are several results:

* Probably the most famous is the Blum-Kalai-Wasserman ('00) result which beats the $2^N$ SQ barrier by a little, giving an algorithm that runs in time $2^{n / \log n}$. ([link](http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&ved=0CE0QFjAC&url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.1696&rep=rep1&type=pdf&ei=LC6-UOLZHqik2gXMtoHACQ&usg=AFQjCNFvv5tEgKSHF7UrwmvHlW-DiPCvYA&sig2=U3Qh04GHuPGBFHhnDMqm2g))
* Lyubashevsky ('05) found an algorithm with worse running time $O(2^{n / \log\log n})$ but better sample complexity of $O(n^{1 + \epsilon})$. ([link](http://www.di.ens.fr/~lyubash/papers/parityproblem.pdf))
* In the sparse case, where we know the parity is on $k$ variables, Grigorescu-Reyzin-Vempala ('11) gave a $\approx O(n^{0.5 k})$ algorithm, beating the $O(n^k)$ brute-force. However, this bound decays toward $O(n^k)$ as the noise rate $\eta$ approaches $1/2$. ([link](http://www.levreyzin.com/papers/GrigorescuRV11.pdf))
* Valiant ('12) recently gave a $\approx O(n^{0.8 k})$ algorithm for the sparse case. This bound is stronger because it does not decay in the exponent with the noise rate (unlike the GRV result). ([link](http://www.cs.berkeley.edu/~gvaliant/papers/corrFOCS.pdf))

> **Comments:**
> **username_0**: This is a very nice answer; thanks! I'll let the bounty float for bit (in case someone manages to dredge up some odd-ball lower bound), but this appears to be complete from my point of view.  
> **username_2**: @LevReyzin In LWE type schemes if we know shortest vector or the secret to the trapdoor we can recover the message. 1) If we know shortest vector, can we recover the secret to the trapdoor? 2) If we know the secret to the trapdoor, can we recover the shortest vector?  

---

