8 ms·

Breaking 256-Bit Elliptic Curve Encryption with a Quantum Computer

117 points by Sami_Lehtinen 5y ago

the_black_hand 5y ago
"No time soon". I'd be careful. I remember when Bill Gates said we would never need more than 128Kb memory. Crypto is giving huge incentive to speed up the development of quantum. We could get to 1 million qbits faster than many think.
- lrem 5y ago
  Do you think any of the large players will get into crypto? Or, any of the crypto players will build a business steady enough, to try developing something so ambitious?
  - bo1024 5y ago
    Another question is exactly how far ahead the NSA is. Remember their budget was estimated at $10 billion back in 2013, more than facebook’s revenue at that time, twice what Twitter’s is today. So picture two companies the size of Twitter working largely on breaking encryption.
    - er4hn 5y ago
      An indicator of that may be the fact that the NSA is in the process of finalizing their selection of quantum resistant algorithms. After that expect those algorithms to end up in the FIPS 140 certification process and percolating into requirements for government agencies to use. The NSA has an interest in making sure that classified information stays that way for as long as the classification lasts. That is at least 25 years, potentially up to 75 years (src: https://en.wikipedia.org/wiki/Classified_information_in_the_United_States#Automatic_declassification https://en.wikipedia.org/wiki/Classified_information_in_the_...) so one could infer that the NSA believes there is a reasonable chance quantum computers will exist and be able to break classical encryption within that timeframe.
SimonTTTT 5y ago
[dead]
- jmnicolas 5y ago
  > The popular press are sucked into the idea that the technology is more capable than it is, the community can't shout the boosters down because it's all about perception. Reminds me of AI...
throawaybong 5y ago
> it would require 13 × 10^6 physical qubits It's 13 million qubits. It's weird they write it in scientific notation, it makes it look larger. If qubits got to the moore-like-bandwagon, that is not many multiplications away from current amount.
- dekhn 5y ago
  scientific notation would look more like "1.3 x 10*5" (only one leading digit: https://en.wikipedia.org/wiki/Scientific_notation#Normalized_notation https://en.wikipedia.org/wiki/Scientific_notation#Normalized...)
  - VikingCoder 5y ago
    Don't you mean 1.3 x 10 ^ 7?
    - dekhn 5y ago
      Probably :)
  - black6 5y ago
    Yes. It looks more like engineering notation (up to three digits to the left of the decimal and the power of 10 divisible by 3).
- zinekeller 5y ago
  Well, except that the approximate time for an additional "stable" qubit is currently plateauing, so outside a very lucky breakthrough, it's still unlikely. The official record for an actual running Shor's algorithm is 21 (not bits, just the number 21), which is still puny (there was an attempt to factor out 35 (again 35 as in 5×7), but it ended in failure due to quantum noise).
  - mburee 5y ago
    But Shor's algorithm is for prime factorization, right? Are there equally faster algorithms available for elliptic curves?
dijit 5y ago
It's only 1 paragraph but to save someone the click: it's not happening soon.
- sliken 5y ago
  Indeed, in fact I'd consider that an understatement of the situation.
- JulianMorrison 5y ago
  Another way of putting it would be "pretty simple and quick - if you can achieve a completely infeasible number of qubits". That is to say, it's an algorithmic overhang, the knowledge how is available but held back by not knowing how to achieve the hardware needed. The risk being that someone could discover "how to make qubits" tomorrow, and although (because it's hardware) it might take a short while to turn that into an industrial qubit pipeline, we don't yet actually know yet that it's mechanically impossible to do.
- charlieyu1 5y ago
  It will probably be earlier than fully crack SHA1 (aka finding the preimage). And SHA1 is already considered a problem for at least a decade. If post-quantum cryptography algorithms are already there, I can see EC being abondoned soon
rmbyrro 5y ago
I wouldn't be so certain it's not happening "anytime soon". They speculated about one way to break it. There could be several ways of using QC to break EC. What is the chance that at least one of those other ways require, say only 1,000 qubits? Oops, it's a two year time frame now. It might be a small chance, but I don't think we can discard it. Better plan for the worse.
- dane-pgp 5y ago
  It would be nice to have a probability distribution over how quickly quantum computers could reach the necessary level, using this paper as just one datapoint and looking at other examples of cryptographic breakthroughs and technological capability curves. By combining such a probability distribution with an estimate of how much damage could be done (or how much profit could be generated) by an enemy breaking elliptic curve encryption, it would then be possible to give a reasoned guess for how much to spend on bringing forward quantum-resistant cryptography.
