# Why is the best way to solve LWE (and Cryptographic related Systems) with SVP (approx)?

Community,

I'm new into lattice based cryptography, and I'm interested about the security of cryptography schemata like Kyber and why the focus of solving this problem lead into solving approx. SVP.

If you're looking into breaking Cryptography schemas like Kyber you find statements like:

“The best known attacks against the underlying MLWE problem in Kyber do not make use of the structure in the lattice. We therefore analyze the hardness of the MLWE problem as an LWE problem" and "Many algorithms exist for solving LWE ... but many of those are irrelevant for our parameter set" This essentially leaves us with two BKZ attacks ... The algorithm BKZ proceeds by reducing a lattice basis using an SVP oracle in a smaller dimension b. https://pq-crystals.org/kyber/data

So the best algorithm for solving LWE (with low samples) is the usage of approx. SVP solver ?

My Question is why ?

What I know is that there exist some reduction between LWE and (some) Lattice Problems like BDB and SIS, and also Gap SVP. Here you see a Picture of reductions between Lattice Problems. Found in "Solving Hard Lattice Problems and the Security of Lattice-Based Cryptosystems" from Thijs Laarhoven Sure, we have a reduction between LWE and GapSVP (and also Approx. SVP with this statement) and several other Lattice Problems (example BDD) but this gives me (in my POV) not much security because someone could find a polynomial solver for LWE and could still not solve the exact SVP or CVP (which seems pretty unsolvable because of the NP-Statements). You see the figure below about the approx. factor and hardness Statements found in “The Complexity of the Shortest Vector Problem” from Huck Bennett. In my way I see the thing it would be good to find a polynomial “shorter” for Gap SVP. If someone could find a polynomial efficient Algorithm of LWE he could use this “shorter” to solve NP-Hard GapSVP in polynomial time which provoke an unbelievable statement and thus guaranty the safety about LWE and the related cryptosystem. For example, we say we could "short" the GapSVP from $$n -> n^{1/log(n)log(n)}$$ in polynomial time.

But I don't know such a Theorem, and it seems not there exist such a statement because it would suggest LWE could be NP-Hard, which we know isn't reachable. Thus left us with a Statement that LWE could be easy to solve (in my POV) and short the distance between two Gap SVP could be still hard.

What makes SVP-solver so attractive into solving LWE and not other attacks ?. What is the exact connection between the different Lattice-Problems (beside the reductions) ?

Maybe I understand many statements about lattice problems incorrectly. I am grateful in advance for help so that I understand it better.

• Because M-LWE is a special case of LWE, and LWE can be seen as BDD in the LWE-lattice Dec 23, 2022 at 15:33
• @DonFreecs Thank you for your good answer. BDD is a hard problem, but it doesn't show me how it forces using Approx. SVP to solve the Problem Dec 26, 2022 at 21:24

Historically, our preferred method of breaking RSA when assessing security has been to factor the public modulus, but no-one has yet shown that breaking the RSA cryptosystem (which requires the extraction of $$e$$th roots modulo $$N$$) provides a means to solve the factoring problem. Similarly in Diffie-Hellman systems we assess security by assessing the difficulty of solving a discrete logarithm, but no-one has yet shown that breaking solving the Diffie-Hellman problem can enable us to recover discrete logarithms. For other PQA examples, the assessed security of Classic McEliece is based on the difficulty of decoding an unstructured linear code.
• Thank you for your good and far reaching explanation. That means that at the moment we just assume that the Approximate SVP are the best approaches ? There could also be theoretically e.g. a algebraic solution to break the LWE ? Can we at least say that the exact solution to the SVP (NP-Hard) loses considerable strength ? So e.g. we find a $Sqrt(n)$ solution to the Approx. SVP problem by our LWE reduction and because the exact solution is not far away (roughly speaking) to the exact SVP it would be a surprise to find such a solution and thus LWE is safe in a way. Dec 26, 2022 at 21:33
• @DanielS Similar question to above. If we break LWE then we can approximate SVP to $O(n^{3/2})$ factor by Regev's quantum reduction. Conversely to break LWE what approximate SVP do we need? Is it $o(n^{3/2})$ or just $\Omega(n^{3/2})$ factor approximation SVP suffices? Jun 9 at 21:15