How quantum computers will destroy and (maybe) save cryptography
- 02 August, 2018 22:25
More than a decade ago, I was giving an introductory presentation on quantum cryptography, as I had done many times before. I discussed the basic concepts of quantum physics, quantum computers, and quantum cryptography. I ended it with the promise that when quantum computing went mainstream that most of our current digital encryption secrets, which rely on hard-to-solve large prime-number equations, would be immediately revealed to the world.
Most secrets have been protected with some form of asymmetric encryption ever since Whitfield Diffie, Mark Hellman and Ralph Merkle publicly revealed the concept in 1976 in their seminal paper called New Directions in Cryptography. Think RSA, SSL, TLS and HTTPS. We’re talking most websites, digitally signed downloads, online financial transactions, your VPN, smartcards, and most wireless networks—all capable of being broken an instant.
Modern day secure communications rely on the fact that traditional digital computers cannot easily factor multi-factor equations involving large prime numbers. If a computer could do that, and quantum computers can, then it would be game over for any secrets encrypted by that protection.
It’s been theorized that most of the world’s major nation-states have been recording and storing much of the world’s encrypted network traffic for future decryption, just waiting for that day of reckoning to come. America will be able to read Russia’s and China’s top-secret communications and vice-versa. I wrote about this threat nearly eight years ago in a column.
Back to my talk many years ago: When I took questions at the end of the presentation, I was asked how long I thought it would be until quantum computers would be good enough to break all those secrets. I said “10 years. Most quantum physics experts think it’s only 10 years off.” As I walked off stage, industry luminary Bruce Schneier was walking on to follow me. He casually said to me as he walked on by without breaking stride, “How long have you been saying 10 years?”
I had probably been saying 10 years as the answer for at least 10 years. Bruce made me realize that none of us really knew the answer. The running joke in quantum physics circles is that quantum computers are always 10 years off.
How quantum computers work
Well, it’s not 10 years away anymore. According to Dr. Mark Jackson, theoretical physicist and scientific lead of business development at Cambridge Quantum Computing (CQC), we might be four to five years away, and in certain areas, limited commercial application—quantum chemistry, for example—might even be possible by the middle of 2021. What’s changed? Well, we now have many quantum computers, devices and software with enough sophistication to be useful without something called “error correction.”
Quantum computers can slay traditional digital computers because of how they work. Obviously, quantum computers rely on quantum mechanics (a subject too big and complex to cover here), but here is the advantage in a nutshell. A digital computer is binary. Each transistor or logic gate within its central processing unit (CPU) is capable of holding only one “state” at one time. It can either be “open” or “closed,” energized or not, be a “1” or a “0.” Hence, the word binary.
Quantum computers are based on something called quantum bits (qubits or qbits). Each qubit can be both states at the same time. Thus, one qubit is equivalent to two binary logic gates. Qubits get exponential as you add them. Two qubits can hold four simultaneous states, three qubits can hold eight simultaneous states, and so on.
A relatively modest quantum computer, then, could break all our previous public/private key pair secrets but would require effective error correction.
How and when quantum computers can break public key cryptography
We’ve been waiting a long time for quantum computing to become a reality. How long? At least since 1959 when Dr. Richard Feynman gave a lecture on it. Many quantum computing experts consider Dr. Peter Shor’s algorithm released in 1994 as being the real start of quantum computing.
Shor’s algorithm showed that quantum-based computing could rapidly decrypt most traditional forms of asymmetric encryption. More than two decades later, the promise (and threat) of quantum computing is nearly here--not just theoretical models, but multiple, working quantum computers, software, networks, and other communication devices.
One of the biggest challenges is getting qubits stable enough, long enough, without errors to be useful in serious computing. I use the non-technical terms “perfect” and “imperfect.” “To break public-key crypto, you’d indeed need thousands of ‘logical’ or ‘encoded’ qubits,” says Scott Aaronson, professor of computer science at the University of Texas at Austin, and director of its Quantum Information Center. “In the real world, because of the need for error-correction and the large overheads of existing fault-tolerance schemes, that could easily translate into millions of high-quality physical qubits.”
So where are we in the quantum computing lifecycle? According to Dr. Jackson, it would take a quantum computer with “only” 49 perfect qubits to outperform traditional binary computers. This is known as “quantum supremacy,” the seminal moment when quantum computers finally become more powerful than binary computers. It’s like IBM’s Deep Blue supercomputer beating world chess champion Gary Kasparov in 1997.
To crack most current public key encryption, it would take a quantum computer with at least 4,000 perfect qubits or many times that number if the qubits were imperfect. How close are we to a perfect 4,000 qubits? It depends on who you ask. Dr. Jackson is confident that we’ll have perfect 4,000-qubit quantum computers in the next five years. He has some evidence to support his claim, although we are nowhere near 4,000 perfect qubits.
In March 2018, Google announced an imperfect 72-qubit computer. Google’s current (publicly known) implementation makes a mistake about once every 200 calculations. When you’re doing billions of calculations a second, that error rate is an unusable disaster. Tens if not hundreds of billions of dollars are being spent around the world trying to make more stable quantum computers. Some say that the jump needed to get to 4,000-qubits is not as daunting as it once was.
Dr. Jackson, who is directly working with quantum computers says, “We have gone from nine to 72 qubits in just one year, so it’s not crazy at all that we could get 4,000 in another five [years]. Given that the US government finally got on board a few months ago, I think that’s now a conservative estimate.”
A greater number of knowledgeable sources still think we still don’t know when the quantum break of public key crypto will be. Schneier, who has written about quantum cryptography for a long time, when told of the 5-year claim, says “I don't buy it. No one knows about the unforeseen implementation problems.”
Dr. Aaronson was also skeptical. He wrote, “I’ll be astonished if that happens in five years. I can’t say it’s impossible, but I expect it to take quite a bit longer. I’ll be happy if, in three to five years, Google, IBM and others succeed in their current efforts to build noisy 70-qubit [quantum computers], and if they start to outperform classical computers at some (mostly artificial) tasks. Even if so, that’s still a long way from threatening public-key cryptography, because of the need for error-correction and the large overheads of existing fault-tolerance schemes, that could easily translate into [requiring] millions of high-quality physical qubits.”
Clearly, the jury is out on when quantum computers can break public-key crypto, but it is no longer the stuff of science fiction.
The National Security Agency (NSA) has not admitted that a quantum break is coming anytime soon, but they have said now is the time to start preparing. Specifically, in a related FAQ they wrote, “The NSA believes the time is right now right…. Consistent advances in quantum computing are being made.... The NSA is looking to all NSA vendors and operators to implement standards-based, quantum resistant cryptography to protect their data and communications.”
The emerging quantum computing industry
A growing number of companies and organizations—at least 44 known entities—are attempting to build quantum computer. The four globally prominent American companies are Google, IBM, Intel and Microsoft. A growing number of startups appear to be making progress, too. One of them, Dr. Jackson’s firm, CQC, is currently working with Google and IBM, among others.
Many of these companies are using similar technologies, a few are using their own methods, and a few others are using multiple methods at the same time in the race to be the winner. In the past few months, IBM and Google have established business development units showing that the focus is turning from the theoretical to the commercial.
The presence of so many competing companies spending billions of dollars is important. When billions of dollars across many companies and countries begins to flow, it’s a virtual certainty that the killer application is at hand. Think cloud computing as an example. For years, cloud was just a discredited buzzword, until it wasn’t. Same thing here.
Common quantum computing methods include superconducting, ion trapping and Majorana fermions. Superconducting and ion trapping are resulting in the greatest number of qubits right now. Superconducting requires very cold temperatures, close to absolute zero (nearly -460F or -273C), and the resulting qubits can be fragile and unstable.
The less mature Majorana fermion method being used by Microsoft is currently resulting in fewer qubits than the other methods but appears to be far less fragile. Dr. Jackson described the Majorana fermion method like tying braids of hair. They can be jostled about by the external environment, but their quantum state remains the same. Dr. Jackson says, “If we could get them to work at scale, they would be the clear winners. But we know less about them.”
The race is an international one, and it is widely believed the Chinese are very competitive, if not leading. As Dr. Jackson puts it, “They are heavily committed to it and have virtually no budget constraints.” The Chinese have even claimed to have performed quantum communications using a satellite, but there is some skepticism about this claim.
Cambridge Quantum Computing
CQC formed four years ago, when the focus on investment started to shift from university laboratories to private firms such as Microsoft, Google and IBM. They are active in the building of tools that enable quantum computers to become effective. They have recently designed and tested a novel device that works in the encryption space providing theoretically unhackable protection.
CQC has a proprietary quantum programming language and compiler, which they call “t|ket.”. Dr. Jackson says the language is somewhat C-like. The compiler is platform agnostic and works with all types of quantum computers based on many different platforms. It works to split computing effort between a traditional digital CPU and the new quantum processing unit, or QPU.
Dr. Jackson says that just like a traditional graphical processing unit, or GPU, handles the intensive graphical loads or a traditional numeric processor unit (NPU) handles the heavy mathematical loads for a regular digital computer, a QPU will handle the quantum stuff.
CQC’s compiler hands off the workloads that traditional digital computers do well to the regular CPU and hands off the specialized quantum computing needs to the QPU. Then the results are re-synthesized into a common output stream. “You won’t be needing to throw away your digital computers anytime soon. We still need them,” says Dr. Jackson. This is great news because I was wondering how we were going to carry around computers needing super cool temperatures.
Verifiably random number generators
CQC also builds hardware, including a “verifiably” quantum random number generator. Traditional digital computers have never been able to generate truly random numbers. It’s just impossible. Traditional computers are driven by very stable and naturally predictable quartz clocks that determine how fast and when a CPU can move information into and out of the CPU’s registers. Every clock tick is the same amount of time as before. This means the ultimate “source of truth” behind any traditional random number generator is predictable (i.e., not truly random).
Randomness in a traditional computer is really someone’s approximation of randomness. The lack of true randomness has been the downfall of many encryption solutions, which start with a randomly generated number. So, not only do we need truly random number generators, we also need to verify that they are truly random to completely trust them.
The National Institute of Standards & Technology (NIST) discussed the need for truly random number generators in the April 2018 issue of Nature magazine. Turns out quantum computing is also really good at generating verified random numbers. The earliest verifiable quantum random number generators were very big (the size of a building at 200 meters long) and fairly slow.
How random numbers can save cryptography in a post-quantum world
CQC has delivered a hardware-based, “pizza box” prototype unit called IronBridge, about the size of a VCR, that is expected to generate about 4 million random bits per second – enough to be commercially viable for powering encryption protocols that provide quantum security today. Wow! All of those numbers are verified as being truly random by the mathematics and physics theorem Bell’s Inequality.
Who cares about getting these types of truly random numbers? Well, anyone hoping to protect data and information after quantum computing breaks the traditional methods. This includes governments, technology firms and any company who need to protect their valuable intellectual property, research and information.
For nearly two decades, I used to say that the day of quantum reckoning was 10 years away with the same commitment given the ideas of flying cars and underwater cities. I and others didn’t really believe it was coming anytime soon.
Today, it’s closer than ever before. We have working quantum computers and the number of qubits is growing fast. It’s no longer a hype-driven pipe dream. Nation-states and companies big and small are making substantive progress against the few remaining problems. It’s still just a matter of time, but it’s time to start measuring the arrival of quantum computing in months or years instead of decades.