For anyone who cares about Internet security and encryption, the advent of practical quantum computing looms like the Y2K bug in the 1990s, a countdown to an unpredictable event that might just break everything. The concern: hackers and intelligence agencies could use advanced quantum attacks to crack current encryption techniques and learn, well, anything they want. Now Google is starting the slow, hard work of preparing for that future, beginning with a web browser designed to keep your secrets even when they're attacked by a quantum computer more powerful than any the world has seen.
The search giant today revealed that it's been rolling out a new form of encryption in its Chrome browser that's designed to resist not just existing crypto-cracking methods, but also attacks that might take advantage of a future quantum computer that accelerates codebreaking techniques untold gajillions of times over. For now, it's only testing that new so-called "post-quantum" crypto in some single digit percentage of Chrome desktop installations, which will be updated so that they use the new encryption protocol when they connect to some Google services. But the experiment nonetheless represents the biggest real-world rollout ever of encryption that's resistant to quantum attacks, and a milestone in the security world's preparations to head off a potentially disastrous but still-distant quantum cryptopocalypse.
"The reason we’re doing this experiment is because the possibility that large quantum computers could be built in the future is not zero. We shouldn’t panic about it, but it could happen," says Google security engineer Adam Langley. Google's also considering the possibility that sophisticated eavesdroppers could record scrambled secrets now and then crack them with techniques developed years or even decades later. For many ubiquitous forms of crypto including many forms of the TLS or SSL encryption protecting our web browsing, that would mean "any information encrypted today could be decrypted in the future by a quantum computer," Langley says.
To stave off that secret-less future, Google is trying a two-year experiment: It's switching the TLS web encryption in a test portion of Chrome installations and Google services from elliptic curve cryptography---a common form of encryption that can be practically unbreakable for normal computers---to a protocol that bolsters elliptic curves by adding in a new type of encryption known as Ring Learning With Errors or Ring-LWE. Cryptographers are hesitantly betting that unlike elliptic curve crypto, the Ring-LWE technique will be resistant to quantum codebreaking.
No one can be sure yet of Ring-LWE's immunity to quantum cracking techniques, points out Johns Hopkins cryptography professor Matthew Green. But he argues it's still an important a step in the right direction. "It's much better to use an algorithm where we don't know of any quantum attacks versus the ones we know today to be broken by them," says Green. "This is research stuff, not what you’d expect to be out there in the world. But it’s interesting that Google's trying it anyway, even on a small percentage of browsers."
To understand how quantum computing threatens common cryptographic techniques, consider the mind-bending way a quantum computer works. Instead of the normal bits in a computer chip that store a "one" or a "zero" setting in the form of an electric current, a "quantum bit" or "qubit" is designed to exhibit the deeply weird, fundamentally different physical properties that occur in particles at a sub-atomic level: A qubit can exist in an indefinite state that's simultaneously a zero and a one at the same time---at least until it's observed, at which point it "collapses" into one of those states or the other.
That means two qubits can, together, exist in four states at once (00, 01, 10, and 11), three can exist in eight at time, and so on. So while a traditional computer might have to cycle through enormous numbers of possible keys, trying one at a time before it randomly guesses the key that decrypts an encrypted message, a quantum computer can try vast swathes of possible keys essentially simultaneously, collapsing those simultaneous states into one fixed state only after cracking a scrambled message. And that can mean the difference between deciphering a message in minutes or in millenia.
Quantum computing's cryptographic skeleton key isn't arriving particularly soon. An effective codebreaking quantum machine would have to have hundreds or thousands of qubits, cryptographers say. Cutting-edge quantum computers today have just a handful; one owned by IBM and made available for academic experimentation, for instance, has five qubits. (Quantum computing firm D-Wave, which has sold computers to Google, NASA, and Lockheed Martin, claims to sell quantum computers that boast more than a thousand qubits. But its machines are generally considered to have only some quantum properties and can't be used for true quantum codebreaking, says Google's Langley.)
"We sometimes joke that practical quantum computers are always 20 years in the future, and have been for a very long time," says Langley. But he nonetheless argues it's important to get the post-quantum ball rolling, the better to start the immense task of finding a quantum-resistant algorithm and getting the entire internet to switch over to it. "These are very early days. But the internet is vast. It takes a long time to deploy anything."
In fact, some corners of the security community are already facing up to the impending quantum risk---including that codebreaking behemoth, the NSA. Last year the NSA's Information Assurance Directorate, focused on securing information rather than collecting it, published an advisory suggesting that American agencies and companies begin the long transition to "quantum-resistant cryptography." The year before, Edward Snowden's leaks revealed that a different part of the NSA sought a crypto-cracking quantum computer as part of a $80 million "Penetrating Hard Targets" project. (Google's Langley dismisses the suggestion that the company's post-quantum crypto move is designed to stymie the NSA in particular. "We’re not focusing on particular adversaries," Langley says. "We believe Internet communications need to be secure.")
As magical as it may sound, quantum computing can't crack every kind of encryption. Its method of trying multiple keys simultaneously only works for certain, quantum-friendly algorithms that make it more likely the computer will spit out the correct answer rather than one of the many incorrect ones it's tried simultaneously. "You have to choreograph the problem so that paths to wrong answers cancel each other out and the paths to right answers reinforce each other," as MIT cryptography professor Scott Aaronson describes it. Quantum computing, he says, is "this bizarre new hammer, and people tried for 25 years to find the nail the hammer is good for. It’s a little bit of a miracle that it’s good for anything at all."
But the bad news for cryptography came in the mid-1990s, when computer scientists discovered that quantum computing is actually very useful for breaking several common crypto schemes. So-called "quantum Fourier transforms" made it theoretically possible to use quantum computing to crack the building blocks for all of the most common crypto protocols we use to exchange secrets over the Internet: Diffie-Helman, RSA and elliptic curve cryptography. The new Ring-LWE system Google's switching to, Aronson says, remains immune to that specific technique.
For now, Chrome's security team will combine Ring-LWE with elliptic curve crypto rather than replace it. That way, they say they can at least be sure the experimental system will remain as strong as its older elliptic curve crypto alone. They're also limiting the experiment to a small portion of Chrome users in part because the new crypto system adds about two kilobytes of data that must be sent in each direction when the browser makes a new HTTPS connection, which Google is concerned might cause data to be caught in some web filtering systems and firewalls.
Google's real goal with the experiment, Langley says, is to catalyze the research community to start looking for vulnerabilities in the Ring-LWE algorithm that quantum computing could exploit. "Ring Learning With Errors could turn out to be complete rubbish, and breaking it could be horribly easy even with existing computers, so we're using both [systems together] and mixing the answers so you’d have to break both," says Langley. "I hope in two years there will be new research and we can replace this with something better."
As experimental as Google's crypto switch may sound, Johns Hopkin's Matthew Green says it's an admirable move, and one that reassures him that the crypto world may just stay ahead of practical quantum computing advancements after all. "We’re on the edge of a cliff. Everything we use today is about to be broken, and we know it. The fact that we’re actually making progress in dealing with this is really heartening," he says. "It’s nice to know that some people aren’t waiting, they're doing something now."