- upofadown 5y ago
  >What is the chance that at least one of those other ways require, say only 1,000 qubits? A thousand physical qubits with current error rates? Pretty much impossible would be my guess.
deleted 5y ago
[deleted]
tromp 5y ago
The paper he discusses claims that Bitcoin private keys are only vulnerable for about 10 minutes, but that only applies to P2PKH (pay to public key hash) with never before used keys. However, millions of BTC are vulnerable with no quantum computation time limits. This includes about 1.75 M BTC in P2PK/raw multisig outputs, and over 4M BTC due to known pubkeys and scripts, revealed in the Bitcoin blockchain.
- shiado 5y ago
  The 10 minutes also isn't accurate because the ability to obtain private keys from public keys would completely destroy the incentives of the Bitcoin network. Miners are incentivized and compensated for including transactions in a block due to fees. The ability to steal the coins from an incoming transaction would create incentives not to include transactions in a block and to instead spam the network with as many malicious nodes as possible to halt the proliferation of transactions.
hangonhn 5y ago
Does anyone know of a similar sort of estimates for AES? Do we know if Grover's algorithms can or cannot be applied to AES? Thanks.
- ahelwer 5y ago
  It can but you only get a sqrt(n) speedup. Which is the same as halving the bits in the search space. Not trivial, but probably doesn't move it to tractable territory given appropriate key sizes.
sgdjgkeirj 5y ago
This is not as comfortable a margin as it seems. If a direct implementation of the algorithm takes a few million qubits, it may well be that both better algorithms, better error correcting codes, and optimizing their combination to the hardware platform will shave a few orders of magnitude. So in 5 years to a decade this could get uncomfortably close to the danger zone. Main issue is that in cryptography (1) some secrets encrypted now will be secret in a decade (2) changing standard is very hard and takes a long time
c1ccccc1 5y ago
Wow, this does not look like an exponentially large number of qubits. I thought elliptic curve cryptography was supposed to be secure against quantum computers, but this makes it seem like cracking is still polynomial, just with a larger constant in front than RSA has. Are there any public key techniques that are actually secure against quantum computers? (meaning they would take exponential time to break using the best known algorithms)
- hatsunearu 5y ago
  ECC is more vulnerable to quantum computing than RSA is. That's the stated reason why the NSA wants the world to move away from ECC to "post quantum cryptography".
  - c1ccccc1 5y ago
    Thanks for the correction, seems I was confused. And thanks for the pointer to post-quantum cryptography, widipedia has a nice list of algorithms.
IndrekR 5y ago
Given that quantum computers double in size in time it takes to complete one PhD thesis, it is not too far fetched to reach such capacity within a reasonable time. So far this "law" has held.
- sp332 5y ago
  Well, what's the biggest one you've seen run Shor's algorithm?
- jmnicolas 5y ago
  They double in size but do they double in performances?
sweis 5y ago
I think we are many, many years away from a quantum computer being able to break 256-bit ECC: https://sam-jaques.appspot.com/quantum_landscape https://sam-jaques.appspot.com/quantum_landscape https://www.bsi.bund.de/EN/Topics/Cryptography/QuantumComputing/quantum_computing_node.html https://www.bsi.bund.de/EN/Topics/Cryptography/QuantumComput... The current record in factoring with Shor's algorithm is 21. Yes. 3*7. That record has stood for 12 years and arguably is not even running Shor's because it required a priori knowledge of the factors. Even with "cheating" by using knowledge of the factors, in 20 years we have seen seen a single bit of improvement. None of the new quantum computers from IonQ, Google, or QuEra with 32-256 qubits are even able to even replicate those early results. D-Wave claims 5000 qubits, but that is for adiabatic QC, which to my knowledge, cannot run Shor's algorithm. To be a threat, QCs need millions of qubits and orders of magnitude better error correction. I think people make the mistake of looking at the speed of progress of classical computers and thinking it applies to QC. It's just not happening.
- acchow 5y ago
  Classical silicon chips got to exponential growth because chips were profitable - the profits could be poured back into R&D enabling a natural feedback loop. Profitability wasn't terribly difficult because computers were VERY fast at calculations compared to the next best thing - humans. For QC to hit natural exponential growth, it would need to be economically feasible compared to the next best thing - classical computers. Is there anything even a tiny QC can do better, faster, and cheaper than a classical computer?
  - javajosh 5y ago
    The most sensational, and arguably most valuable, use is breaking hard encryption, so QC has "nation state STEM/security funding" written all over it. Even if it's 1% likely to be used in this way, it makes sense for wealthy nations to spend on it. But yeah, it's not the same story as for the IC boom. >Is there anything even a tiny QC can do better, faster, and cheaper than a classical computer? This is a really good question, and I don't know the answer. If I were to try, I'd focus on QC efficient algorithms, and what you can do with that in an application. So, in your system a QC is a magic box that takes an O(n^2) algo and makes it O(n), say. But for ordinary humans, n is very small, so this won't matter. I don't think there is mundane problem, e.g. one dealing with ordinary productivity, that a QC can do better than classical. It's shaping up to be a nation-state funded capital intensive information superweapon against private communication. And you know what? Maybe if you can maintain the infrastructure and staff to build one, you deserve to have it! It's especially untroubling if it's capacity is limited, like being able to read 10 2048-bit RSA encrypted messages per day. That's a superpower, but a very limited and expensive one, which I am fine with.
