An excerpt from “Chapter 1: Why Quantum Computing ” in the book Dancing with Qubits, Second Edition (Packt, 2024) by Robert S. Sutor
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.
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.
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. A physical qubit is the hardware implementation of the logical qubits…
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.
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.
Figure 1.16: It will take many physical qubits to make one logical qubit
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. 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.
Author Bio
Robert S. Sutor is a theoretical mathematician and veteran IT leader with 40+ years’ experience—including two decades at IBM Research—former Chief Quantum Advocate at Infleqtion, author of Dancing with Qubits, and an adjunct professor at the University at Buffalo.
About the Book
Dancing with Qubits (Second Edition) is a comprehensive, math-forward textbook that builds from classical-vs-quantum foundations (superposition, entanglement, interference) through circuits, hardware, and core algorithms (Grover, Deutsch–Jozsa, Simon, Shor), adds new chapters on NISQ algorithms and quantum machine learning with 100+ new exercises, and targets readers with strong interests in mathematics, physics, engineering, or computer science.
Buy the book here: https://packt.link/yNrXA