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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ There's the McEliece cryptosystem $\endgroup$– Command MasterCommented Jun 8, 2023 at 15:38
-
1$\begingroup$ Did you check what wikipedia writes about your question? $\endgroup$– j.p.Commented Jun 8, 2023 at 16:16
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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
- The choice of which algebraic structure to work with (unstructured, ring, some mix of the two i.e. module)
- The choice of which particular ring to work over,
- 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.
-
$\begingroup$ 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.? $\endgroup$– TurboCommented Jun 9, 2023 at 18:44
-
$\begingroup$ If noise is $\Omega(n)$ what is the typical $q$ size currently recommended? $\endgroup$– TurboCommented Jun 9, 2023 at 18:45
-
$\begingroup$ 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? $\endgroup$– TurboCommented Jun 9, 2023 at 21:19
-
$\begingroup$ 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. $\endgroup$– Mark Schultz-Wu ♦Commented Jun 10, 2023 at 21:32
-
1$\begingroup$ I am not aware of multivariate encryption schemes, only digital signatures. $\endgroup$– LeoDucasCommented Aug 14, 2023 at 4:51