<div dir="ltr">There was a cool talk at Real World Crypto by Doug Stebila about doing post-quantum secure key exchange [1]. It was in the context of TLS but the ideas would apply equally to messaging.<div><br></div><div>The idea is to use a quantum-safe key exchange algorithm (in this case, Ring Learning With Errors or Ring-LWE) protected by normal signatures. So the idea is, Alice and Bob do the equivalent of a Diffie-Hellman key exchange in Ring-LWE, a lattice scheme in which is there is not a known quantum speedup better than general quantum search. However, for performance reasons they sign their shares with a conventional (non-quantum-safe) signature scheme. Because we all assume there quantum computers do not exist today, it is okay to protect the key exchange with a non-quantum-safe scheme since a future adversary can't do a middleperson attack retroactively, which I think is a cool insight.<div><br></div><div>For TLS, the slowdown is not so bad here over ECDSA (probably below 2x slowdown), although Doug cautioned that we don't know enough to do a key size comparison.</div><div><br></div><div>Another option for security is to perform both ECDH and Ring-LWE key exchanges and combine keys from there, giving you equivalent security to today but also a hedge against future quantum computers.</div><div><div><br></div><div><br><div>[1] <a href="http://files.douglas.stebila.ca/files/research/presentations/20150108-RWC.pdf" target="_blank">http://files.douglas.stebila.ca/files/research/presentations/20150108-RWC.pdf</a></div></div></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Jan 24, 2015 at 4:36 PM, Tao Effect <span dir="ltr"><<a href="mailto:contact@taoeffect.com" target="_blank">contact@taoeffect.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><span class=""><blockquote type="cite">Yes.  Shor's algorithm can compute finite field and elliptic curve<br>discrete logs, so an attacker who saved a transcript of g^a, g^b over<br>the wire today can, if/when quantum computers become available,<br>compute a, b, and g^ab and retroactively decrypt the rest of the<br>encrypted transcript.<br></blockquote><div><br></div></span><div>... Shit.</div><span class=""><div>
<br><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;display:inline!important;float:none">--</span><br style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;display:inline!important;float:none">Please do not email me anything that you are not comfortable also sharing</span><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;display:inline!important;float:none"> with the NSA.</span>
</div>
<br></span><span class=""><div><div>On Jan 24, 2015, at 1:18 PM, Taylor R Campbell <<a href="mailto:campbell+moderncrypto@mumble.net" target="_blank">campbell+moderncrypto@mumble.net</a>> wrote:</div><br><blockquote type="cite">   Date: Sat, 24 Jan 2015 13:07:29 -0800<br>   From: Tao Effect <<a href="mailto:contact@taoeffect.com" target="_blank">contact@taoeffect.com</a>><br><br>   So, I understand that QM algos can pretty much dismantle all<br>   popular asymmetric encryption algos with enough q-bits, but I<br>   haven't thought hard enough to see if they also can be used to<br>   compromise communications that used DH to do PFS underneath the<br>   initial handshake.<br><br>Yes.  Shor's algorithm can compute finite field and elliptic curve<br>discrete logs, so an attacker who saved a transcript of g^a, g^b over<br>the wire today can, if/when quantum computers become available,<br>compute a, b, and g^ab and retroactively decrypt the rest of the<br>encrypted transcript.<br></blockquote></div><br></span></div><br>_______________________________________________<br>
Messaging mailing list<br>
<a href="mailto:Messaging@moderncrypto.org">Messaging@moderncrypto.org</a><br>
<a href="https://moderncrypto.org/mailman/listinfo/messaging" target="_blank">https://moderncrypto.org/mailman/listinfo/messaging</a><br>
<br></blockquote></div><br></div>