Is there a good reason not to mention that ECC is weaker than RSA on a quantum computer?

Question

In most papers and other documents I see people are considering an ECC key of 256 bits equivalent to an RSA key of 3072 bits, which is true on a classical computer. But the amount of qubits required to crack RSA keys are estimated to be 2•bits while ECC is roughly 6•bits, which would make 256 bit ECC weaker than 1024 bit RSA.

|           RSA       |           ECC       |
| Key Length | qubits | Key Length | qubits |
|------------|--------|------------|--------|
| 1024       | 2048   | 163        | 1000   |
| 2048       | 4096   | 224        | 1300   |
| 3072       | 6144   | 256        | 1500   |
| 4096       | 8192   | 383        | 2300   |
| 15360      | 30720  | 512        | 3000   |

Source: https://security.stackexchange.com/a/96880

Is there a good reason to leave out that ECC is weaker than RSA on a quantum computer when writing a paper that involves comparing RSA to ECC? E.g. you want to promote the use of ECC over RSA.

Answer 1

I mainly see two reasons against comparing the quantum attack cost of RSA and ECC:

• If your threat model includes (large) quantum computers, you should neither promote RSA nor ECC : they both scale badly against them, and any argument about which is stronger or weaker is marginal.
• Since quantum computers large enough to be useful do not exist as of today (2017), it is to soon to compare precisely the two schemes, since the quantum computer’s architecture (as in “Von Neuman architecture”, not x86 vs PowerPC) is far from settled. Many different theoretical models exists (circuit model, measurement based quantum computers, Clifford computation with magic states, etc.), different universal sets of gates and fault-tolerant architectures are proposed, and work on quantum compilers is only starting. For a theoretician, this in “not really important because all these models are polynomially equivalent”, put this might easily reduce (or increase) the gap between ECC and RSA.

Answer 2

Yes, there is, and that is that a number of knowledgeable people think that ECC is going to be harder to solve in a quantum computer than RSA. Here's my explanation, that comes from my discussions with Tanja Lange and Dan Bernstein, who are knowledgeable in both ECC and quantum cryptanalysis:

Before I say anything more, let me state that none of us actually know what quantum computers are going to be able to do in terms of an equivalent of say, instruction count for an algorithm on a Von Neumann classical computer. This is the same point that Frédéric Grosshans made in this thread.

However, here's some mathematical basics:

• There is a mathematical parallelism between factoring and discrete logarithms. If there is a "shortcut" for one then there is a shortcut for the other. This is a proved theorem.

• ECC is discrete log crypto over a finite field that is an elliptic curve (duh) as opposed to prime-modular integers.

Thus, if someone finds a fast way to factor, then there's a fast way to solve integer discrete logs, and thus EC discrete logs.

However, there's no guarantee that things will be directly analogous in the same way.

For example, we know that factoring by Shor's algorithm takes $72k^3$ quantum gates, where $k$ is the size of the integer in bits. We thus know that there's a solution for discrete logs over any finite field, but we don't know that it's going to be $k^3$ in bit size, we only know that it's polynomial. It is entirely possible that someone could come up with some other form of discrete log that Shor's algorithm would be $k^{100}$ and if that happened, one might reasonable claim that it is "resistant" to a quantum computer, because you're not going to see one appear that can break it for engineering reasons. In fact, there's an interesting paper on how to tweak RSA so it's usable in a world with quantum computers.

The next thing to consider is that quantum computers can only do reversible computations. This is why hash-based signatures are immune to quantum computers. But it also means that when you're running a quantum algorithm, you have to write it so that your intermediate steps are reversible. You can't do something like "x = 0", you have to clear your register/qbit x by undoing the previous calculations you made in it.

And this is the key engineering question around the larger question. Yes, naively, a 256 bit ECC key that is conventionally as strong as a 3k-bit RSA key has fewer bits and therefore needs fewer q-bits to store, doing elliptic curve operations on the quantum computer needs more intermediate state, and that intermediate state means more q-bits to the point that it is likely harder to do Shor's algorithm on ECC than on equivalent state of RSA.

Of course, the proof is always in the implementation, but the present thoughts are that factoring integers requires less quantum computer state than doing ECC.