Post-quantum Crypto Talk by Peter Schwabe

In 2012, Mark Ketchen, researcher at IBM, stated about large quantum computers that they are "within reach" and estimated a timespan of 10 to 15 years until such computers can be built. It is not clear if Ketchen is right with this estimate, it is not even clear if a large quantum computer will ever be built. However, what is clear is that such a computer will be able to break all asymmetric cryptography in wide use today. More specifically, it will break in polynomial time systems that are based on factoring (like RSA) and systems based on the discrete logarithm (like DSA, and Diffie-Hellman key exchange), including their elliptic-curve variants. There are asymmetric cryptographic systems that, as far as we know, are not broken by quantum computers, so called "post-quantum cryptography". It is obvious that once large quantum computers exist, the world will need to switch to such post-quantum schemes. However, users who are concerned about long-term security, have to switch to post-quantum schemes for confidentiality already now: an attacker who records and stores key exchanges today can go back in a decade or two and use a quantum computer to attack them. In my talk I will give a brief overview of post-quantum crypto and then highlight what we can, and should, already do today to provide long-term security in cryptographic systems. In particular, I will present the "NewHope" key exchange, which is currently used in an experiment by Google and is one of the candidates to be considered for post-quantum key exchange in Tor.