[Cryptography] Post Quantum Crypto

Kristian Gjøsteen kristian.gjosteen at math.ntnu.no
Thu Nov 12 06:32:13 EST 2015


12. nov. 2015 kl. 09.45 skrev Philipp Gühring <pg at futureware.at>:
> the scalability was demonstrated by D-Wave in the recent years

You should probably have noticed that D-Wave is building a machine that isn’t suitable for running Shor’s algorithm.

As far as I know, it is an open problem if the D-Wave machine is suitable for anything. See Scott Aaronson’s blog.

That is not to say that quantum computers won’t be a problem, but your premise is faulty, so your reasoning does not apply.

As for the question: How do we find a key exchange algorithm with the same properties as DH?

In general, you can turn any PKE with a reasonable message space into a two-move DH-like key exchange algorithm:

Alice generates a ephemeral key pair (ek, dk) and sends the public key ek to Bob.

Bob encrypts a random message x1 using Alice’s key ek to get c. Bob sends c to Alice.

Alice decrypts c to get x1.

Now Bob and Alice can both compute k = H(ek, c, x1).

Alice erases dk and x1. Bob erases x1.

If the cryptosystem is reasonably secure, then this is secure against passive adversaries. You make it secure against active adversaries using digital signatures, just like with DH.

The interesting question is: Can you do better than this, say like (H)MQV? Can you get more symmetry?

-- 
Kristian Gjøsteen



More information about the cryptography mailing list