Blockchain Security -- How Soon Do We Need to Worry About Quantum Computers？
Speaking of codebreaking , how soon do we need to worry about quantum computers?
One obvious answer is “when quantum computers arrive”. But is it true?
It’s long before then. As Dr.Michele Mosca explained, if x+y>z, then we have problems, where x is “how long data need to be safe”, y “ time for standardization and adoption”, and z “time until quantum computer are here”.
https://open-ecosystem.org/articles/whats-your-risk-quantum-computers
Shor's 1994 quantum algorithm gives an exponential speed-up over classical computers on factoring large integers and finding discrete logarithms.
Grover's 1996 quantum algorithm gives a polynomial speed-up in unstructured search, from O(N) to O(sqrt(N)).
NIST asymmetric key crypto standards are all vulnerable to attacks from a (large-scale) quantum computer: SP 800-56A Diffie-Hellman, ECDH SP 800-56B RSA encryption FIPS 186 RSA, DSA, ECDSA signatures
Symmetric key crypto (AES, SHA) would also be affected, but less dramatically.
Experts were asked to indicate their estimate for the likelihood of a quantum computer that is able to break RSA-2048 from a short term of 5 years to 30 years.
When will a practical quantum computer exist?
As Mosca wrote: based on responses from the Quantum Threat Timeline Report, some respondents believed that in 5 years there is a 5% probability a quantum computer will exist that can break RSA-2048.
5% may seem like a small risk, but it is a matter of perspective. If you’re talking about the weather, a 5% chance that it may rain means you might bring an umbrella. But a 5% chance of your house burning down will make you act.
Organizations responsible for security will likely conclude that a 5% in 5 years requires action.
In 2016, NIST announced PQCrypto call for proposals and 82 submissions were received the next year.
https://csrc.nist.gov/projects/post-quantum-cryptography
In 2017, NIST announced 69 1st round candidates of cryptographic schemes and later shortlisted 26 2nd round candidates in 2019. It was further reduced to 7 finalists and 8 alternate candidates at the end of the 3rd round in 2020.
In July 2022, NIST announced 4 schemes to be standardized and 4 more for round 4. The first draft of PQCrypto standards is around the corner now.
Feeling excited!