Skip to main content
added 39 characters in body
Source Link

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)
  • Multivariate cryptography.

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 resultschoices of "parameters", so it would make sense if the reason why this is the case is because the problems have fundamentally different difficulties.

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)
  • Multivariate cryptography.

Additionally, for digital signatures, one can use (typically stateful) hash-based signatures.

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 results, so it would make sense if the reason why this is the case is because the problems have fundamentally different difficulties.

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.

Source Link

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)
  • Multivariate cryptography.

Additionally, for digital signatures, one can use (typically stateful) hash-based signatures.

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 results, so it would make sense if the reason why this is the case is because the problems have fundamentally different difficulties.