Slashdot Mirror
Microsoft Creates a Quantum Computer-Proof Version of TLS Encryption Protocol
holy_calamity writes: When (or if) quantum computers become practical they will make existing forms of encryption useless. But now researchers at Microsoft say they have made a quantum-proof version of the TLS encryption protocol we could use to keep online data secure in the quantum computing era. It is based on a mathematical problem very difficult for both conventional and quantum computers to crack. That tougher math means data moved about 20 percent slower in comparisons with conventional TLS, but Microsoft says the design could be practical if properly tuned up for use in the real world.
When (or if) quantum computers become practical they will make existing forms of encryption useless.
Uh, no. It will only make breaking certain popular public-key cryptosystems practical. There are quantum-safe public-key systems, and most symmetric ones are also safe (at best, using a quantum computer with symmetric systems is equivalent to halving the key size — with an obvious way to compensate).
"Politicians and diapers must be changed often, and for the same reason."
I'm one of the authors of the research that was described in the article. Here's a link to our research paper for more information: https://eprint.iacr.org/2014/5...
What is that method? How does it differ from current encryption techniques? Why is that well suited to encrypting against quantum computers? How did you come to that conclusion, given that you don't have one to test against?
I'm one of the authors of the research that was discussed. Unfortunately, the MIT Technology Review article doesn't contain much detail. Here's a link to our research paper: https://eprint.iacr.org/2014/5....
The scheme uses a mathematical primitive called the "ring learning with errors (RLWE) problem". Rather than multiplying large prime numbers together like in RSA encryption or using points on a curve like in elliptic curve cryptography, here the mathematical operation is based on multiplying polynomials together, and then adding small random noise. An analog of this is solving systems of linear equations: if you took first year linear algebra, you might remember that if I give you a matrix A and a vector b, you can use Gaussian elimination (row reduction) to find a vector x such that Ax=b. But it turns out that if I add a small random noise vector e, and give you A and (Ax+e), it becomes much harder to find x. 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. (Here are some slides from a recent talk I gave about the research, which try to explain the problem in more detail: http://files.douglas.stebila.c...)
RLWE isn't our invention -- we build on existing research by Regev, Peikert, and others, and RLWE has been studied for a few years now. RSA and elliptic curve cryptography can be broken by quantum computers because they have a certain periodic structure that can be easily detected by a quantum computer using a quantum algorithm invented by Shor. But RLWE, and several related problems, don't seem to be susceptible to Shor's algorithm, nor to any of the other quantum algorithms that give an exponential speedup over normal classical computers. No one in the research community today knows if RLWE is hard for quantum computers, but right now people accept it as a promising candidate, and it is being explored for a variety of uses. 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 they going with something lattice based?
Hm.. An internet search finds this one: http://research.microsoft.com/...
The headline is "Post-quantum key exchange for the TLS protocol from the ring learning with errors problem", so it doesn't seem to have strictly to do with a lattice-based problem if it's the algorithm that was meant in the article above.
And this is an explanation: http://csrc.nist.gov/groups/ST...
I haven't understood the problem that deeply but when I do I will post it here.
I think this is the actual publication.
They're using ring learning with errors.
upon the advice of my lawyer, i have no sig at this time