What if LWE is not as secure as we think?

ru flag

LWE schemes are currently being deployed. LWE has no quantum polynomial time algorithms as far as we know.

Despite this what is the consequence if LWE can be broken on a classical computer? Do we have any other alternatives?

Command Master avatar
in flag
There's the McEliece cryptosystem
cn flag
Did you check what [wikipedia]( writes about your question?
ng flag

There are some alternatives. Mainly they fall into the categories of

  • Coding-based crypto (LPN type things, McCliece, and rank metric codes)
  • Isogeny-based crypto (though this has suffered devastating classical attacks. I'm the wrong person to summarize the current state of affairs)

Additionally, for digital signatures, one can use (typically stateful) hash-based signatures, or signatures based on multi-variate quadartic systems of equations.

Of course, these things are not all independent. It is plausible that if LWE is attacked it will yield better attacks against LPN type things (the problems are similar, but "with respect to a different metric"). It is also worth mentioning there is many ways that "LWE is broken by a classical computer" could manifest. When designing an LWE-based cryptosystem, there are a few things that matter

  1. The choice of which algebraic structure to work with (unstructured, ring, some mix of the two i.e. module)
  2. The choice of which particular ring to work over,
  3. The size of the modulus to noise paramter $q/\sigma$ (and generally Gaussian paramter $\sigma$).

It is possible that the most aggressive assumptions, i.e. Ring LWE with small Gaussian noise $\sigma = \Theta(1)$, is broken while other LWE-based cryptosystems (plain LWE with Gaussian noise $\Omega(\sqrt{n})$) is fine. So far the best attacks are roughly independent of these underlying choices, but there is no reason to think this should be true a priori. Moreover, the theoretical results we can prove regarding these problems hardness do depend pretty strongly on the above choices of "parameters", so it would make sense if the reason why this is the case is because the problems have fundamentally different difficulties.

Turbo avatar
ru flag
to me 3. seems to be a significant thing. The larger it is, it appears it might be weaker. I agree I like code based crypto better despite larger key sizes (1megabyte in a world of 5G or 6G is nothing). (A.) Is there any literature on attacks based on 3.? (B.) Any literature on theoretical guarantees based on 3.?
Turbo avatar
ru flag
If noise is $\Omega(n)$ what is the typical $q$ size currently recommended?
Turbo avatar
ru flag
one last question. 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 algorithm do we need? Is it $o(n^{3/2})$ or just $\Omega(n^{3/2})$ factor approximation SVP algorithm suffices?
Mark avatar
ng flag
Larger key sizes are not nothing. We would have to significantly rearchitect essentially the entire internet to store keys long-term to deal with the blowup in traffic. There is a reason that McCliece did not do particular well in the NIST competition.
Turbo avatar
ru flag
still code based cryptography is the 4th round. Plus Europeans want a code based one.
I sit in a Tesla and translated this thread with Ai:


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.