Cryptography at the crossroads Cryptography at the crossroads Cryptography at the crossroads

The crossroads is a common metaphor for a place where a person can be faced with a life-changing decision. Movies, songs and stories often have climactic supernatural dealings take place at a crossroads, usually in the dead of night. I'm not suggesting that we're here to make a Faustian bargain ourselves; I rather prefer Robert Frost's more benign, poetic take: “Two roads diverged in a wood and I—I took the one less traveled by.” I'd like to suggest that the cryptography industry is at a crossroads as it faces the threats posed by quantum computing and there are a couple of different paths forward.

On one side we have the classical approach. The cryptographic algorithms in use today, based on common mathematical problems like finding the prime factors of very large integers, will before long be vulnerable to attacks using large quantum computers. A number of candidate replacement algorithms based on different kinds of problems have been identified and tested, and some of these are already being deployed today. A lot of work still needs to be done to fix protocols like TLS that protect internet traffic as well as organizations’ internal encryptions, but IT architects and developers can start building project plans to get the work done. Advanced organizations are already budgeting and planning for this work. The end state goes by the name of Post-Quantum Cryptography, or PQC. In PQC, the fundamental approach of generating and exchanging cryptographic keys isn’t changing; it’s just being improved and strengthened to withstand quantum attacks.

On the other side of our crossroads is the intriguing and rapidly developing field of quantum cryptography. Not to be confused with PQC, quantum cryptography envisions a whole new approach—rebuilding cryptography from the ground up, using quantum physics as the foundation. The fundamental idea is that data encoded in a quantum state is inherently more secure than data protected by classical encryption methods. Quantum theory implies that any attempt to view such encoded data would necessarily change the data, rendering it useless—and allowing the data owner to know that it had been compromised.

Devil in the details
Different areas of quantum cryptography are currently being researched with promising results, although—as with quantum computing in general—significant problems still need to be overcome. To understand quantum cryptography, let’s meet three characters who have long played key roles in explanatory storytelling about cryptography: Alice and Bob, who wish to communicate securely, and Eve the eavesdropper, who wants to listen in on their conversation.

To begin, Alice and Bob would like to dispense with the notion of encryption keys altogether. Maybe, they think, they can communicate over a quantum channel without having to encrypt and decrypt their messages. This idea is Quantum Secure Direct Communication (QSDC). Using QSDC, Alice and Bob can encode the information they want to communicate into qubits—usually photons, tiny particles of light—and transmit the qubits to each other directly through space or via fiber-optic cable. They might add multiple qubits for error correction, and even entangle their qubits during the transmission process. The hope is that if Eve captures any qubits in transit and tries to read them, their quantum state would decohere and this would be known to Alice and Bob—so they would know that the transmission had been compromised, disconnect, and start again.

But Eve is clever, and she knows that when photons are transmitted, they don’t always go one at a time—sometimes two or more photons are sent at once. If she waits, she could capture an extra photon and keep it for herself, thus reading at least part of Alice’s message without Bob being any the wiser. Or, Eve could take an entangled photon Bob had sent to Alice and entangle it with her own photon. Alice would receive the photon without knowing that it was now entangled with Eve, and again the communication between Alice and Bob would be compromised.

In addition to these vulnerabilities, QSDC at the moment doesn’t scale up well enough to transmit large messages. The qubits are also susceptible to interference and noise in transit (the same noise that afflicts quantum computers), so the transmission range is fairly limited. The hardware needed to transmit and receive qubits is complicated and expensive. Despite its promise, Alice and Bob can’t fully use QSDC for now so they will look for a hybrid alternative that blends quantum with tried-and-true classical cryptography.

Enter Quantum Key Distribution (QKD). Alice and Bob will need to go back to using cryptographic keys to encode and decode their messages, but they don’t trust the classical key-generation methods based on finding prime factors, or other more difficult problems in pure mathematics. The promise of QKD is that Alice and Bob can use quantum physics to generate and transmit their cryptographic keys. There’s a lot of extremely complicated algebra behind QKD, but the basic premise is that Alice and Bob can use qubits to transmit the building blocks of key values to each other. And, if Eve happens to capture some of these qubits, Alice and Bob will notice the disruption in their key exchange and can just start over. Once Alice and Bob have successfully generated a key, they can then encode their messages and transmit them safely over any classical communication channel they choose.

QKD has been proven mathematically to be more secure than classical cryptography, as long as it adheres to the same basic assumption that Alice and Bob already know and trust each other. If they don’t, then both QKD and classical cryptography are vulnerable to a “man-in-the-middle” attack where Eve could impersonate either Alice or Bob and receive the communicated key. Defending against this is a whole other field of study known as “mistrustful quantum cryptography,” which is beyond the scope of this post.

Although QKD promises to be better than classical cryptography, including PQC, it also suffers from the same limitations as QSDC. Overall speed isn’t great, especially for large key values, and the transmission quality deteriorates with distance, so it doesn’t do well beyond a few hundred kilometres. And there’s expensive and complicated hardware required, making it difficult—for now—to implement commercially. Encouragingly, there are vendors—including here in Canada—building promising software solutions for QKD that will circumvent these limitations.

Path finder
By the way—I’ve written a lot in this and previous posts about cryptographic keys. How do we come up with these key values in the first place? Well, we need to rely on random numbers. And the funny thing about computers is that they’re anything but random. Random number generation is a whole separate field of computer science, and classical computers generally rely on software called pseudo-random number generators (PRNGs) which, if they’re complicated enough, generally do the trick for now. But the key word is pseudo—there is still an algorithm underlying the PRNG which could be cracked by a sufficiently powerful (read: quantum) attacker. So, quantum random number generators (QRNGs) are being developed; they use the inherently random nature of quantum particles to produce true random numbers. A few manufacturers are already starting to introduce QRNGs into their hardware but, like all quantum technology, it will take a bit more time to mature.

Back to Alice and Bob—they may have to wait a bit longer before they can fully commit to using quantum cryptographic techniques like QKD and QRNG. And when they do, it will still be a hybrid approach – using quantum methods to generate and transmit their keys and using classical methods to communicate securely using those keys. Unlike Robert Frost’s poetic persona, Alice and Bob don’t need to choose a single path forward. Instead, they’ll need to bring together the best of both worlds—classical and quantum encryption—to stay ahead of Eve and become fully secure.

As the famous baseball philosopher (and inadvertent quantum theorist) Yogi Berra once said: “When you come to a fork in the road, take it.”