Call it an abundance of caution. A Microsoft research project has upgraded the encryption protocol that secures the Web to resist attacks from quantum computers—machines that are expected to have stupendous power but have never been built.
Governments and computing giants like IBM, Microsoft, and Google are working on quantum computers because tapping subtle effects of quantum physics should let them solve in seconds some problems that a conventional machine couldn’t solve in billions of years (see “Microsoft’s Quantum Mechanics”). That might allow breakthroughs in areas such as medicine or energy. But such machines would also be able to easily break the encryption used to secure information online.
Intelligence organizations see that as a positive—the National Security Agency has an $80 million research program on quantum computing. But some researchers think we should be planning to upgrade our encryption so life can continue normally in a quantum-computing era. A team from Microsoft, chip maker NXP, and Queensland University of Technology have now shown how that might be done. They are testing a quantum-computer-proof version of the transport layer security protocol, TLS, that online banking sites and others use to encrypt online data.
Krysta Svore, who leads a research group working on software for quantum computers at Microsoft’s headquarters in Redmond, Washington, says this is more than just an academic exercise. “Given that scalable quantum computers are under development, it is crucial to prepare,” she says. It can take a decade or more for a new cryptographic algorithm—or “primitive”—to be properly tested out and widely deployed, she says. “There is an urgent need to determine other primitives now.”
When your bank or e-mail provider uses the TLS protocol to secure your data, today it typically uses the RSA algorithm (the letters stand for the last names of its three inventors). That creates pairs of digital security keys by multiplying together large prime numbers. One key is public and the other private; if you can figure out which primes were used to make the public key, you could also re-create the private one and unlock encrypted data. But conventional computers can’t quickly work out the primes used to make a key.
In 1994, mathematician Peter Shor proved that a quantum computer could easily find the primes behind a key. By using quantum states to exploit the mathematical structure of the problem, such a computer could effectively take a shortcut to the right answer. Shor’s algorithm can also be modified to crack a stronger alternative to RSA encryption, known as elliptic curve cryptography, which is becoming more common and is also used with TLS to secure online data.
The new quantum-proof version of TLS generates encryption keys using a different mathematical problem that’s believed to be beyond the practical reach of both conventional and quantum computers.
That system was tested by using it to encrypt data moving between two PCs, one taking the role of a Web browser and the other a Web server. The quantum-proof encryption protocol moved data 21 percent more slowly than a version using elliptic curve cryptography, as some websites do today, but the researchers consider that penalty a reasonable one to pay if their idea is polished up for real-world use.
Ari Juels, a professor at Cornell Tech and previously chief scientist at the security company RSA, says it makes sense to prepare our encryption for quantum computers now. Outdated encryption lingering in websites or software already causes security problems, even with the relatively slow progress made on encryption-beating attacks, he says.
However, right now it’s not certain that the math used in Microsoft’s quantum-proof software will always be intractable for either quantum or conventional computers, says Juels. Mathematicians and cryptographers haven’t studied them as intensely as they have RSA or the encryption used today. “We’ve no solid assurance,” he says.
Svore agrees but says the signs look good so far—people have looked for quantum shortcuts to the problem used in the new version of TLS for 15 years without success. Nonetheless, Microsoft’s researchers are studying possible alternative forms of quantum-proof encryption. Svore says she also wants to educate more computer scientists and programmers about how to write code for quantum computers so they are better prepared to use—or defend against—them when they do arrive. “We need to raise awareness on the power of quantum computing,” she says.