4 ms·

> It is estimated that 2048-bit RSA keys could be broken on a quantum computer comprising 4,000 qubits and 100 million gates. Experts speculate that quantum com

by mtgx 9y ago

> It is estimated that 2048-bit RSA keys could be broken on a quantum computer comprising 4,000 qubits and 100 million gates. Experts speculate that quantum computers of this size may be available within the next 20-30 years. https://www.entrust.com/wp-content/uploads/2013/05/WP_QuantumCrypto_Jan09.pdf https://www.entrust.com/wp-content/uploads/2013/05/WP_Quantu... The paper is from 2009, so ~2030 to break 2048-bit RSA seems about right. If they can double the number of qubits every two years, then we should have: 100-qubit by 2020. 200-qubit by 2022 400 qubit by 2024 800 qubit by 2026 1600 qubit by 2028 3200 qubit by 2030 6400 qubit by 2032. It's also possible the rate of progress will be slightly higher than 2x every 2 years, so doing it a few years sooner than that is not out of the question. Also, you have to consider that once you get a quantum computer that can break 2048-RSA, you'll be able to break all the encrypted communications you've stored in the past few years, too. So you can't "switch-on" the quantum-resistant crypto in 2031 and think you're all good. You have to do it as soon as possible, especially after practical quantum computers that are capable of scaling in a scheduled way start appearing (which seems to have happened). Plus, even if Google is super-quick to adopt quantum-resistant crypto, doesn't mean the rest of the internet will be, too. It could take a few more years for that to happen, too.

marcosdumay 9y ago
From the Wikipedia timeline[1], it seems to be growing linearly. 1 - https://en.wikipedia.org/wiki/Timeline_of_quantum_computing https://en.wikipedia.org/wiki/Timeline_of_quantum_computing
- nategri 9y ago
  To quote my thesis advisor's terrible joke: "Everything's linear to first order"
  - marcosdumay 9y ago
    Not too long ago I summarized every datapoint in that page. It is almost perfectly linear (there's 1 qubit lower somewhere, 1 qubit higher elsewhere), the noise is way lower than anything I was expecting to see.
gruez 9y ago
>Also, you have to consider that once you get a quantum computer that can break 2048-RSA, you'll be able to break all the encrypted communications you've stored in the past few years, too isn't that what PFS is supposed to prevent?
- mtgx 9y ago
  PFS can slow it down a bit, but not much. Assuming before PFS everyone changed their keys every 3 years, and with PFS they change them every 2 weeks, then it should be about 80x harder (slower to break the encryption). 80x harder may seem like a lot but it's not that much in the context of quantum computers. Also, PFS uses 256-bit ECC, which only requires a 512-qubit quantum computer to break it. So it's possible that a 4,000 qubit quantum computer, or even a smaller one, could break ECC with PFS even faster than it can break 2048-bit RSA.
  - jcranmer 9y ago
    > Also, PFS uses 256-bit ECC, which only requires a 512-qubit quantum computer to break it. Grover's algorithm is a quadratic, not exponential speedup. It may require 512 qubits, but it still requires 2^128 time.
    - Zaak 9y ago
      ECC is vulnerable to Shor's algorithm, which gives exponential speedup. A rough calculation implies that 256-bit ECC would take on the order of 25k quantum operations to break.
Strilanc 9y ago
You have to divide the qubit count by 100 to account for error correction.

by mtgx 9y ago

marcosdumay 9y ago

From the Wikipedia timeline[1], it seems to be growing linearly. 1 - https://en.wikipedia.org/wiki/Timeline_of_quantum_computing https://en.wikipedia.org/wiki/Timeline_of_quantum_computing

nategri 9y ago
To quote my thesis advisor's terrible joke: "Everything's linear to first order"
- marcosdumay 9y ago
  Not too long ago I summarized every datapoint in that page. It is almost perfectly linear (there's 1 qubit lower somewhere, 1 qubit higher elsewhere), the noise is way lower than anything I was expecting to see.

gruez 9y ago

>Also, you have to consider that once you get a quantum computer that can break 2048-RSA, you'll be able to break all the encrypted communications you've stored in the past few years, too isn't that what PFS is supposed to prevent?

mtgx 9y ago
PFS can slow it down a bit, but not much. Assuming before PFS everyone changed their keys every 3 years, and with PFS they change them every 2 weeks, then it should be about 80x harder (slower to break the encryption). 80x harder may seem like a lot but it's not that much in the context of quantum computers. Also, PFS uses 256-bit ECC, which only requires a 512-qubit quantum computer to break it. So it's possible that a 4,000 qubit quantum computer, or even a smaller one, could break ECC with PFS even faster than it can break 2048-bit RSA.
- jcranmer 9y ago
  > Also, PFS uses 256-bit ECC, which only requires a 512-qubit quantum computer to break it. Grover's algorithm is a quadratic, not exponential speedup. It may require 512 qubits, but it still requires 2^128 time.
  - Zaak 9y ago
    ECC is vulnerable to Shor's algorithm, which gives exponential speedup. A rough calculation implies that 256-bit ECC would take on the order of 25k quantum operations to break.

Strilanc 9y ago

You have to divide the qubit count by 100 to account for error correction.