6
$\begingroup$

We know that both the RSA and ECC algorithms are vulnerable against attacks using (future) Quantum Computing (QC). Are there however any advantages of choosing one algorithm over the other?

As an example: would it be possible that the larger key size of RSA has advantages over the short key size used by ECC, possibly with regards to the amount of qbits or qbit configuration required? Would such an advantage matter in practice?

$\endgroup$
4
  • $\begingroup$ The any answer should not only be a technical equation. Crystal balls can be rented at low cost from the asker. $\endgroup$
    – Maarten Bodewes
    Oct 18, 2016 at 8:38
  • 1
    $\begingroup$ Perhaps yes; see this answer and section 5.4 of its Koblitz & Menezes source. $\endgroup$
    – fgrieu
    Oct 18, 2016 at 8:46
  • 2
    $\begingroup$ @fgrieu That section 5.4 comes dangerously close to an answer - it's a shame that that part of the article doesn't refer to any papers on the subject. On the other hand Koblitz and Menezes themselves are of course credible sources. Some more insight in the required size of the QC would be nice though. $\endgroup$
    – Maarten Bodewes
    Oct 18, 2016 at 8:56
  • 1
    $\begingroup$ Note that Koblitz and Menezes are not making any strong statement; their 5.4 is in the context (page 12): "We next examine some conjectures about the NSA’s motives in its PQC announcement." (emphasis mine). $\endgroup$
    – fgrieu
    Oct 18, 2016 at 9:07

1 Answer 1

7
$\begingroup$

This is by no means a comprehensive answer on this subject, but perhaps it's a good start.

Shor's algorithm for (specific) ECC

This paper by Proos and Zalka compares implementations of Shor's algorithm for integer factorization and discrete logarithms for some elliptic curve groups (notably, ONLY those over prime finite fields).

If $n$ is the bit length of the group (from section 6.3):

RSA                      | ECC
-----+--------+----------+-----+--------+---------
n    | qubits | time     | n   | qubits | time
-----+--------+----------+-----+--------+---------
1024 |   2048 | 4.3*10^9 | 163 |   1000 | 1.6*10^9
2048 |   4098 |  34*10^9 | 224 |   1300 |   4*10^9
3072 |   6144 | 120*10^9 | 256 |   1500 |   6*10^9

RSA needs about $2n$ qubits, while ECC needs approximately $6n$ (for smaller $n$). Similarly, RSA needs ~$4n^3$ gates, while ECC only requires ~$360n^3$.

ECC is classically more difficult than RSA, allowing for smaller key sizes and more efficient computation. Quantumly, ECC is still more difficult than RSA, but less so, leading to what the authors call a "quantum advantage" for elliptic curve discrete logarithms over integer factorization.

Comparing RSA-3072 to ECC-256, they found that a quantum computer needs to be approximately $4\times$ as big and takes approximately $20\times$ as much time to crack RSA as compared to ECC.

Keep in mind that this work is from 2008 and is only relevant for curves over prime fields.

In practice

Obviously a factor of 4 in the number of qubits is not "much more quantum-resistant" as per the link given by fgrieu. It's very possible that ECC over GF($2^m$) is much more efficiently broken by quantum computing.

Due to the similarities of the two problems, I can't imagine that qubit configuration would have much of an impact in one direction or the other.

However, this is all conjecture on my part.

It is not likely that the gap between quantum cryptanalysis of a 384-bit key and a 3072-bit key will be great enough to serve as a basis for a cryptographic strategy.

In any case, I interpret the above quote from as there being no practical difference between the two. Both should be considered utterly broken at that time.

$\endgroup$

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.