Google Is Racing to Protect You From Quantum Hackers. Can It?
Post-quantum cryptography isn't going to be a walk in the park.
Encryption is basically complicated math.
The tools used to secure your private messages, online transactions, and basically everything else you do with a computer depend on complex math that is used to make sure data is only available to the people who are supposed to have access to it. There’s just one problem: Quantum computers don’t struggle with this math. That basic truth could have wide-ranging implications for the safety of your data.
Quantum computers don’t work the same way the device you’re using to read this article does. Instead of using a bunch of 1s or 0s to tell the computer what to do, quantum devices use “qubits” that can exist as both 1s and 0s at the same time. It’s efficient, smart, and (possibly) the future.
You know the really complicated math I was talking about? Turns out that it’s hard to perform that math on current devices, but it won’t be so hard on quantum devices, at least as far as we’re able to tell based on the quantum computing experiments that have been conducted to date. That’s bad news for encryption.
“One mathematical problem which quantum computers can solve much faster than classical ones — to our knowledge at the present time — is one at the heart of modern cryptography, namely factoring,” MIT professor Isaac Chuang, who teaches several classes in the illustrious university’s department of physics, tells Inverse.
Factoring is easy to do in one direction (9 times 13 equals 91) but harder to do in the other direction (what times what equals 91?). “This ‘one-way’ behavior is at the heart of the security of modern cryptography and authentication,” Chuang says. “However, quantum computers, remarkably, do not find factoring hard to solve, and thus this problem poses no one-way barrier for quantum machines.”
The Encryption of Today, Broken by Computers of Tomorrow
This means that the cryptography used today could be broken by the quantum computers of tomorrow. Encryption needs to advance — the math needs to become even more complex — to ensure that data considered secure by today’s standards won’t become vulnerable to attack once quantum computers become more available. So who’s going to protect us from these hackers from the future?
Google. That’s what it hopes, at least, which is why it’s experimenting with post-quantum cryptography in the beta version of its popular Chrome browser.
The company notes in its announcement that quantum devices aren’t yet ready for the big leagues. Yet many groups are working to make these devices a reality, including MIT and Google itself, among other tech companies and organizations.
“A hypothetical, future quantum computer would be able to retrospectively decrypt any internet communication that was recorded today, and many types of information need to remain confidential for decades,” writes Google software engineer Matt Braithwaite in a blog post. “Thus even the possibility of a future quantum computer is something that we should be thinking about today.”
Here’s how Google plans to start defending against those attacks:
Today we’re announcing an experiment in Chrome where a small fraction of connections between desktop Chrome and Google’s servers will use a post-quantum key-exchange algorithm in addition to the elliptic-curve key-exchange algorithm that would typically be used. By adding a post-quantum algorithm on top of the existing one, we are able to experiment without affecting user security. The post-quantum algorithm might turn out to be breakable even with today’s computers, in which case the elliptic-curve algorithm will still provide the best security that today’s technology can offer. Alternatively, if the post-quantum algorithm turns out to be secure then it’ll protect the connection even against a future, quantum computer.
Basically, that means Google will be using two encryption algorithms for some connections between the Chrome browser and its servers. The post-quantum encryption algorithm — which is based on the New Hope algorithm — will be tested to see if it can defend against theoretical quantum attacks. The other algorithm will be used as a fail-safe to ensure that any problems in the experimental protections don’t leave Google users vulnerable to attacks.
Google is careful to note that this is a short-term experiment, not a final solution. “We explicitly do not wish to make our selected post-quantum algorithm a de-facto standard,” Braithwaite writes. “To this end, we plan to discontinue this experiment within two years, hopefully by replacing it with something better.”
It’s not clear what that “something better” will look like — Google didn’t respond to Inverse’s multiple interview requests — but at least the company is working on it.
Even the National Security Agency is concerned by the development of quantum computers. “There is growing research in the area of quantum computing,” it announced in February, “And enough progress is being made that NSA must act now.” The agency will surely keep an eye on Google’s progress, both to learn from it and to figure out how it might be able to undermine those protections in the future.
That conflict is inherent to any advance in cybersecurity. As companies like Google work towards cryptography that can withstand attacks from quantum devices, researchers create quantum computers that can defeat advanced encryption algorithms. We’d be more secure if those devices were never created, but once it’s been unleashed, there’s no way to stuff the genie back in the bottle. (Or, in this case, to suddenly forget how to create functioning quantum devices.)
This is why it’s important to note that Google hasn’t solved the problem of post-quantum cryptography, it’s merely advanced it. Here’s what security expert and Tor Project board member Bruce Schneier writes about the experiment:
It’s certainly interesting that Google is thinking about this, and probably okay that it’s available in the Canary version of Chrome, but this algorithm is by no means ready for operational use. Secure public-key algorithms are very hard to create, and this one has not had nearly enough analysis to be trusted. Lattice-based public-key cryptosystems such as New Hope are particularly subtle — and we cryptographers are still learning a lot about how they can be broken.
Targets are important in cryptography, and Google has turned New Hope into a good one. Consider this an opportunity to advance our cryptographic knowledge, not an offer of a more-secure encryption option. And this is the right time for this area of research, before quantum computers make discrete-logarithm and factoring algorithms obsolete.
Chuang agrees.
“It’s certainly a race. Experimental realizations of small-scale quantum computers running the quantum factoring algorithm have been demonstrated,” he says. “Can large-scale quantum computers, capable of factoring large numbers, be realized, before post-quantum crypto becomes widespread? It’s important to keep in mind that new quantum algorithms also continue to be developed, and thus for post-quantum crypto to be secure, it’s also necessary to prove no quantum algorithm will ever be able to break it.” This is the cryptographic equivalent of an arms race.
Well, they never said that defending people against future hackers with access to theoretical devices that rely on quantum physics to operate was going to be easy.