Encryption vs. Quantum Computing
Prime factorization goes the way of the Dodo
Last week I wrote about end-to-end encryption and how public key exchange could be compromised. Today I want to follow up on the thread of threats to encryption with a discussion on Quantum Computing.
The Threat
Quantum computers will render current encryption obsolete. That means your email, your backups, your secure messages, your financial records, access to your money, access to your health history, etc - everything will be at risk. The internet will cease to function as we know it. The power grid, national defense apparatuses, spy satellites, GPS… everything will be under the control of whoever has the most powerful quantum computer.
What Are We Breaking?
At its core, encryption is about hard math problems. The goal is to pick a math problem that is very hard for an attacker to complete with only public information but very easy to complete with some additional private information. Currently, the math problem that is used is prime factorization.
Multiplying two prime numbers together is easy, but taking a product of two prime numbers and figuring out the prime factors is much harder. When we start talking about numbers with thousands of digits, determining the prime factors becomes virtually impossible with classical computing. This difficulty is what makes today’s encryption secure.
Quantum computing, when powerful enough, will be able to easily solve these currently very difficult math problems. Once that happens, we need a different set of math problems to base our encryption standards on.
How Bad Could It Be?
Breaking encryption is pretty freaking bad. Wired has a great article that lays out the whole scenario in The Quantum Apocalypse Is Coming. Be Very Afraid - https://www.wired.com/story/q-day-apocalypse-quantum-computers-encryption/. I encourage you to read it.
One of the passages that was most impactful was the discussion around national security threats.
Experts from one national security agency told me they break the resulting threats down into two broad areas: confidentiality and authentication. In other words, keeping secrets and controlling access to critical systems. Chris Demchak, a former US Army officer who is a professor of cybersecurity at the US Naval War College and spoke with me in a personal capacity, says that a Q-Day computer could let an adversary eavesdrop on classified military data in real time. “It would be very bad if they knew exactly where all of our submarines were,” Demchak says. “It would be very bad if they knew exactly what our satellites are looking at. And it would be very bad if they knew exactly how many missiles we had and their range.” The balance of geopolitical power in, say, the Taiwan Strait could quickly tilt.
It’s one thing to worry that your emails are being read by someone other than your intended recipient, it is another thing entirely if an adversary could capture one of our ballistic missile submarines or alter long distance communication in real time.
How do you conduct diplomacy if you can’t be sure you are talking to the world leader you think you’re talking to? How do militaries around the world know that the order to shoot or stand down actually came from their command structure and not from someone else? The scenarios are myriad, and the implications are dizzying.
If You Only Watch One
PBS Space Time on YouTube does a good job providing an overview where they describe quantum computing in general. They also have a good visual explanation for how current encryption works. If you only have time to watch one video then this is the one.
Start at the 3:04 mark if you only want to know about how current encryption uses prime factorization to secure our digital communication.
Harvest Now, Decrypt Later
Luckily for us all, there are people working on Quantum Resistant Encryption. In fact, National Institute of Standards and Technology (NIST) has selected multiple different algorithms for standardization https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms that are believed to be quantum secure.
That said, even if we land in an idillic future where all data is quantum secure, that does nothing for the encrypted data of today that is accessible for bad actors to store for later use. IBM Technology on YouTube has a great video on how breaking encryption in the future could compromise your encrypted-but-not-quantum-resistent data from today.
If your data is accessed by hackers and it's encrypted, no problem because they can't decrypt it, right? Sorry, no! Because another type of attack "harvest now, decrypt later" comes into play with the oncoming reality of cracking today's cryptography algorithms with tomorrow's quantum computers.
Conclusion
There is not much that the average consumer can do to protect their data of today from the quantum computer wielding bad actors of tomorrow. Frustratingly, we have to rely on governments, corporations, and international compacts to manage the future risks. While this may seem disheartening, I think it is also useful as a tool to shift your perspective about digital security.
Your digital security is a based on a multitude of factors - some within your control, and others outside of it. Your appetite for risk is on a spectrum and fluctuates depending on the task, the day of the week, and how much sleep you got last night, and the concept of “secure” and “not secure” is a reductionist fallacy. Broaden your view of digital security and you’ll see that while there are more and less secure ways to live, there is no guarantee. That doesn’t mean we should not try to eliminate risk when we can, but instead consider the risks and adopt strategies that are reasonable for your daily living.
Quantum computing is coming, and if we are lucky, it will take some time to arrive. But in the mean time, focus less on the impending doom of current encryption, and focus more on avoiding the enticement to click on malicious links in your email.
Stay safe out there.
Nitty Gritty: Shor’s Algorithm
For those of you who are interested in the algorithm that quantum computers would use to perform prime factorization, I encourage you to watch this explanation from minutephysics on YouTube. Be prepared for some maths!
Nitty Gritty: Quantum Resistant Encryption
Chalk Talk on YouTube does a great job explaining the basis for some future math problems that are hard even for quantum computers. Nothing you really need to know here, but I think the concept is very cool.