3
$\begingroup$

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

enter image description here

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.

enter image description here

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.

$\endgroup$
2
  • 1
    $\begingroup$ Because M-LWE is a special case of LWE, and LWE can be seen as BDD in the LWE-lattice $\endgroup$
    – Don Freecs
    Dec 23, 2022 at 15:33
  • $\begingroup$ @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 $\endgroup$
    – Max Weber
    Dec 26, 2022 at 21:24

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Max Weber
    Dec 26, 2022 at 21:33
  • $\begingroup$ @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? $\endgroup$
    – Turbo
    Jun 9, 2023 at 21:15
  • $\begingroup$ Just a quick addition: The reduction by Maurer and Wolf shows that one can recover discrete logarithms when being able to solve the computational Diffie-Hellman problem, but it requires auxiliary information. $\endgroup$
    – CRTified
    Mar 25 at 20:40
  • $\begingroup$ @CRTified IIRC the Maurer-Wolf depends knowing the parameters of an elliptic curve mod $q$ with very smooth order. Beyond the question of whether such a curve can be identified and provided as auxiliary information, it is not clear that it exists. $\endgroup$
    – Daniel S
    Mar 26 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.