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
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!)