5 ms·

HN Crypto and Quantum Experts. What is your prediction when classical public key encryption using elliptical curve cryptographic becomes practically vulnerable

HN Crypto and Quantum Experts. What is your prediction when classical public key encryption using elliptical curve cryptographic becomes practically vulnerable to quantum computers, such that we would need these PQC algorithms. 10 years out? 20 years out? 50 years out? 100 years out?

hannob 4y ago
I've been following this space for a while and this is a good question, but I think the answer is really a "ranges from 10 years to never". There's a lot of investment currently in the quantum computer space (+ a lot of hype and scams). Yet this is still all very early research and far away from any practical use. The challenges to really build a QC that can break cryptography are enormous - and it is absolutely a possibility that they're too big to overcome.
- chasil 4y ago
  This article asserts that D-Wave and other quantum annealing devices will be able to mount attacks long before a machine exists that can run Shor's algorithm with error-corrected qubits in sufficient quantity. https://www.forbes.com/sites/arthurherman/2021/06/07/q-day-is-coming-sooner-than-we-think/?sh=1a7676f83f5d https://www.forbes.com/sites/arthurherman/2021/06/07/q-day-i...
  - latenightcoding 4y ago
    Quantum Annealing is not a threat for cryptography. You can safely dismiss these sort of articles.
  - krastanov 4y ago
    To second what the sibling comment has said, "quantum annealing" claims by DWave are considered fairly overblown (on some rare occasions even misleading/scammy). If the claims of this article held, they would have been much better known in the field and published in much more popular venues.
Asraelite 4y ago
I want to see these actually being implemented in current software ASAP (layered with traditional crypto). As-is it's possible to capture encrypted traffic out of the air, store it for however many decades are needed, and then decrypt it in future.
NavinF 4y ago
"When will 256 bit ECC become insecure?" : https://www.metaculus.com/questions/8169/?invite=GpV2Dc https://www.metaculus.com/questions/8169/?invite=GpV2Dc The community prediction is 22% by 2032 which seems way too high IMO. I predict 5% due to advances in automated algorithm search and 0% due to quantum computers in that time frame.
- marcosdumay 4y ago
  Why would a croudsoursing site know that? This is the kind of question where 1 expert will fare better than the average of 90% of the people.
  - NavinF 4y ago
    Sure. If that 1 expert bothered to post a falsifiable prediction like “x% likely this’ll happen by year y”, the rest of us could read their argument and update our predictions. Unfortunately that’s pretty uncommon so everyone has to go by base rates (crypto algorithms seem to last x years historically) and vague guesses (quantum computer capabilities seem to be doubling every x years so I dunno maybe enough qbits by 2050)
    - marcosdumay 4y ago
      > quantum computer capabilities seem to be doubling every x years so I dunno maybe enough qbits by 2050 Ok, let's get a try from a mildly informed person, that is also probably better than the 90% average... The number of qbits seems to be growing linearly, at about 7 qbits every 2 years. Extending that trend says that none of us will ever see a quantum computer break 256-bits ECC. But I really doubt the trend will hold. Quantum computing seems prone to surprise gains, and those are unpredictable by their nature. About this: > crypto algorithms seem to last x years historically I don't think we have enough data to decide on an average, but the distribution does surely look fat-tailed, so any statistic summary you make from it will be useless. If history tells anything, it is that algorithms that have minor attacks will be broken quickly, and algorithms that don't have minor attacks will survive for very long.
IncRnd 4y ago
I think what you are asking may better be answered by ignoring PQC and following CNSA recommendations for up to TOP SECRET. The crypto is likely what you already use, but it defines how to get enough bits of security from an algorithm. There is a table of transition algorithms on the second or third page, depending on your screen size. [1] [1] https://apps.nsa.gov/iaarchive/programs/iad-initiatives/cnsa-suite.cfm https://apps.nsa.gov/iaarchive/programs/iad-initiatives/cnsa...
danuker 4y ago
I expect you'd see a large increase in Bitcoin Days Destroyed, perhaps unrelated to market volume, should someone break ECDSA. Bitcoin uses ECDSA to validate whether coins were spent by the owner of an address. https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_Algorithm https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_...
- jleahy 4y ago
  The modern wallets don’t publish the public key though, so this is not likely to help.
  - baby 4y ago
    That's only Bitcoin though
    - jleahy 4y ago
      He did say bitcoin specifically.
- rvz 4y ago
  Well good thing that some of the cryptographers that created Falcon [0][1] (the ones who developed Algorand) for post-quantum cryptography for digital signatures use cases is considered to be 'standardised' as such. This tells me that Algorand is one of the more serious blockchain projects out there with top cryptographers as evidenced by Falcon. [0] https://falcon-sign.info https://falcon-sign.info [1] https://github.com/algorand/falcon https://github.com/algorand/falcon
