The Best Security Against Quantum Attack Isn’t Quantum Key Distribution
Author: Perry Loveridge
Every day, billions of people connect to the internet. Some just read articles, watch shows, and look at pictures of anonymous cats. Others check bank statements, apply to jobs, make electronic payments, and share personal photos with their friends and family. Amazingly, we are all able to do these things, connecting billions of people to innumerable websites, relatively securely. When you log on to your favorite website, mitre.org for example, you can be quite safe in assuming that what you get is the real MITRE website and not a random server pretending to be mitre.org to steal information. You can also safely assume that you are the only one who can log on to your bank account and access all the information contained in it.
So how is it that we’re able to secure remote connections to billions of people all over the world? The short answer is well-placed cryptography. Most web traffic is encrypted using symmetric cryptography, through which the data you want to protect is encrypted using a given key (imagine locking a briefcase with a physical key) and can then only be decrypted using the same key. The encrypted information, what cryptographers call ciphertext, can safely be sent over the internet for all to see without worry of someone being able to read it.
Symmetric cryptography cannot be used for everything, though, because it requires that both sender and receiver have the same key. On top of that, each person needs a different key from everyone else (otherwise someone else would be able to unencrypt ciphertext meant for you). It would be impossible to pre-establish keys with every person and website you will ever want to connect to when you buy a new computer (or phone, or tablet, or smart watch, or smart fridge), not to mention that new websites are made every day.
We get around this problem by using something called asymmetric cryptography. Asymmetric cryptography is so named because the sender and the receiver don’t need to have the same key to successfully communicate. In fact, key exchange algorithms, a specific type of asymmetric cryptography that we focus on here, allow two people to come up with a shared key only known to them by sharing ciphertext that everyone can see. That is, we can send each other messages in a way that everyone else can also see those messages, and we can then combine those messages such that we share a secret key but nobody else can figure out what it is. The math behind this is extensive, so we won’t talk about it here, but the takeaway is that the two users can then use their shared key to initiate communication and then continue with symmetric algorithms.
But in 1994, a math professor at MIT named Peter Shor found an issue with asymmetric crypto: it can be broken using something called a quantum computer (QC). “How is that?” you may ask, or “What is that?” We’re not answering either of those questions here, but you can read about it here or here. For this article, just know that QCs break asymmetric crypto by quickly solving hard math problems that would take millions of years or longer to solve with a conventional computer.
This brings us to quantum key distribution (QKD), a method of secure key distribution that relies on the physical properties of photons to “guarantee” security. Photons are individual light particles that have quantum mechanical properties. For example, a photon can be in a superposition of two different states, meaning it is in both of those states at the same time. However, when you measure the photon it “collapses” to one of those two states (I’m not just simplifying; it really is that weird). When the photon collapses, the information in its original superposition is lost. This is the physical property that makes QKD secure.
In one version of QKD, one user, Alice, sends photons to another user, Bob, with whom she wants to communicate. The state of the photons Alice sends will eventually become a key shared by Alice and Bob. The trick is that if an eavesdropper, Eve, tries to look at the state of Alice’s photons to find out the key, Eve will alter the information in the photons just by looking at them. Alice and Bob will check if someone is eavesdropping after Bob receives all of Alice’s photons by checking some random sample of the photons. For example, Alice will say “my first photon should have been measured as A, the third as B, the seventh as B…” and so on, but if Eve was peeking, then Bob will find that some of these measurements don’t match. In this way, Alice and Bob can always detect if someone is eavesdropping in a way guaranteed by the laws of physics. QCs don’t impact this security at all because there is no hard math problem to solve (remember, we said that’s how they break modern key exchange).
But QKD has its own problems. For one, while modern key exchange works with normal internet infrastructure, QKD requires special equipment for sending and/or receiving single photons. The same goes for other applications, such as satellite communications. This special equipment is also difficult to make and still vulnerable to engineering difficulties. As one example, MITRE has a patent demonstrating how the single photon detection equipment used in many QKD experiments is vulnerable to “backflashes” where the photon detector (Bob) leaks his measurements back out of the detector where Eve could see them (MITRE has a long history of studying QKD). The protocol we described also does nothing to guarantee you’re establishing a key with the right person; Eve could pretend to be Alice from the beginning, and Bob would be none the wiser. The National Security Agency has even come out saying they currently do not recommend QKD for these reasons, and others.
So, what can be done as we get closer to crypto-breaking QCs? We stick with old methods, just done a little differently. QCs are only able to break modern asymmetric cryptography because of the specific math problems they’re based on. Cryptographers have known asymmetric crypto algorithms based on other hard math problems, and therefore aren’t broken by QCs, for decades. They are slower, or need bigger keys, or their messages take longer to send, but most computers can easily handle them (without needing new equipment), and they get faster every year. The National Institute of Standards and Technology (NIST) has been reviewing submission for new “Post-Quantum” algorithms since 2016 and plans to have finalists decided by 2022. QKD may one day serve a valuable purpose protecting information requiring extra caution that justifies the cost (some are already using it), but post-quantum algorithms are the real solution for now, and, for most of us, likely forever.
Perry Loveridge is a Space Systems Engineer in the Quantum Technology group at MITRE. He has a bachelor’s degree in Engineering Physics from Cornell University and is pursuing an MS in Computer Science at the Georgia Institute of Technology. Currently, his biggest interests are in post-quantum cryptography and quantum algorithms.
© 2021 The MITRE Corporation. All rights reserved. Approved for public release. Distribution unlimited. Case number 21-0123
MITRE’s mission-driven teams are dedicated to solving problems for a safer world. Through our public-private partnerships and federally funded R&D centers, we work across government and in partnership with industry to tackle challenges to the safety, stability, and well-being of our nation. Learn more about MITRE.