[messaging] Do quantum attacks/algos also lead to compromise of PFS?

[Joseph Bonneau]

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.

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.

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.

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.


[1]
http://files.douglas.stebila.ca/files/research/presentations/20150108-RWC.pdf

On Sat, Jan 24, 2015 at 4:36 PM, Tao Effect <contact at taoeffect.com> wrote:

> Yes.  Shor's algorithm can compute finite field and elliptic curve
> discrete logs, so an attacker who saved a transcript of g^a, g^b over
> the wire today can, if/when quantum computers become available,
> compute a, b, and g^ab and retroactively decrypt the rest of the
> encrypted transcript.
>
>
> ... Shit.
>
> --
> Please do not email me anything that you are not comfortable also sharing with
> the NSA.
>
> On Jan 24, 2015, at 1:18 PM, Taylor R Campbell <
> campbell+moderncrypto at mumble.net> wrote:
>
>   Date: Sat, 24 Jan 2015 13:07:29 -0800
>   From: Tao Effect <contact at taoeffect.com>
>
>   So, I understand that QM algos can pretty much dismantle all
>   popular asymmetric encryption algos with enough q-bits, but I
>   haven't thought hard enough to see if they also can be used to
>   compromise communications that used DH to do PFS underneath the
>   initial handshake.
>
> Yes.  Shor's algorithm can compute finite field and elliptic curve
> discrete logs, so an attacker who saved a transcript of g^a, g^b over
> the wire today can, if/when quantum computers become available,
> compute a, b, and g^ab and retroactively decrypt the rest of the
> encrypted transcript.
>
>
>
> _______________________________________________
> Messaging mailing list
> Messaging at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/messaging
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://moderncrypto.org/mail-archive/messaging/attachments/20150124/d7f17565/attachment.html>