zucker42 5y ago
If anyone would like to try their hand at predicting when this might happen, there's this Metaculus question[1]. Looks like the community median is 2047 right now. [1] https://www.metaculus.com/questions/8169/256-bit-ecc-to-be-broken/ https://www.metaculus.com/questions/8169/256-bit-ecc-to-be-b...
childintime 5y ago
Moore's law added 5 zeroes to the transistor count in 40 years. Deep learning compute does a similar feat in just 5 years. So my uninformed guess is encryption could be cracked before the decade is out, but if not still in most people's lifetime. Way before this happens BTC has either lost its value or its ECC has been dramatically upgraded.
- speed_spread 5y ago
  "Moore's Law" isn't like gravity. It's the trillions of monies invested in fab tech that kept transistor count growing.
errcorrectcode 5y ago
The timeline seems like an unknowable due to the nature of technological progress: discontinuous jumps that usually require discover manufacturing techniques in secret. Not as a UFO or conspiracy theory, but as a realization that there are some technologies intentionally kept secret to maintain military, political, or economic advantages. When that distance between in-the-pipeline reaches a magnitude delta of 2, then I'd be concerned about what's already being designed or kept in secret. Scaling QC is a difficult, unsolved problem of manufacturing.
madengr 5y ago
jzer0cool 5y ago
That's a lot of qubits. Could someone share ELI5 the form factor of having just 1 qubit? Any kind of simple project that could be made DIY at home?

117 points by Sami_Lehtinen 5y ago

"No time soon". I'd be careful. I remember when Bill Gates said we would never need more than 128Kb memory. Crypto is giving huge incentive to speed up the development of quantum. We could get to 1 million qbits faster than many think.

lrem 5y ago
Do you think any of the large players will get into crypto? Or, any of the crypto players will build a business steady enough, to try developing something so ambitious?
- bo1024 5y ago
  Another question is exactly how far ahead the NSA is. Remember their budget was estimated at $10 billion back in 2013, more than facebook’s revenue at that time, twice what Twitter’s is today. So picture two companies the size of Twitter working largely on breaking encryption.
  - er4hn 5y ago
    An indicator of that may be the fact that the NSA is in the process of finalizing their selection of quantum resistant algorithms. After that expect those algorithms to end up in the FIPS 140 certification process and percolating into requirements for government agencies to use. The NSA has an interest in making sure that classified information stays that way for as long as the classification lasts. That is at least 25 years, potentially up to 75 years (src: https://en.wikipedia.org/wiki/Classified_information_in_the_United_States#Automatic_declassification https://en.wikipedia.org/wiki/Classified_information_in_the_...) so one could infer that the NSA believes there is a reasonable chance quantum computers will exist and be able to break classical encryption within that timeframe.

SimonTTTT 5y ago

[dead]

jmnicolas 5y ago
> The popular press are sucked into the idea that the technology is more capable than it is, the community can't shout the boosters down because it's all about perception. Reminds me of AI...

throawaybong 5y ago

> it would require 13 × 10^6 physical qubits It's 13 million qubits. It's weird they write it in scientific notation, it makes it look larger. If qubits got to the moore-like-bandwagon, that is not many multiplications away from current amount.

dekhn 5y ago
scientific notation would look more like "1.3 x 10*5" (only one leading digit: https://en.wikipedia.org/wiki/Scientific_notation#Normalized_notation https://en.wikipedia.org/wiki/Scientific_notation#Normalized...)
- VikingCoder 5y ago
  Don't you mean 1.3 x 10 ^ 7?
  - dekhn 5y ago
    Probably :)
- black6 5y ago
  Yes. It looks more like engineering notation (up to three digits to the left of the decimal and the power of 10 divisible by 3).
zinekeller 5y ago
Well, except that the approximate time for an additional "stable" qubit is currently plateauing, so outside a very lucky breakthrough, it's still unlikely. The official record for an actual running Shor's algorithm is 21 (not bits, just the number 21), which is still puny (there was an attempt to factor out 35 (again 35 as in 5×7), but it ended in failure due to quantum noise).
- mburee 5y ago
  But Shor's algorithm is for prime factorization, right? Are there equally faster algorithms available for elliptic curves?

dijit 5y ago

It's only 1 paragraph but to save someone the click: it's not happening soon.

sliken 5y ago
Indeed, in fact I'd consider that an understatement of the situation.
JulianMorrison 5y ago
Another way of putting it would be "pretty simple and quick - if you can achieve a completely infeasible number of qubits". That is to say, it's an algorithmic overhang, the knowledge how is available but held back by not knowing how to achieve the hardware needed. The risk being that someone could discover "how to make qubits" tomorrow, and although (because it's hardware) it might take a short while to turn that into an industrial qubit pipeline, we don't yet actually know yet that it's mechanically impossible to do.
charlieyu1 5y ago
It will probably be earlier than fully crack SHA1 (aka finding the preimage). And SHA1 is already considered a problem for at least a decade. If post-quantum cryptography algorithms are already there, I can see EC being abondoned soon

