While quantum computing is still in its infancy, post-quantum cryptography is a field of growing interest for companies and research institutions. InfoQ has spoken with cryptography researcher Jean-Philippe Aumasson to understand where post-quantum crypto is headed.
InfoQ: Could you tell us a bit about your background and current endeavours?
Jean-Philippe Aumasson: I've been doing cryptography since 2006, when I started publishing research at international conferences. Since that I've done a PhD in crypto, worked in a big technology firm, did consulting and audit, and created start-ups. I'm currently co-founder and chief security officer of Taurus, now the leading European provider of crypto asset custody technology for banks. We're launching an exchange platform for tokenized securities, where investors can buy tokenized shares of companies, tokenized real estate, or NFTs, for example. I've also recently published a new book, Crypto Dictionary, which is an encyclopedia of crypto covering everything from the history of crypto to blockchain and modern protocols.
InfoQ: What does quantum computing imply for current cryptography techniques?
Aumasson: The quantum computing model works quite differently than the classical computing model we're used to, because the result of a computation is not the direct result of mathematical operations between inputs encoded as bits set to 0 or 1.
Instead, a quantum computer works by transforming a state composed of particles that can be seen as 0 and 1 at the same time, a physical phenomenon called superposition in the context of quantum mechanics. The type of transformation and the interference between particles then yield a result that sometimes can't be computed efficiently with a classical computer.
That's what we call a quantum speedup, when there exists a quantum algorithm solving some computational problem more efficiently than a classical computer. And the reason why cryptographers are worried is that there's an algorithm, called Shor's algorithm, that could break all the public-key cryptography used on internet. Namely, elliptic-curve cryptography and the [RSA algorithm](https://en.wikipedia.org/wiki/RSA_(cryptosystem)). It would do so by solving their underlying math problems, respectively the factoring problem (given a number N that is equal to P*Q, compute P and Q, which are large prime numbers), and the discrete logarithm problem.
If you'd like to learn more about this, I recommend the book Quantum Computing Since Democritus, by Scott Aaronson.
InfoQ: How real is the threat to current cryptographic systems from quantum computing? Is the possibility that quantum computers break current ciphers "just around the corner"? Do we need post-quantum cryptography today?
Aumasson: There is little chance that we'll see a quantum computer capable of breaking crypto in our lifetime, but the chance is not zero.
Post-quantum cryptography algorithms are alternative algorithms that could replace elliptic-curve cryptography and RSA, but be safe against quantum computers. Choosing to use these is thus a kind of insurance against the quantum computer risk.
However, in many cases today I believe that adopting these now is premature, because of the following reasons: we still don't have established standards, interoperability would be a problem, and we don't have enough mature, production-ready implementations.
InfoQ: How is the academic and research community involved in the process of building post-quantum crypto ciphers?
Aumasson: The heavy lifting is done by academic researchers. If you look at the algorithms submitted to NIST's post-quantum cryptography project, most of them are from teams of researchers from Europe or the US, with some of the most respected names in the field.
To be trusted, new algorithms need to have a solid analysis as well as mathematical proofs that breaking them is about as hard as some notoriously hard problem. It's not enough to craft a new algorithm with weird math and called it post-quantum just because you have no idea how to break it.
InfoQ: What major families of post-quantum crypto algorithms are being currently proposed or investigated?
Aumasson: There are essentially five classes of post-quantum algorithms: 1) Those based on hash functions, such as BLAKE2 or SHA-3; 2) those based on error-correcting codes, which like hash-based crypto were discovered in the 1970s; 3) those based on multivariate equations, or equations with unknown variables multiplied and added together; 4) those based on mathematical lattices 5) those based on isogenies, a pretty complex type of cryptography that involves elliptic curves, like a lot of the crypto we use today, but in such a way that it wouldn't be broken by quantum computers.
InfoQ: How do those post-quantum algorithm families compare with one another?
Aumasson: The post-quantum family that appears to be the most suitable for practical usage is lattice-based cryptography, the fourth family discussed above. These algorithms can be pretty fast, work with small keys, and we're confident about their security. The only downside is that they're usually incomprehensible unless you're a cryptographer specialized in this type of algorithms.
I love the hash-based algorithm (our first category), but these have severe limitations: you can only use them to create signatures (not to encrypt), and their keys are huge (dozens of kilobytes).