Microsoft Tests Quantum Computer-Proof Web Encryption

Microsoft says it has taken the first steps toward a new form of web encryption designed to be able to fend off attacks from quantum computers, which are expected to be able to crack the encryption techniques in wide use today.

Although quantum computers, which make use of the phenomena of quantum mechanics to perform operations on data, don’t currently exist, experts have demonstrated that such systems would have little difficulty solving the mathematical problems, or “primitives”, upon which current web security is based.

And given that organisations including Google, IBM, the NSA and Microsoft itself are investing heavily in quantum computer development, this danger is unlikely to remain theoretical for long, Microsoft said.

‘Urgent need’

“There is an urgent need to determine other primitives now,” Krysta Svore, head of Microsoft’s quantum computer research group, told the MIT Technology Review.

Websites that use the widespread SSL/TLS encryption standard currently tend to make use of the RSA algorithm, which mathematician Peter Shor showed in 1994 could be easily broken by a quantum computer. Shor’s approach could also be used to crack elliptic curve cryptography, another primitive increasingly used with SSL/TLS.

The research carried out by the team of researchers from Microsoft, chip maker NXP and Queensland University of Technology (QUT) focuses on building a protocol using one of the primitives currently thought to be difficult for quantum computers to solve, called the “ring learning with errors” (RLWE) problem.

The team said it has built an early version of such a system and tested it, finding that it performed 21 percent more slowly than a version using elliptic curve cryptography, according to its paper.

Practical application

“Our work is about actually using RLWE, seeing how to design a key exchange protocol that’s suitable for use in SSL/TLS and then implementing and testing it,” stated Douglas Stebila, senior lecturer at QUT, one of the authors of the research.

Rather than multiplying large prime numbers together as in RSA encryption, or using points on a curve as in elliptic curve cryptography, here the mathematical operation is based un multiplying polynomials together, then adding some random noise, Stebila said.

The result makes it “much harder” to crack, he said.

Critics say RLWE hasn’t been studied intensively enough to prove that it would be any more secure against quantum computers than the techniques currently in use, but the primitive seems to be one of the better bets currently out there, according to Stebila.

“Right now people accept it as a promising candidate, and it is being explored for a variety of uses,” he stated. “If after years of cryptanalytic research no one manages to break it, then it may achieve the corresponding levels of confidence that the research community has in the difficulty of currently accepted problems, like factoring or elliptic curve discrete log.”

Are you a security pro? Try our quiz!