bawolff 4y ago
https://xkcd.com/678/ https://xkcd.com/678/ Any predictions on these time scales are pretty much pointless.
ghaff 4y ago
It's worth noting that the relevant timeframe to implement PQC isn't just when quantum computers become sufficiently fast to break current crypto (assuming the answer isn't never). It can take a decade or longer to re-encrypt data and/or to update cryptographic infrastructure. Given that (varied) expert option on quantum computing being able to break current public key cryptography seems to mostly fall in the 10-20 year range, there is some, at least mild, urgency to start using PQC for the most sensitive data relatively soon.
kvathupo 4y ago
Not an expert, but you should upgrade now to prevent attackers from stealing your encrypted data today, and decrypting it later. That said, you'll have to determine if your data is worth stealing.
bwesterb 4y ago
It's hard to say. Here is a great paper that tries to answer this question. https://arxiv.org/pdf/2009.05045v1.pdf https://arxiv.org/pdf/2009.05045v1.pdf See Figure 11. Optimistically 15 years. Pessimistically 35 years. But anything can happen.
- Zamicol 4y ago
  The linked study is about RSA, not elliptical curve cryptography
  - krastanov 4y ago
    Does that matter? Both are based on some hidden subgroup problem and both are breakable in a similar way.
  - upofadown 4y ago
    It is generally accepted that elliptical curge cryptography is a bit easier to break with Shor's algorithm than RSA. Something like half as hard, but it probably would not make any real difference in practice. So the paper is directly applicable to elliptic curves to the extent that it is applicable to anything.
adastra22 4y ago
10-20 years. As soon as we have atomically precise manufacturing, there are multiple approaches to making stable, scalable quantum computers that work. I see APM being possible on that time horizon. One company, Zyvex, has already prototyped those capability in the lab.
upofadown 4y ago
We have not been able to implement even a single logical qubit of the sort required to run Shor's algorithm (we would need thousands). It is impossible to extrapolate from zero.
sweis 4y ago
The record for factoring using a quantum computer is 21. Don't read that as 21 bits. 3*7. This has been the record for 12 years and that is arguably a result that is "cheating" with a priori knowledge of the factors. There are some other examples of people factoring special-form composites that are particularly easy to factor on quantum computers, but those are basically stunts with no impact. To threaten RSA, quantum computers need to increase the number qubits 6 orders of magnitude and improve the error correction at least 2 orders of magnitude. Check out this blog post for an illustration of where we are at: https://sam-jaques.appspot.com/quantum_landscape https://sam-jaques.appspot.com/quantum_landscape
baby 4y ago
I'm betting on never

hannob 4y ago

I've been following this space for a while and this is a good question, but I think the answer is really a "ranges from 10 years to never". There's a lot of investment currently in the quantum computer space (+ a lot of hype and scams). Yet this is still all very early research and far away from any practical use. The challenges to really build a QC that can break cryptography are enormous - and it is absolutely a possibility that they're too big to overcome.

chasil 4y ago
This article asserts that D-Wave and other quantum annealing devices will be able to mount attacks long before a machine exists that can run Shor's algorithm with error-corrected qubits in sufficient quantity. https://www.forbes.com/sites/arthurherman/2021/06/07/q-day-is-coming-sooner-than-we-think/?sh=1a7676f83f5d https://www.forbes.com/sites/arthurherman/2021/06/07/q-day-i...
- latenightcoding 4y ago
  Quantum Annealing is not a threat for cryptography. You can safely dismiss these sort of articles.
- krastanov 4y ago
  To second what the sibling comment has said, "quantum annealing" claims by DWave are considered fairly overblown (on some rare occasions even misleading/scammy). If the claims of this article held, they would have been much better known in the field and published in much more popular venues.

Asraelite 4y ago

I want to see these actually being implemented in current software ASAP (layered with traditional crypto). As-is it's possible to capture encrypted traffic out of the air, store it for however many decades are needed, and then decrypt it in future.

NavinF 4y ago

"When will 256 bit ECC become insecure?" : https://www.metaculus.com/questions/8169/?invite=GpV2Dc https://www.metaculus.com/questions/8169/?invite=GpV2Dc The community prediction is 22% by 2032 which seems way too high IMO. I predict 5% due to advances in automated algorithm search and 0% due to quantum computers in that time frame.

marcosdumay 4y ago
Why would a croudsoursing site know that? This is the kind of question where 1 expert will fare better than the average of 90% of the people.
- NavinF 4y ago
  Sure. If that 1 expert bothered to post a falsifiable prediction like “x% likely this’ll happen by year y”, the rest of us could read their argument and update our predictions. Unfortunately that’s pretty uncommon so everyone has to go by base rates (crypto algorithms seem to last x years historically) and vague guesses (quantum computer capabilities seem to be doubling every x years so I dunno maybe enough qbits by 2050)
  - marcosdumay 4y ago
    > quantum computer capabilities seem to be doubling every x years so I dunno maybe enough qbits by 2050 Ok, let's get a try from a mildly informed person, that is also probably better than the 90% average... The number of qbits seems to be growing linearly, at about 7 qbits every 2 years. Extending that trend says that none of us will ever see a quantum computer break 256-bits ECC. But I really doubt the trend will hold. Quantum computing seems prone to surprise gains, and those are unpredictable by their nature. About this: > crypto algorithms seem to last x years historically I don't think we have enough data to decide on an average, but the distribution does surely look fat-tailed, so any statistic summary you make from it will be useless. If history tells anything, it is that algorithms that have minor attacks will be broken quickly, and algorithms that don't have minor attacks will survive for very long.

IncRnd 4y ago

I think what you are asking may better be answered by ignoring PQC and following CNSA recommendations for up to TOP SECRET. The crypto is likely what you already use, but it defines how to get enough bits of security from an algorithm. There is a table of transition algorithms on the second or third page, depending on your screen size. [1] [1] https://apps.nsa.gov/iaarchive/programs/iad-initiatives/cnsa-suite.cfm https://apps.nsa.gov/iaarchive/programs/iad-initiatives/cnsa...

danuker 4y ago

I expect you'd see a large increase in Bitcoin Days Destroyed, perhaps unrelated to market volume, should someone break ECDSA. Bitcoin uses ECDSA to validate whether coins were spent by the owner of an address. https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_Algorithm https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_...

jleahy 4y ago
The modern wallets don’t publish the public key though, so this is not likely to help.
- baby 4y ago
  That's only Bitcoin though
  - jleahy 4y ago
    He did say bitcoin specifically.
rvz 4y ago
Well good thing that some of the cryptographers that created Falcon [0][1] (the ones who developed Algorand) for post-quantum cryptography for digital signatures use cases is considered to be 'standardised' as such. This tells me that Algorand is one of the more serious blockchain projects out there with top cryptographers as evidenced by Falcon. [0] https://falcon-sign.info https://falcon-sign.info [1] https://github.com/algorand/falcon https://github.com/algorand/falcon

bawolff 4y ago

https://xkcd.com/678/ https://xkcd.com/678/ Any predictions on these time scales are pretty much pointless.

ghaff 4y ago

It's worth noting that the relevant timeframe to implement PQC isn't just when quantum computers become sufficiently fast to break current crypto (assuming the answer isn't never). It can take a decade or longer to re-encrypt data and/or to update cryptographic infrastructure. Given that (varied) expert option on quantum computing being able to break current public key cryptography seems to mostly fall in the 10-20 year range, there is some, at least mild, urgency to start using PQC for the most sensitive data relatively soon.

kvathupo 4y ago

Not an expert, but you should upgrade now to prevent attackers from stealing your encrypted data today, and decrypting it later. That said, you'll have to determine if your data is worth stealing.

bwesterb 4y ago

It's hard to say. Here is a great paper that tries to answer this question. https://arxiv.org/pdf/2009.05045v1.pdf https://arxiv.org/pdf/2009.05045v1.pdf See Figure 11. Optimistically 15 years. Pessimistically 35 years. But anything can happen.

Zamicol 4y ago
The linked study is about RSA, not elliptical curve cryptography
- krastanov 4y ago
  Does that matter? Both are based on some hidden subgroup problem and both are breakable in a similar way.
- upofadown 4y ago
  It is generally accepted that elliptical curge cryptography is a bit easier to break with Shor's algorithm than RSA. Something like half as hard, but it probably would not make any real difference in practice. So the paper is directly applicable to elliptic curves to the extent that it is applicable to anything.

adastra22 4y ago

10-20 years. As soon as we have atomically precise manufacturing, there are multiple approaches to making stable, scalable quantum computers that work. I see APM being possible on that time horizon. One company, Zyvex, has already prototyped those capability in the lab.

upofadown 4y ago

We have not been able to implement even a single logical qubit of the sort required to run Shor's algorithm (we would need thousands). It is impossible to extrapolate from zero.

sweis 4y ago

The record for factoring using a quantum computer is 21. Don't read that as 21 bits. 3*7. This has been the record for 12 years and that is arguably a result that is "cheating" with a priori knowledge of the factors. There are some other examples of people factoring special-form composites that are particularly easy to factor on quantum computers, but those are basically stunts with no impact. To threaten RSA, quantum computers need to increase the number qubits 6 orders of magnitude and improve the error correction at least 2 orders of magnitude. Check out this blog post for an illustration of where we are at: https://sam-jaques.appspot.com/quantum_landscape https://sam-jaques.appspot.com/quantum_landscape

baby 4y ago

I'm betting on never