Quantum threat: Why you need to consider it now?
What’s a quantum computer (in plain language)?
A quantum computer uses the rather strange properties of very small particles (smaller than an atom) to encode information and performs special operations on that information. They are not like a normal computer (referred to as a “Classical Computer”), as they don’t have a monitor, keyboard or mice, but rather they are a special machine that needs to be connected to a classical computer to be practical.
They work entirely differently from classical computers. They don’t have the usual CPU, RAM and a disk drive, but rather an array of Quantum Bits, or qubits, for information storage and quantum gates for operations. Unlike a classical computer which can store a 1 or a 0 in each bit, a quantum computer stores the probabilities of each qubit being a 1 or a 0. This combined with its special quantum gate operations, allows a quantum computer with many qubits to rapidly perform in a single step, what may take a classical computer billions of years. This is only a brief explanation of what a quantum computer is, and you can watch videos and read more about them in the references section. (See Houston-Edwards (2017a) and Houston-Edwards (2017b) for a good introduction by video).
How does that affect cryptography? Why worry?
Cryptography, or the secret encoding and decoding of data, is the mainstay of secure electronic communications. Since ancient times, cryptography works because it is a lop-sided operation: with the correct key or keys, encoding and decoding is easy; without them, it is very hard. Although it is theoretically possible to break all commonly used cryptographic schemes, doing so can take such a long time and use so many resources that it’s simply not worth it, and that means our information stays secure.
Broadly speaking, there are two types of encryption algorithms (also called ciphers): symmetric and asymmetric.
- Symmetric ciphers encode a message with a secret number (called a key). A prerequisite of a symmetric cipher is that the sender and the receiver must have copies of the same secret key, somehow shared securely in advance. Symmetric ciphers can offer very strong security and operate relatively efficiently on most computers.
- Asymmetric ciphers have two keys: one to encode and the other to decode. The encoding key cannot be used for decoding, so it can be widely and publicly shared. The decoding key is kept secret and does not need to be exchanged with anyone else. This avoids the problem of having to securely share a secret key to begin with. Asymmetric ciphers are usually computationally intensive and are best used to send very short messages.
Most modern encrypted internet-based services use a combination of Symmetric and Asymmetric ciphers to operate. They use intensive Asymmetric ciphers to establish identity and securely exchange a secret key. From then on, only use the more efficient symmetric ciphers with the secret key that has been exchanged.
Quantum computers have special properties that allow them to break some popular ciphers very quickly, and a couple of prominent algorithms have been developed for quantum computing that allow this. They are Grover’s Algorithm and Shor’s Algorithm.
Grover’s algorithm
Named after Lov Grover’s discovery in 1996 (Grover, 1996), this algorithm allows a sufficiently powerful quantum computer to break into a message that has been encrypted with a Symmetric cipher. The result of using this algorithm is that instead of having to try at least half of the potential keys (on average) to find the correct one, you only need to try the square root of that number.
For example, to break into a message encrypted with the popular AES cipher with a 128-bit key, this will take at most 2128 (or about 340 trillion trillion trillion) attempts, unless you are lucky enough to guess the key on the first attempt. So on average, you will break the message halfway between 1 and 2128 attempts, which is 2127 attempts. That’s still a lot of attempts, about 170 trillion trillion trillion of them in fact! Even at a billion attempts per second, it would still take over 5 billion trillion years to find the key 50% of the time, on average. This is considered to be quite secure by classical computer standards.
Using Grover’s algorithm on a quantum computer makes it much faster. Instead of the time being dictated by halving the key length (from 2128 to 2127), with Grover’s algorithm and a sufficiently large quantum computer, the time taken is the square root of 2128, which is 264. At a billion attempts per second, it will take a single quantum computer just over 580 years, or it would take 1000 quantum computers just over 200 days. This is not secure for any information that needs to be kept secret from someone with 1000 capable quantum computers for over 200 days.
Shor’s algorithm
Shor’s algorithm, discovered by Peter Shor in 1994 (Shor, 1994), allows an arbitrarily large quantum computer to break RSA cryptography, ECDHE key exchange and other asymmetric systems within minutes. The RSA Asymmetric cipher is used as the security backbone of almost all encrypted websites. The more qubits the quantum computer has, the larger the RSA key that can be broken. Right now, the largest quantum computer is agreed by most to be IBM’s 127-qubit “Eagle” (IBM, 2021), and it does not have the capability to break the commonly-used 2048-bit RSA keys (which would require 4099 qubits). The problem here is that it will not be long before 4099-bit quantum computers become a reality. IBM is already planning to produce a 1121 qubit computer by 2023, the Condor (Gambetta, 2020). Further advances are expected within years after that, for example Google’s current roadmap is eventually planning for a 1-million qubit machine (Google, n.d.).
Why worry now?
We don’t have quantum computing that is capable yet of breaking today’s strong encryption, so why worry about any of this now? Essentially, because your data today will become unsafe within a decade or so. There is evidence that state actors are planning to copy and retain high-value data now (Booz Allen Hamilton, 2021), so that when sufficiently large quantum computers are available, it may be readily decrypted.
What do I need to do?
As a developer
For Symmetric ciphers, it’s relatively easy to fix this problem: use a larger key. In the case above, use AES256 instead of AES128. To break AES256, even a quantum computer will still take about 10 billion trillion years. One important item to note is that the key you use must be random. If it is not, then it may be easier to guess the key than try all the possibilities.
For Asymmetric ciphers, the situation is more complicated. Increasing the key size of RSA for example from 2048 to 4096 bits will help in the short term, but this too will falter when a quantum computer of sufficient size is built. To be properly secure, a new form of Asymmetric cipher is required. Thankfully, there are a few ciphers in development and they have so far stood up to mathematical scrutiny. To date, ciphers such as NTRU, Classic McElice and SABER appear to be post-quantum secure. NIST maintains a standardisation process that will result in strong post-quantum algorithms (NIST, 2016).
As a user of the internet
When we use internet services, we usually have very little option about how our data is encrypted; we trust organisations to do this properly for us. As we approach quantum computer supremacy (the point in time where quantum computers can solve problems in a reasonable amount of time that classical computers can never do), more service providers will move to a post-quantum security posture. Of course, when quantum supremacy is achieved, internet services that are providing RSA 2048-bit and AES encryption with 128 bits are to be avoided, lest your data be promptly decrypted. In the meantime, 2048 is okay if your data will be worthless in about 10 years, but if you’re dealing with data that needs to be secure for longer than 10 years, you may wish to consider services that offer post-quantum security right now.
The future of quantum computing
Quantum computers are of course not only useful for the breaking of ciphers. They are an important tool in many fields including:
- Biological and chemical engineering
- Artificial intelligence
- Financial services
- Manufacturing
- Materials science
They may predict traffic jams before they occur so you can avoid them, simulate molecule interactions with incredible accuracy, predict large-scale electricity use potentially years in advance, and find the optimal route for delivery vans. Many of quantum computing’s possible applications are yet to be discovered!
References
Booz Allen Hamilton. (2021). Chinese Threats in the Quantum Era. Booz Allen Hamilton. Retrieved December 22, 2021, from https://www.boozallen.com/expertise/analytics/quantum-computing/chinese-cyber-threats-in-the-quantum-era.html
Gambetta, J. (2020, September 15). IBM’s roadmap for scaling quantum technology. IBM Research. Retrieved December 22, 2021, from https://research.ibm.com/blog/ibm-quantum-roadmap
Google. (n.d.). Our quantum computing journey. Google Quantum AI. Retrieved December 22, 2021, from https://quantumai.google/learn/map
Grover, L. K. (1996, July 01). A fast quantum mechanical algorithm for database search. STOC ’96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing. https://dl.acm.org/doi/10.1145/237814.237866
Houston-Edwards, K. (2017, April 20). How to Break Cryptography | Infinite Series. YouTube. Retrieved December 22, 2021, from https://www.youtube.com/watch?v=12Q3Mrh03Gk
Houston-Edwards, K. (2017, April 28). Hacking at Quantum Speed with Shor’s Algorithm | Infinite Series. YouTube. Retrieved December 22, 2021, from https://www.youtube.com/watch?v=wUwZZaI5u0c
IBM. (2021, November 16). IBM Unveils Breakthrough 127-Qubit Quantum Processor. IBM Newsroom. Retrieved December 22, 2021, from https://newsroom.ibm.com/2021-11-16-IBM-Unveils-Breakthrough-127-Qubit-Quantum-Processor
NIST. (2016). Post-Quantum Cryptography | CSRC. NIST Computer Security Resource Center. Retrieved December 22, 2021, from https://csrc.nist.gov/projects/post-quantum-cryptography
Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring,. IEEE Xplore. Retrieved 12 22, 2021, from https://ieeexplore.ieee.org/document/365700