Quantum cryptography definition
Quantum cryptography, also called quantum encryption, applies principles of quantum mechanics to encrypt messages in a way that it is never read by anyone outside of the intended recipient. It takes advantage of quantum’s multiple states, coupled with its "no change theory," which means it cannot be unknowingly interrupted.
Performing these tasks requires a quantum computer, which have the immense computing power to encrypt and decrypt data. A quantum computer could quickly crack current public-key cryptography.
Companies and governments around the world are in a quantum arms race, the race to build the first usable quantum computer. The technology promises to make some kinds of computing problems much, much easier to solve than with today’s classical computers.
One of those problems is breaking certain types of encryption, particularly the methods used in today’s public key infrastructure (PKI), which underlies practically all of today’s online communications. “I’m certainly scared of what can be the result of quantum computing,” says Michael Morris, CEO at Topcoder, a global network of 1.4 million developers. Topcoder is part of Wipro, a global consulting organization. It’s also working on finding solutions to quantum computing programming challenges.
“Instead of solving one problem at a time, with quantum computing we can solve thousands of problems at the same processing speed, with the same processing power,” Morris says. “Things that would take hundreds of days today could take just hours on a quantum computer.”
The commercial quantum computers available today are still far from being able to do that. “The theories have advanced farther than the hardware,” says William Hurley, IEEE senior member, founder and CEO of Austin-based quantum computing company Strangeworks. “However, we shouldn’t wait for the hardware to motivate the switch to post-quantum cryptography.”
Who knows what kind of technology isn’t available on the public market, or is operated in secret by foreign governments? “My fear is that we won’t know that the quantum computer capable of doing this even exists until it’s done,” says Topcoder’s Morris. “My fear is that it happens before we know it’s there.”
Asymmetric versus symmetric encryption
Here’s how encryption works on “traditional” computers: Binary digits (0's and 1's) are systematically sent from one place to another, and then deciphered with a symmetric (private) or asymmetric (public) key. Symmetric key ciphers like Advanced Encryption Standard (AES) use the same key for encrypting a message or file, while asymmetric ciphers like RSA use two linked keys — private and public. The public key is shared, but the private key is kept secret to decrypt the information.
The first target of encryption-breaking quantum computers will be the weakest link in the encryption ecosystem: asymmetric encryption. This is PKI, the RSA encryption standard. Emails, websites, financial transactions and pretty much everything is protected with asymmetric encryption.
The reason it’s popular is that anyone can encrypt a message by using the intended recipient’s public key, but only the recipient can decrypt it using the matching private key. The two-key approach relies on the principle that some kinds of mathematical processes are much easier to do than to undo. You can crack an egg, but putting it back together is a lot harder.
With symmetric encryption, messages are encrypted and decrypted using the same key. That makes symmetric encryption less suitable for public communication but significantly harder to break. “Quantum computers are unlikely to crack symmetric methods (AES, 3DES, etc.) but are likely to crack public methods, such as ECC and RSA,” says Bill Buchanan, professor in the School of Computing at Edinburgh Napier University in Scotland. “The internet has often overcome problems in cracking within an increase in key sizes, so I do expect a ramp up in key sizes to extend the shelf life for RSA and ECC.”
How to defend against quantum cryptography
Longer keys are the first line of defense against quantum encryption, and pretty much everybody is on board with that. In fact, the 1024-bit version of the RSA encryption standard is no longer regarded as safe by NIST, which recommends 2048 bits as a minimum. Longer keys make encryption slower and more costly, however, and the key length will have to increase substantially to stay ahead of quantum computers.
Another option is to use symmetric encryption for the messages themselves, then use asymmetric encryption just for the keys. This is the idea behind the Transport Layer Security (TLS) online standard, says Alan Woodward, a professor at the department of computing at the University of Surrey.
Many researchers are also looking at ways to create new kinds of encryption algorithms that would still allow public and private keys but be proof against quantum computers. For example, it’s easy to multiply two prime numbers together but very difficult to break a large number back up into its prime factors. Quantum computers can do it, and there are already known quantum techniques that could solve the factoring problem and many similar approaches, says Woodward.
However, there’s no known quantum method to crack lattice-based encryption, which uses cryptographic algorithms built around lattices. “Lattice cryptography is the one that looks to be the favorite at the moment, simply because it’s the most practical to implement,” he says.
The best solution could be a combination of post-quantum algorithms like lattice-based encryption for the initial communication to securely exchange keys, then using symmetric encryption for the main messages.
Can we really rely on lattice-based encryption or similar algorithms to be safe? “You can’t guarantee that your post-quantum algorithm will be secure against a future quantum computer that uses some unknown quantum algorithm,” says Brian La Cour, professor and research scientist at the University of Texas.
Quantum key distribution is unhackable, in theory
This is where the laws of quantum physics can come to the rescue. Quantum key distribution (QKD) is a method of sending encryption keys using some very peculiar behaviors of subatomic particles that is, in theory at least, completely unhackable. The land-based version of QKD is a system where photons are sent one at a time through a fiberoptic line. If anyone is eavesdropping, then, according to the principles of quantum physics, the polarization of the photons is affected, and the recipient can tell that the message isn’t secure.
China is furthest ahead with QKD, with dedicated pipes connecting Beijing, Shanghai, and other cities. There are also networks in Europe. In the United States, the first commercial QKD network went live this past fall. The Quantum Xchange, connecting New York City’s financial firms with its data centers in New Jersey, rents space on existing fiberoptic networks, then uses its own QKD senders and receivers to send the secure messages on behalf of clients. The company plans to expand to Boston and Washington, D.C. later in 2019.
However, the technology is extremely slow and requires expensive equipment to send and receive the individual photons. According to John Prisco, CEO and president of Quantum Xchange, a customer would need to buy a transmitter and a receiver, each of which costs in the neighborhood of $100,000. “It’s not too terribly different from other high-speed fiber optics communication equipment,” he says. “And the price will come down over time as more companies provide the hardware.”
The big breakthrough last year was that QKD systems no longer require special pipes, says Woodward. “Now it looks like they’ll be able to use existing fiber networks, so they don’t have to lay new fiber.”
Then there’s the satellite-based approach. This one uses the principle of entanglement, which Einstein called “spooky action at a distance” and refused to believe was real. Turns out, it is real, and China has had a quantum communication satellite up and working for a couple of years now.
Entanglement isn’t about instantaneous communications that break the speed of light speed limit, says Woodward. The way that it works is that two particles become entangled so that they have the same state, and then one of these particles is sent to someone else. When the recipient looks at the particle, it’s guaranteed to be the same state as its twin.
If one of those particles is changed, it doesn’t mean that the other particle instantly changes to match — it’s not a communication system. Plus, the state of the two entangled particles, while identical, is also random. “So, you can’t send a message,” says Woodward, “but you can send an encryption key, because what you really want in a key is a sequence of random digits.”
Now that the sender and the receiver both have the same random key, they can then use it to send messages using symmetric encryption over traditional channels. “China has leapfrogged everyone with this satellite,” says Woodward. “Everyone said it couldn’t be done, that passing through the atmosphere would drop it out of superposition, but the Chinese have been able to do it.” To receive the signals, companies would need to put something that looks like a telescope on their rooftops, he says, and then install some processing equipment.
Neither ground-based nor satellite-based quantum key distribution is practical for general use since both require very specialized and expensive equipment. It could, however, be useful for securing the most critical and sensitive communications.
The limits of quantum key distribution
If the integrity of the keys can be perfectly guaranteed by QKD, does that mean that unhackable communications are within our reach?
Not so fast.
“Most hackers, when they break into things, they hardly go head-on,” says Woodward. “They go around the side, and I suspect that's where you'll find problems with these implementations.” Today’s attackers, while they could, in theory, listen in to traffic over fiber optic lines, typically don’t do that.
There are far easier ways to read the messages, such as getting to the messages before they are encrypted or after they are decrypted or using man-in-the-middle attacks.
Plus, QKD requires the use of relays. Unless the sender and the recipient build a pipe that goes directly between their two offices, and the distance is short enough that the messages don’t degrade — about 60 miles or less with current technology — there will be plenty of opportunities for hackers. QKD networks will need repeaters when messages travel long distances. “You can imagine that those repeaters are going to become weak points,” says Woodward. “Someone could hack in and get the key.”
In addition, QKD networks will need to be able to route messages, and that means routers and hubs, each of which is also a potential point of vulnerability. “Physicists can say, this is absolutely secure,” says Woodward, “but there’s a danger in that, in thinking that just because you’re using QKD that you’re secure. Sure, the laws of physics apply, but there might be ways around them.”
Besides the security problems, it’s not realistic to expect that every internet user will have access to an QKD endpoint anywhere in the near future. That means, except for the most sensitive, high-value communications, better encryption algorithms are the way to go.
When will quantum cryptography become available?
So how much time do we have to get those algorithms in place? When are the quantum computers getting here? Nobody knows, says Woodward, since very significant engineering challenges still need to be overcome, and that could take years — or decades — to solve. The technology is still in its infancy, he says. “The quantum computer I play with over ihe Internet via IBM now has 20 qubits,” he says. “Google is talking about 50 qubits.”
Cracking today’s standard RSA encryption would take thousands of qubits. Adding those qubits isn’t easy because they’re so fragile. Plus, quantum computers today have extremely high error rates, requiring even more qubits for error correction. “I teach a class on quantum computing,” says University of Texas’s La Cour. “Last semester, we had access to one of IBM’s 16-qubit machines. I was intending to do some projects with it to show some cool things you could do with a quantum computer.”
That didn’t work out, he says. “The device was so noisy that if you did anything complicated enough to require 16 qubits, the result was pure garbage.”
Once that scalability problem is solved, we’ll be well on our way to having usable quantum computers, he says, but it’s impossible to put a time frame on it. “It’s like saying back in the 70s, if you can solve the magnetic confinement problem, how far away is fusion?”
La Cour guesses that we’re probably decades away from the point at which quantum computers can be used to break today’s RSA encryption. There’s plenty of time to upgrade to newer encryption algorithms--except for one thing.
“People are worried about things that are encrypted today staying secure several decades in the future,” La Cour says. Even if companies upgrade their encryption technology as new algorithms come along and go back and re-encrypt all the old files that they’ve stored, it’s impossible to know where all your old messages have gone.
“If emails go out and are intercepted, there’s now this warehouse of messages somewhere where someone is waiting for a quantum computer to come along and break them all,” he says. “People are really concerned about that.”
With Doug Drinkwater