What is quantum computing?
Quantum Computing is a new paradigm in computer science that leverages quantum phenomena like superposition, entanglement and interference to gain a significant speedup over classical algorithms when solving some complex problems.
Here is a post to find out more about quantum computing
Impact of quantum computing in cryptography
This opens incredible new opportunities in science and business, but also new threats. A quantum algorithm created by Peter Shor in 1994 provides an exponential speedup to integer factorization and the discrete logarithm problem.
The intractability of these problems is, precisely, the foundation of most of the public key cryptography the world uses today, like RSA and Elliptic Curve.
While breaking our current keys might take several thousand years using classical algorithms, it could be a task of just a few hours for a large quantum computer.
Another quantum algorithm created by Lov Grover in 1996 provides a quadratic speedup to reverse a black-box function. This reduces the security of any generic hash function or symmetric key cryptosystem.
So, quantum computers will have the ability to reduce or eliminate the security of our current cryptography.
Luckily in this regard, quantum computers are still a novel technology.
Currently their size is in the order of 100 qubits (or quantum bits), while running Shor’s algorithm requires many more, maybe some millions depending on their quality.
Latest roadmaps expect to reach the 1 million qubit milestone by the end of this decade. Estimations are that RSA and Elliptic Curve cryptography will be broken somewhere between the 30s and mid 40s.
Efforts to mitigate that impact: PQCrypto
The cryptography community is actively involved in addressing this risk by designing new cryptosystems that can be executed in classical computers but cannot be attacked by quantum computers. This is called Post Quantum Cryptography.
NIST, the US National Institute of Standards and Technology, is now in the process of creating a post quantum crypto standard which is expected to be ready between 2022 and 2024.
What should I do? ?
We can expect to be changing our crypto algorithms to new post quantum alternatives in the second half of this decade. Considering how cryptography is embedded in all our IT processes, this will not be a simple task.
Before the time for migration arrives, we can get ready by analyzing how we use cryptography today.
- You should review which encrypted data and signatures performed now need to remain secure for decades and protect them accordingly.
- You may also want to get ready to change your cryptographic algorithms quickly and easily. This is called crypto-agility and it may well be an advantage in the future.
Impact to Blockchain
Quantum computing will have a direct impact on blockchains.
One of the most important features of Blockchain is immutability. Data, hashes and signatures in a blockchain are expected to be there forever. And available to scrutiny by attackers.
In summary, the most relevant risks are:
- Signatures in a Blockchain can allow an attacker to retrieve the associated private key.
- Hash calculation may be simplified.
- Hash collision (two inputs to a hash function providing the same result) finding may be achievable.
So, current blockchains will also need their own migration. This will likely take the form of a fork or a protocol update, creating a new post-quantum chain or addresses and a limited window of time for users to migrate their data and assets.
Adapting blockchains to the postquantum era will require increased storage and computing resources. Probably the evolution of technology will account for that in most cases. Perhaps IoT applications, where resource constraints are greatest, will have greater difficulty in adapting.
Further learning
There are several ongoing efforts to understand how blockchains might adapt to the postquantum era. To learn more, I suggest that you visit these resources:
- Video: Introducción a la criptografía para todos los públicos (Spanish). A video with an easy-to-follow introduction to cryptography.
- Video: ¿Qué es la computación cuántica? (Spanish). A video with an easy-to-follow introduction to quantum-computing.
- Paper: Towards Post-Quantum Blockchain: A Review on Blockchain Cryptography Resistant to Quantum Computing Attacks. A comprehensive article with a highly detailed analysis of the impact of quantum computing to Blockchain. Full of great references. Take a look at the “Post-quantum Blockchain Proposals” chapter.
- Paper: Report on Post-Quantum Cryptography. The initial report by NIST starting the postquantum standardization process.
- Paper: Post-Quantum Cryptography: Current state and quantum mitigation. A document by the European Agency for Cybersecurity summarizing the families of postquantum cryptography algorithms with details on the ones that have passed to phase 3 of the NIST standardization process. It includes measures that can be adopted to mitigate the risks associated with quantum computing.
- Article: Quantum computers and the Bitcoin blockchain. An explanatory article showing what Bitcoin addresses are at risk in front of a quantum computer.
- Paper: Quantum attacks on Bitcoin, and how to protect against them. A detailed analysis on quantum attacks to Bitcoin.
- Article: How will quantum computing affect Blockchain? An explanatory article explaining the postquantum provisions on Ethereum-2 and Ethereum-3.
Jaime Gómez García
Universia
Architecture and IT & Telecom Infrastructure expert. I learn about the Internet, networks and applied cryptography every day since the mid 90’s.
