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?
Almost all widely used encryption systems rely on keys — typically large, random, numbers that can be used to encrypt or decrypt data. Current encryption packages are most often built using either symmetric or asymmetric keys — many using asymmetric keys to transmit a shared, symmetric key for doing the actual data encryption. Both types of keys would be vulnerable to hacking using quantum computers. Symmetric systems rely on a shared secret key, and cracking the key requires about double the computing work for each additional bit. With that kind of scaling, it’s been possible to keep using larger keys as computers get more powerful. However, by implementing Grover’s algorithm, quantum computers can essentially cut the key length in half — a nearly inconceivable reduction in the amount of time required to crack a key. The good news is that now that we’re aware of the challenge, doubling the key lengths in use should be an excellent defense.
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.
While QKD isn’t in widespread use, it has been in commercial use in Europe since 2007, and in the US since 2010. For high-value transactions like inter-bank communication and election result transmission, the benefits of QKD are sometimes worth the cost. Another impediment to the wider adoption of QKD is that current systems aren’t interoperable between different vendors. Fortunately, that’s starting to change. In a research effort directed at finding ways to secure the power grid, teams at Oak Ridge and Los Alamos National Laboratories have demonstrated the first successful use of QKD between different implementations. The University of Bristol has also just published research on doing something similar to help secure multi-vendor 5G wireless networks.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.
In Kak’s protocol, Alice and Bob use encryption functions UA and UB as proxies for the physical locks of a traditional two-lock protocol.
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.
0 comments:
Post a Comment