rmbyrro 5y ago

I wouldn't be so certain it's not happening "anytime soon". They speculated about one way to break it. There could be several ways of using QC to break EC. What is the chance that at least one of those other ways require, say only 1,000 qubits? Oops, it's a two year time frame now. It might be a small chance, but I don't think we can discard it. Better plan for the worse.

dane-pgp 5y ago
It would be nice to have a probability distribution over how quickly quantum computers could reach the necessary level, using this paper as just one datapoint and looking at other examples of cryptographic breakthroughs and technological capability curves. By combining such a probability distribution with an estimate of how much damage could be done (or how much profit could be generated) by an enemy breaking elliptic curve encryption, it would then be possible to give a reasoned guess for how much to spend on bringing forward quantum-resistant cryptography.
upofadown 5y ago
>What is the chance that at least one of those other ways require, say only 1,000 qubits? A thousand physical qubits with current error rates? Pretty much impossible would be my guess.

deleted 5y ago

[deleted]

tromp 5y ago

The paper he discusses claims that Bitcoin private keys are only vulnerable for about 10 minutes, but that only applies to P2PKH (pay to public key hash) with never before used keys. However, millions of BTC are vulnerable with no quantum computation time limits. This includes about 1.75 M BTC in P2PK/raw multisig outputs, and over 4M BTC due to known pubkeys and scripts, revealed in the Bitcoin blockchain.

shiado 5y ago
The 10 minutes also isn't accurate because the ability to obtain private keys from public keys would completely destroy the incentives of the Bitcoin network. Miners are incentivized and compensated for including transactions in a block due to fees. The ability to steal the coins from an incoming transaction would create incentives not to include transactions in a block and to instead spam the network with as many malicious nodes as possible to halt the proliferation of transactions.

hangonhn 5y ago

Does anyone know of a similar sort of estimates for AES? Do we know if Grover's algorithms can or cannot be applied to AES? Thanks.

ahelwer 5y ago
It can but you only get a sqrt(n) speedup. Which is the same as halving the bits in the search space. Not trivial, but probably doesn't move it to tractable territory given appropriate key sizes.

sgdjgkeirj 5y ago

This is not as comfortable a margin as it seems. If a direct implementation of the algorithm takes a few million qubits, it may well be that both better algorithms, better error correcting codes, and optimizing their combination to the hardware platform will shave a few orders of magnitude. So in 5 years to a decade this could get uncomfortably close to the danger zone. Main issue is that in cryptography (1) some secrets encrypted now will be secret in a decade (2) changing standard is very hard and takes a long time

c1ccccc1 5y ago

Wow, this does not look like an exponentially large number of qubits. I thought elliptic curve cryptography was supposed to be secure against quantum computers, but this makes it seem like cracking is still polynomial, just with a larger constant in front than RSA has. Are there any public key techniques that are actually secure against quantum computers? (meaning they would take exponential time to break using the best known algorithms)

