[RcouF1uZ4gsC]

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]

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]

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-i...

[latenightcoding]

Quantum Annealing is not a threat for cryptography. You can safely dismiss these sort of articles.

[krastanov]

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.

[sweis]

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

[IncRnd]

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...

[NavinF]

"When will 256 bit ECC become insecure?" : 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]

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]

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]

> 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.

[bwesterb]

It's hard to say. Here is a great paper that tries to answer this question.

https://arxiv.org/pdf/2009.05045v1.pdf

See Figure 11. Optimistically 15 years. Pessimistically 35 years. But anything can happen.

[Zamicol]

The linked study is about RSA, not elliptical curve cryptography

[upofadown]

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.

[krastanov]

Does that matter? Both are based on some hidden subgroup problem and both are breakable in a similar way.

[Asraelite]

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.

[ghaff]

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.

[upofadown]

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.

[danuker]

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_...

[rvz]

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

[1] https://github.com/algorand/falcon

[jleahy]

The modern wallets don’t publish the public key though, so this is not likely to help.

[baby]

That's only Bitcoin though

[jleahy]

He did say bitcoin specifically.

[adastra22]

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.

[kvathupo]

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.

[baby]

I'm betting on never

[bawolff]

https://xkcd.com/678/

Any predictions on these time scales are pretty much pointless.