Introducing post-quantum cryptography

The upcoming post-quantum cryptography standardization, announced by NIST in 2016 and expected to take place in the next few years, aims at replacing currently used cryptographic primitives such as RSA, Diffie-Hellman key exchange and elliptic curve cryptography, which have been proved to be breakable by a quantum computer. It turns out that such cryptosystems, whose security is based on the presumed intractability of some number-theoretic problems, are not mathematically strong enough to resist quantum adversarial attacks. Indeed, despite being in their earliest days, quantum computers, due to the underlying quantum-mechanical properties, are capable of significantly reducing the computational hardness required to solve, e.g., integer factorization, which would take not even a lifetime on classical computers, thus outperforming the latter. The need of identifying new (and revisiting some old) quantum-safe algorithms now stems from the fact that, first, migrating to a whole new cryptographic infrastructure (i.e. anything that involves both the hardware and the software used by cryptographic services) will take a very long time, so the transition must be planned beforehand. Secondly, there is still a lot of research on proving which algorithms are resilient to quantum and what an attacker can do; possibly while large-scale quantum computers do not exist yet.

As part of a university project, this is my attempt ‒ which just wants to be an introduction; definitely not an expert on the topic, so take it with a grain of salt ‒ to give, hopefully, an intuition about the main post-quantum algorithms ‒ trying to not go too deep into math. You can find here the slides, and feel free to contact me for any mistake, suggestion, or insight you might have.