hatsunearu 5y ago
ECC is more vulnerable to quantum computing than RSA is. That's the stated reason why the NSA wants the world to move away from ECC to "post quantum cryptography".
- c1ccccc1 5y ago
  Thanks for the correction, seems I was confused. And thanks for the pointer to post-quantum cryptography, widipedia has a nice list of algorithms.

IndrekR 5y ago

Given that quantum computers double in size in time it takes to complete one PhD thesis, it is not too far fetched to reach such capacity within a reasonable time. So far this "law" has held.

sp332 5y ago
Well, what's the biggest one you've seen run Shor's algorithm?
jmnicolas 5y ago
They double in size but do they double in performances?

sweis 5y ago

I think we are many, many years away from a quantum computer being able to break 256-bit ECC: https://sam-jaques.appspot.com/quantum_landscape https://sam-jaques.appspot.com/quantum_landscape https://www.bsi.bund.de/EN/Topics/Cryptography/QuantumComputing/quantum_computing_node.html https://www.bsi.bund.de/EN/Topics/Cryptography/QuantumComput... The current record in factoring with Shor's algorithm is 21. Yes. 3*7. That record has stood for 12 years and arguably is not even running Shor's because it required a priori knowledge of the factors. Even with "cheating" by using knowledge of the factors, in 20 years we have seen seen a single bit of improvement. None of the new quantum computers from IonQ, Google, or QuEra with 32-256 qubits are even able to even replicate those early results. D-Wave claims 5000 qubits, but that is for adiabatic QC, which to my knowledge, cannot run Shor's algorithm. To be a threat, QCs need millions of qubits and orders of magnitude better error correction. I think people make the mistake of looking at the speed of progress of classical computers and thinking it applies to QC. It's just not happening.

acchow 5y ago
Classical silicon chips got to exponential growth because chips were profitable - the profits could be poured back into R&D enabling a natural feedback loop. Profitability wasn't terribly difficult because computers were VERY fast at calculations compared to the next best thing - humans. For QC to hit natural exponential growth, it would need to be economically feasible compared to the next best thing - classical computers. Is there anything even a tiny QC can do better, faster, and cheaper than a classical computer?
- javajosh 5y ago
  The most sensational, and arguably most valuable, use is breaking hard encryption, so QC has "nation state STEM/security funding" written all over it. Even if it's 1% likely to be used in this way, it makes sense for wealthy nations to spend on it. But yeah, it's not the same story as for the IC boom. >Is there anything even a tiny QC can do better, faster, and cheaper than a classical computer? This is a really good question, and I don't know the answer. If I were to try, I'd focus on QC efficient algorithms, and what you can do with that in an application. So, in your system a QC is a magic box that takes an O(n^2) algo and makes it O(n), say. But for ordinary humans, n is very small, so this won't matter. I don't think there is mundane problem, e.g. one dealing with ordinary productivity, that a QC can do better than classical. It's shaping up to be a nation-state funded capital intensive information superweapon against private communication. And you know what? Maybe if you can maintain the infrastructure and staff to build one, you deserve to have it! It's especially untroubling if it's capacity is limited, like being able to read 10 2048-bit RSA encrypted messages per day. That's a superpower, but a very limited and expensive one, which I am fine with.

zucker42 5y ago

If anyone would like to try their hand at predicting when this might happen, there's this Metaculus question[1]. Looks like the community median is 2047 right now. [1] https://www.metaculus.com/questions/8169/256-bit-ecc-to-be-broken/ https://www.metaculus.com/questions/8169/256-bit-ecc-to-be-b...

childintime 5y ago

Moore's law added 5 zeroes to the transistor count in 40 years. Deep learning compute does a similar feat in just 5 years. So my uninformed guess is encryption could be cracked before the decade is out, but if not still in most people's lifetime. Way before this happens BTC has either lost its value or its ECC has been dramatically upgraded.

speed_spread 5y ago
"Moore's Law" isn't like gravity. It's the trillions of monies invested in fab tech that kept transistor count growing.

errcorrectcode 5y ago

The timeline seems like an unknowable due to the nature of technological progress: discontinuous jumps that usually require discover manufacturing techniques in secret. Not as a UFO or conspiracy theory, but as a realization that there are some technologies intentionally kept secret to maintain military, political, or economic advantages. When that distance between in-the-pipeline reaches a magnitude delta of 2, then I'd be concerned about what's already being designed or kept in secret. Scaling QC is a difficult, unsolved problem of manufacturing.

madengr 5y ago

jzer0cool 5y ago

That's a lot of qubits. Could someone share ELI5 the form factor of having just 1 qubit? Any kind of simple project that could be made DIY at home?