7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ it's 3661 qubits for 1024 bit rsa. the ecc numbers are off as well. unless something has changed significantly in the past year since I looked at the data $\endgroup$ – b degnan May 27 '17 at 22:10
  • 3
    $\begingroup$ Quantum computers don't exist $\endgroup$ – fkraiem May 28 '17 at 6:25
  • 1
    $\begingroup$ @bdegnan It's from page 26 of this paper $\endgroup$ – indolas May 28 '17 at 10:48
  • 1
    $\begingroup$ @fkraiem Large quantum computers that can run Shor's algorithm don't exist. They factored the number 21 with 10 qubits using Shor's algorithm 2012 and the the number 56153 with an adiabtic quantum computer in 2012. $\endgroup$ – indolas May 28 '17 at 10:48
  • 1
    $\begingroup$ You cannot compare the universal quantumcomputer of IBM with the adiabatic one of D-Wave. The D-Wave one is totally useless for exponential speed-up for solving RSA or DL problems.. $\endgroup$ – user27950 May 31 '17 at 2:36
7
$\begingroup$

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.
$\endgroup$
  • 1
    $\begingroup$ Also, if you did compare them, how would you do that? Compare at equal key size? Compare at equal performance? Comparisons at equal classical strength make little sense. $\endgroup$ – otus May 29 '17 at 14:04
4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ '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.'; actually,that's not correct; it's easy to embed a (fixed input sized) hash function within larger invertible function, and so Grover's algorithm works. The reason that HBS appear to be quantum resistant is that Grover's is the best known attack against believed strong hashes (SHA-2, SHA-3), and we can scale these hashes enough to make Grover's infeasible. $\endgroup$ – poncho May 31 '17 at 1:28
  • 2
    $\begingroup$ Also, your mathematical basics are questionable at best. It's known that if you can solve DLog problems modulo a composite, you can factor that composite. There's nothing proven about any equivalence between factoring and DLog modulo a prime; and certainly not between factoring and the ECDLog problem... $\endgroup$ – poncho May 31 '17 at 4:21
  • 1
    $\begingroup$ Your answer seems to claim that detailed quantum cryptanalysis of ECC has not been conducted, beyond “It‘s a kind of discrete log, therefore Shor’s algorithm gives a polynomial attack”, and that such attack could use $k^{100}$ quantum gates. But such analysis has been published as far back as 2003 (arxiv:quant-ph/0301141), which, I guess, is the ultimate source of the OP’s question. $\endgroup$ – Frédéric Grosshans Jun 1 '17 at 10:20
  • $\begingroup$ And the discussion about reversibility is a total red-herring. Otherwise, attacks against CBC-MAC like the one described in arXiv:1602.05973 would be impossible $\endgroup$ – Frédéric Grosshans Jun 1 '17 at 10:35

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.