Quantum Cryptography Demystified: How It Works in Plain Language

We’ve already covered the basics of quantum computing in our article on How Does Quantum Computing Work, so now it’s time to dive into one of its most publicized applications: quantum cryptography. Quantum cryptography holds both promises and threats for our current cryptographic infrastructure. The most obvious threat is quantum computers could decrypt data that’s been encrypted using many of our current systems. But it also holds the promise of secure communications channels for key distribution. Eventually, using quantum technology, it may even be possible to build entire encryption systems that are considered unbreakable.

Quantum Computing Decryption: Looming Crisis Or Another Y2K Blind Panic?

Asymmetric systems (like Public Key Infrastructure — PKI) use public/private key pairs that are mathematically generated. In the case of the widely-used RSA family of algorithms, the math is fairly complex. But it’s possible to crack if you can factor a very large number into its two prime number factors. If a key with enough bits is used, this is a nearly intractable problem for conventional computers, but quantum computers can use something called Shor’s algorithm to find the factors much more quickly. A rough estimate of the compute power needed is two qubits per bit length of the key. So a 1,024-bit key would require a quantum computer with 2,048 bits. Experts expect those to be possible within a decade, and some think sooner. Note that today 1,024-bit keys are already considered potentially unsafe, as they can be cracked given enough time on a large computer, but once a quantum computer can handle the task it will take very little time.

Much like the situation with the software migration required by Y2K, there are other encryption techniques that aren’t easily cracked with quantum computers. Examples of (non-quantum) encryption systems resistant to quantum attacks include McEliece and NTRUEncrypt. That means the problem is migrating the large number of systems and data already in place to newer ones. Also, like Y2K, it remains to be seen how real, and how widespread, the threat will be, as sufficiently large quantum computers will be expensive when they are finally available. That means they’re unlikely to get used for trying to hack information unless it’s considered extremely valuable. To run all of Shor’s algorithm, a quantum computer also needs to be paired with a powerful conventional computer, which will drive the cost of a key cracking system up even further.

Secure Communications Using Quantum Key Distribution

When you hear the term quantum cryptography, more often than not what is being referred to is Quantum Key Distribution (QKD). QKD doesn’t actually encrypt user data but makes it possible for users to securely distribute keys to each other, which can then be used for subsequent encrypted communication.

Whatever encryption system is used, there is almost always some type of private information that must be kept secret. For symmetric key systems, it is shared information in the form of a key, while in asymmetric systems each node has its own secret key while sharing a matching public key. In both cases, there are vulnerabilities when initializing communication. Symmetric key systems often rely on physical sharing of keys — some financial institutions use actual couriers with portable storage devices — to bootstrap. Or they may rely on a connection secured using an asymmetric system to share the encryption key needed for subsequent use. One reason for that is asymmetric systems like Public Key don’t require sending the secret (in this case private keys) over the channel, while symmetric systems are more efficient, and often more secure, for large volumes of data once keys have been exchanged.

But What About True Quantum Cryptography?

While harder than QKD, it will eventually be possible to encrypt data using quantum computing techniques that are particularly resistant to eavesdropping and various other forms of hacking. The most popular approach currently is the Kak protocol. Essentially it’s a quantum version of the well-known double-lock algorithm, which allows two users to securely exchange data without sharing any keys.

The double-lock protocol is remarkably simple. We’ll use common convention, and assume Alice and Bob want to exchange information, without it being modified by an eavesdropper, Eve. They also want to know if anyone is successfully eavesdropping on their communication channel. To do this they trade locks in a three-step process.

As the first step, Alice locks her data (in the digital case, encrypts it using a secret key), and sends it to Bob. Bob, in turn, adds his lock (encrypting Alice’s already encrypted data with his own secret key), and sends it back to Alice. Alice removes her lock and sends the result back to Bob. Bob can then remove his lock, and read the original data.

This all works really nicely with physical locks and keys, but it’s a little more complex when digital encryption is involved. For the protocol to work, the encryption processes have to be commutative (because the encryptions are applied in the order Alice, Bob, but then Alice needs to be able to remove her encryption before Bob removes his). An example of one possible, and popular, encryption, is multiplying by a large number. So far, so good. But now imagine that Eve is listening. As the data goes back and forth, she will be able to see the data multiplied by Alice’s key, the data multiplied by both keys, and the data multiplied by Bob’s key. From that, she can compute the supposedly secret keys of Alice and Bob.

Subhash Kak proposed using certain quantum rotations as a way to create a version of the double-lock protocol that couldn’t be eavesdropped. The rotations he proposed could be applied in either order, but any attempt to listen in by reading out intermediate data would result in corrupted data. Other researchers have continued to evolve the protocol with features to make it even more tamper-resistant, but unlike QKD, there aren’t any commercial implementations yet. While it is going to require much more powerful quantum computers to make true quantum-based encryption a reality, researchers are getting closer.

Last fall, a team of Chinese researchers successfully used quantum-entangled photons to create and share one-time pads between a satellite and a ground station in Austria. Encryption using one-time pads is provably secure as long as the pad is not compromised, is random, is used only once, and is longer than the data being transmitted. Quantum technology helps with the first three of these, but its performance is still quite slow. Still, the team was able to encrypt, transmit, and decrypt over 2GB of data using their quantum system.

In the meantime, quantum computers can do one simple task that’s important for encryption quite well: They can generate truly random numbers. It’s unlikely ultra-expensive quantum computers will be deployed just for that purpose, but once they’re in use, it will be a useful capability.

[Top Image Credit: iStock, Gauntman1, Museum of Science, Milan, Italy]

Continue reading

Hubble Examines 16 Psyche, the Asteroid Worth $10,000 Quadrillion

Researchers just finished an ultraviolet survey of 16 Psyche, the ultra-valuable asteroid NASA plans to visit in 2026.

Voyager 2 Probe Talks to Upgraded NASA Network After 8 Months of Silence

NASA just said "hello" to Voyager 2, and the probe said it back.

How Do SSDs Work?

Ever wondered how SSDs read and write data, or what determines their performance? Our tech explainer has you covered.

How L1 and L2 CPU Caches Work, and Why They’re an Essential Part of Modern Chips

Ever been curious how L1 and L2 cache work? We're glad you asked. Here, we deep dive into the structure and nature of one of computing's most fundamental designs and innovations.