7
$\begingroup$

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?

$\endgroup$
  • 9
    $\begingroup$ 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 $\endgroup$ – Sasho Nikolov Jul 23 '17 at 5:32
  • 3
    $\begingroup$ 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). $\endgroup$ – Alex Golovnev Jul 25 '17 at 20:49
6
$\begingroup$

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

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/

| cite | improve this answer | |
$\endgroup$

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.