1.6 What about cryptography?
You may have seen media headlines such as
Quantum Security Apocalypse!!!
Y2K??? Get ready for Q2K!!!
Quantum Computing Will Break All Internet Security!!!
These breathless announcements grab your attention and frequently contain egregious errors about quantum computing and security. Let’s look at the root of the concerns and insert some reality into the discussion.
RSA (Rivest-Shamir-Adleman) is a commonly used security protocol, and it works something like this:
- You want to allow others to send you secure communications. This means you give them what they need to encrypt their messages before sending them. You and only you can decrypt what they then give you.
- You publish a public key used to encrypt these messages intended for you. Anyone who has access to the key can use it.
- There is an additional key, your private key. You and only you have it. With it, you can decrypt and read encrypted messages. 190
Though I phrased this in terms of messages sent to you, the scheme is adaptable for sending transaction and purchase data across the Internet and storing information securely in a database.
Indeed, if anyone steals your private key, there is a cybersecurity emergency. Quantum computing has nothing to do with physically taking your private key or convincing you to give it to a bad person.
What if I could compute your private key from the public key?
The public key for RSA looks like a pair of numbers (e, n) where n is a very large integer that is the product of two primes. We’ll call these primes numbers p and q. For example, if p = 982451653 and q = 899809343, then n = p × q = 884019176415193979.
Your private key looks like a pair of integers (d, n) using the very same n as in the public key. It is the d part you must keep secret.
Here’s the potential problem: if someone can quickly factor n into p and q, then they can compute d. That is, fast integer factorization leads to breaking RSA encryption. 204
Though multiplication is very easy and can be done using the method you learned early in your education, factoring can be very, very hard. For products of certain pairs of primes, factorization using known classical methods could take hundreds or thousands of years.
Given this, unless d is stolen or given away, you might feel pretty comfortable about security. But what if there is another way of factoring involving nonclassical computers?
In 1995, Peter Shor published a quantum algorithm for integer factorization that is almost exponentially faster than known classical methods. We analyze Shor’s factoring algorithm in section 10.7. Shor, Peter
This sounds like a major problem! Here is where many articles about quantum computing and security start to go crazy. The key question is, how powerful and of what quality must a quantum computing system be to perform this factorization?
At the time of writing, scientists and engineers are building quantum computers with low four-digit numbers of physical qubits. For example, IBM researchers have a demonstrated qubit count of 1,121. 37 A physical qubit is the hardware implementation of the logical qubits we start discussing in Chapter 7, “One Qubit.”
Physical qubits have noise that causes errors in computation. Shor’s factoring algorithm requires fully fault-tolerant, error-corrected qubits. We can detect and correct errors that occur in logical qubits. This happens today in the memory and data storage in your laptop and smartphone. We explore quantum error correction in section 11.5. logical qubit qubit$logical
As a rule of thumb, assume it will take 1,000 very good physical qubits to make one logical qubit. This estimate varies by the researcher, the degree of marketing hype, and wishful thinking, but I believe 1,000 is reasonable. We discuss the relationship between the two kinds of qubits in Chapter 11, “Getting Physical.” Meanwhile, we are in the Noisy Intermediate-Scale Quantum, or NISQ, era. Physicist John Preskill coined the term NISQ in 2018. Although Preskill initially thought these systems would have between 50 and 100 qubits, or at most a few hundred, it seems apparent that the power of NISQ machines may still be limited even if they have several thousand physical qubits. 172 Preskill, John NISQ Noisy Intermediate-Scale Quantum era
A further estimate is that it will take 2 × 107 = 20 million physical qubits to use Shor’s algorithm to factor the values of n used in RSA today. That’s approximately twenty thousand logical qubits. On the one hand, we have quantum computers with two or three digits worth of physical qubits. We’ll need seven digits’ worth for Shor’s factoring algorithm to break RSA. That’s a huge difference. 91
These numbers may be too conservative, but I don’t think by much. If anyone quotes you much smaller numbers, try to understand their motivation and what data they are using.
There’s a good chance we won’t get quantum computers this powerful until 2035 or much later. We may never get such powerful machines. Assuming we will, what should you do now?
First, you should move to so-called “post-quantum” or “quantum-proof” encryption protocols. These are being standardized at NIST, the National Institute of Standards and Technology, in the United States by an international team of researchers. We believe these protocols can’t be broken by quantum computing systems, as RSA and some of the other classical protocols might be eventually.
You may think you have plenty of time to change over your transactional systems. How long will it take to do that? Financial institutions can take ten years or more to implement new security technology.
Of greater immediate importance is your data. Will it be a problem if someone can crack your database security in 15, 30, or 50 years? For most organizations, the answer is a loud YES. Start looking at hardware and software encryption support for your data using the new post-quantum security standards.
Finally, quantum or no quantum, if you do not have good cybersecurity and encryption strategies and implementations in place now, you are exposed. Fix them. Listen to the people who make quantum computing systems to get a good idea of when hackers might use quantum algorithms to break encryption schemes. All others deal with second and third-hand knowledge.
To learn more
Estimates for when and if quantum computing may pose a cybersecurity threat vary significantly. Any study on the topic must be updated as technology evolves. The most complete analysis at the time of writing this book appears to be Mosca and Piani. 156
