# Why is the security of lattice cryptosystems not provable from $P \neq NP$?

My understanding is that the Shortest Vector Problem ($\text{SVP}$) is $\text{NP}$-hard. Therefore, $\text{LWE}$ is also $\text{NP}$-hard. But $\text{LWE}$ is hard on average if it is hard in the worst case, so breaking certain cryptosystems based on it is also $\text{NP}$-hard, which means that secure asymmetric encryption is not only possible but known, unless $\text{P} = \text{NP}$!

That would be a rather striking result, and to my knowledge it has not been clamed in a serious paper. What is the flaw in my reasoning?

• LWE is at least as hard as finding approximate solutions to SVP, but the approximation factors for which the reduction from SVP to LWE works are larger than the approximation factors for which we know NP-hardness – Sasho Nikolov Jul 23 '17 at 5:32
• As @SashoNikolov pointed out, the only flaw in you reasoning is that the LWE cryptosystems are based on approximate versions of SVP such as GapSVP. GapSVP is not known to be NP-hard, and under plausible complexity-theoretic assumptions it's not NP-hard (see an excellent survey here: web.eecs.umich.edu/~cpeikert/pubs/lattice-survey.pdf). Moreover, there are reasons to believe that even a secret key cryptography (which is not harder to construct than a public key one like LWE) cannot be based on an NP-hard problem (see,e.g., link.springer.com/chapter/10.1007/978-3-662-46494-6_1). – Alex Golovnev Jul 25 '17 at 20:49