<p>To expand somewhat on Sasho Nikolov's comment...</p>

<blockquote>
  <p>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</p>
</blockquote>

<p>...the following is a reasonably complete view of things:</p>

<p><a href="https://i.sstatic.net/T3RHJ.png" rel="noreferrer"><img src="https://i.sstatic.net/T3RHJ.png" alt="Summary of Known Results"></a></p>

<p>This was part of Oded Regev's talk at the Winter School on Lattice-Based Cryptography and Applications, held at Bar-Ilan University, Israel, in 2012.</p>

<p>If you are interested in a good introduction to the very basics of lattice cryptography, I'd happily recommend checking out the full record of this winter school. You can (still-- as of Summer 2017) find a large list of slides and talk videos at:</p>

<p><a href="https://cyber.biu.ac.il/event/the-2nd-biu-winter-school/" rel="noreferrer">https://cyber.biu.ac.il/event/the-2nd-biu-winter-school/</a></p>

CC BY-SA 3.0
2017-07-27T19:32:18.753Z
2017-07-27T19:32:18.753Z
Daniel Apon
<p>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 <em>also</em> $\text{NP}$-hard, which means that secure asymmetric encryption is not only possible but known, unless $\text{P} = \text{NP}$!</p>

<p>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? </p>

CC BY-SA 3.0
2017-07-23T05:32:17.043Z
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
CC BY-SA 3.0
2017-07-25T20:49:26.783Z
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: https://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., https://link.springer.com/chapter/10.1007/978-3-662-46494-6_1).
Alex Golovnev
<cc.complexity-theory><cr.crypto-security>
Why is the security of lattice cryptosystems not provable from $P \neq NP$?
Demi
# Why is the security of lattice cryptosystems not provable from $P \neq NP$?

(Asked by: username_0 on 2017-07-23)

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?

**Tags:** cc.complexity-theory, cr.crypto-security
> **Comments:**
> **username_1**: 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  
> **username_2**: 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: https://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., https://link.springer.com/chapter/10.1007/978-3-662-46494-6_1).  

---

## 1 answers

### Answer by username_3 on 2017-07-27. Score: 7 | Accepted answer

To expand somewhat on Sasho Nikolov's comment...

> 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

...the following is a reasonably complete view of things:

[![Summary of Known Results](https://i.sstatic.net/T3RHJ.png)](https://i.sstatic.net/T3RHJ.png)

This was part of Oded Regev's talk at the Winter School on Lattice-Based Cryptography and Applications, held at Bar-Ilan University, Israel, in 2012.

If you are interested in a good introduction to the very basics of lattice cryptography, I'd happily recommend checking out the full record of this winter school. You can (still-- as of Summer 2017) find a large list of slides and talk videos at:

<https://cyber.biu.ac.il/event/the-2nd-biu-winter-school/>


---

