Score:3

Crypto

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

Max Weber

12/23/23, 1:56 PM

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.

192

1 + 2

cryptanalysis

post-quantum-cryptography

lattice-crypto

lwe

Don Freecs

12/23/23, 3:33 PM

Because M-LWE is a special case of LWE, and LWE can be seen as BDD in the LWE-lattice

Max Weber

12/26/23, 9:24 PM

@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

Score:2

Crypto

Daniel S

12/23/23, 6:18 PM

The inability to show necessity in our preferred means of attacking a cryptographic system is really quite common.

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.

When attacks have been proposed against (M)LWE, the ones which require the fewest operations for parameter sets of interest they almost always involve finding short vectors in lattice as part of their approach. If anyone did propose a general method that did not involve short vectors and which used fewer operations, we would almost certainly start considering this other approach. However, similar to the cases of RSA and Diffie-Hellman, no-one has made such a general proposal and there is an unspoken belief (if not surety) that the chosen approaches are closely-tied to the decryption problems given our current state of knowledge.

+ 2

Max Weber

12/26/23, 9:33 PM

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.

Turbo

6/9/24, 9:15 PM

@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?

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.