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 <[email protected]> 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 < > [email protected]> wrote: > > Date: Sat, 24 Jan 2015 13:07:29 -0800 > From: Tao Effect <[email protected]> > > 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 > [email protected] > https://moderncrypto.org/mailman/listinfo/messaging > >
_______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
