Slashdot Mirror

← Back to Stories (view on slashdot.org)

Microsoft Creates a Quantum Computer-Proof Version of TLS Encryption Protocol

Posted by samzenpus on from the protect-ya-neck dept.

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.

13 of 128 comments (clear)

  1. 20% slowdown isn't that bad... by XxtraLarGe · · Score: 4, Insightful

    Especially if the choice is between your data being secure or not.

    --
    Taking guns away from the 99% gives the 1% 100% of the power.
    1. Re: 20% slowdown isn't that bad... by Krishnoid · · Score: 4, Insightful

      I bet the NSA is going, "Just charge it to the taxpayers."

  2. very difficult problems by davidwr · · Score: 5, Funny

    It is based on a mathematical problem very difficult for both conventional and quantum computers to crack.

    Ah, that would be my federal tax return.

    --
    Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
  3. Well, I did read TFA... by laughingcoyote · · Score: 4, Insightful

    This article is about a waste of time.

    Microsoft has developed an encryption method resistant to quantum computers, it claims. Alright? 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? Are we just supposed to believe Microsoft when they say "Trust us, this is secure"?

    --
    To fight the war on terror, stop being afraid.
    1. Re:Well, I did read TFA... by ljw1004 · · Score: 4, Insightful

      This article is about a waste of time. Microsoft has developed an encryption method resistant to quantum computers, it claims. Alright? 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? Are we just supposed to believe Microsoft when they say "Trust us, this is secure"?

      No of course not. You're meant to read this article, understand that it's an example of bad science journalism, and because of your innate geekiness and intellectual curiosity you should use the power of Google or Bing to find the scientific research in question:

      http://csrc.nist.gov/groups/ST...

    2. Re:Well, I did read TFA... by stebilad · · Score: 5, Informative

      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.

  4. QCs will _not_ make existing crypto useless by Prune · · Score: 4, Informative

    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."
  5. Re:haha by Anonymous Coward · · Score: 3, Funny

    I think I deciphered the message hidden within your comment, but as a woman I'm afraid that I cannot be of any help to you.

    Your encrypted message was:

    hahah hahahah hahahah hahahah ... hahahah hahahahahaha hahaha

    Decrypted, it reads:

    HELP. VERY THIRSTY. SEND JUICY PENISES. OUT.

    Maybe somebody else here could be of assistance?

  6. Link to the research paper by stebilad · · Score: 5, Informative

    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...

    1. Re:Link to the research paper by stebilad · · Score: 4, Interesting

      True, authentication still relies on existing certificate authorities. Authentication has to come from some pre-existing trust relationship, and CAs -- for all their problems -- do make the web work. In TLS in general, including our post-quantum work, you only have to trust the CA up to when you start your communication (they could impersonate the server to you). Assuming you actually did connect to the right server, then after the communication is done the CA is not able to read the encrypted data you sent or received. So yes, there's trust in a middleman, but only for a limited time. Hopefully orthogonal technologies, like Certificate Transparency and DANE, will reduce the reliance on CAs.

  7. Re:What algorithm/primitive? by datokrat · · Score: 4, Informative

    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.

  8. Re:There is no there there by compro01 · · Score: 4, Informative

    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
  9. Re:One time pad by DamnStupidElf · · Score: 4, Interesting

    That said, you could probably use a synchronized random number generator as the shared pad data. The other side would only be able to decrypt messages for as long as they buffer the random number data; after which the message is lost to everyone for eternity. This could work for a TLS session where messages are exchanged with only a couple minutes (or preferably seconds) delay so that the buffer does not need to be very big.

    That's roughly the definition of a stream cipher (e.g. RC4 or a block cipher in Counter mode). Only a cryptographically secure random number generator works, which is why such a thing is called a stream cipher and not just a "pseudo-random one time pad". In any case it's not a true one time pad because the entropy of the stream of pseudorandom data is limited to the entropy of the internal state of the cipher, and further limited by the entropy of the key. That means stream ciphers can be broken given only the ciphertext, as opposed to using a one time pad. Stream ciphers also share the same weakness as one time pads; reusing the same stream cipher key is just as bad as reusing a one time pad (virtually automatic recovery of all plaintexts encrypted with the same pad/stream).