3
$\begingroup$

As opposed to RSA or elliptic curve cryptography?

$\endgroup$
2
$\begingroup$

The attacks on RSA and Elliptic curve cryptography(ECC) are based on Shor's quantum algorithm which is used for integer factorization in the context of RSA.

Correction: Note that, as pointed out by @yyyyyyy in the comments, Shor's algorithm for DLP does not factor; neither is it based on finding the order of an element (which is usually known anyway in a DLP context). Both variants have in common that Shor finds the period lattice of a certain map, and while in the factoring context this period is indeed (the $\mathbb{Z}$-multiples of) the order of an element, the lattice is two-dimensional in the discrete-logarithm setting (and contains a vector of the form $(𝑥,−1)$ where $𝑥$ is the solution to the DLP instance).

Cyclic groups are at the heart of RSA (over integer rings) and ECC (over additive groups defined on an elliptic curve over finite fields), thus the vulnerability.

However, lattice based crypto does not rely on such structures. Neither do code-based cryptosystems (McEliece, for example) so they are resistant to known quantum attacks.

$\endgroup$
  • 2
    $\begingroup$ Shor's algorithm for DLP does not factor; neither is it based on finding the order of an element (which is usually known anyway in a DLP context). Both variants have in common that Shor finds the period lattice of a certain map, and while in the factoring context this period is indeed (the $\mathbb Z$-multiples of) the order of an element, the lattice is two-dimensional in the discrete-logarithm setting (and contains a vector of the form $(x,-1)$ where $x$ is the solution to the DLP instance). $\endgroup$ – yyyyyyy Jun 7 at 0:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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