Post-quantum cryptography explained

by Christophe Petit

Introduction

Cryptography is the science and art of ensuring private and authenticated communications. In our highly digital society, we as individuals use it daily to ensure the security of our electronic banking transactions, emails, and of course our countries rely on cryptography for national security purposes. These examples have something in common, they use “asymmetric cryptography” (also known as “public key cryptography”, which is what we need when we want to establish a secure communication without necessarily being able to share secrets (or “keys”) in advance.

Now, when quantum computers will be built, public key cryptography will become completely insecure. This means private emails can be read, fraudulent banking transactions will become easy to make, and national security assets will be at risk.

From Mathematics to Cryptography

Modern cryptography relies on the difficulty of solving certain mathematical problems. More precisely, a typical “security proof” for a cryptographic protocol says that “if you can invalidate its security, then you can also solve a very hard mathematical problem”. Turning the logic around, this also means that “if you cannot solve the mathematical problem, you also cannot break the protocol”.

Some mathematical problems do seem very hard to solve. A typical example is factorization: one can efficiently multiply two numbers to obtain a third one, but the reverse operation, called factorization, is considered a very hard problem. The best human brains have tried for a very long time (one could argue for thousands of years), and recently they have been assisted by very powerful computers, yet factorization is still considered very hard. (Of course, recovering that 15=3*5 is easy, but in cryptography we use very large numbers).

If breaking your cryptographic scheme would require solving factoring, then you do have a pretty good confidence in its security.

Quantum computers and the threat they pose to cryptography

Quantum computers are machines that rely on the law of quantum mechanics to perform computation. They were theorised in the eighties by physicists like Richard Feynman. As far as we know, nobody has built one yet, but based on the theoretical model we have for them, we can already predict what sort of computations they will be good at performing.

As it turns out, quantum computers are very good at factoring. They are also very good at solving two other mathematical problems: the discrete logarithm problem and the elliptic curve discrete logarithm problem. Together with factorization, these problems underpin the security of most digital infrastructure today.

The day quantum computers are built, our existing security infrastructures are essentially dead.

Post-quantum cryptography

Post-quantum cryptography aims at developing new cryptographic schemes that will remain secure even after quantum computers are built.

This is a very important research topic at the moment, and it is encouraged by national security agencies like the NSA and GCHQ. The American National Institute for Standards and Technology is currently running a competition to develop the next generation of cryptographic algorithms, which will be resistant against quantum computers.

Why now?

Quantum computers do not really exist now, but leading academic and industrial organisations (including Microsoft, Google and IBM) are developing prototypes. What appeared as a theoretical long-term threat before is now perceived as a plausible one in the not too distant future.

Developing post-quantum cryptography will require a number of stages:

• identifying new mathematical problems that quantum computers will (hopefully) not be able to solve,
• building new protocols that rely on these schemes,
• implementing these protocols into all sort of devices that need security,
• updating our standards,
• ensuring a smooth transition and compatibility between existing and future infrastructures.

This will take a lot of time and effort. Even if quantum computers are only available as early as 2040, the time it will take to develop mature post-quantum cryptography infrastructures means that we have to start research now.

Here at Birmingham

The Birmingham Centre for Cyber Security and Privacy has a long standing expertise on security protocols and privacy issues, and the research we are doing here is key to preserving our security infrastructures in a post-quantum era.

The group is part of a European Research Consortium, FutureTPM, to develop the next generation of Trusted Platform Modules, an essential component which provides a cryptographic toolkit to guarantee the security of passwords, encrypted drives and software licenses. This project will ensure that future laptops and other hardware will remain secure in a post-quantum world.

We are also looking at applications such as railway systems and automotive security, developing lightweight cryptographic protocols that are not only post-quantum secure but also efficient enough to be used in safety critical environments.

We also have a strong expertise on the mathematics of both “classical” and post-quantum cryptography including, for example, isogeny-based cryptography, multivariate cryptography and group-based cryptography.
We are developing research projects together with UK industry and government to address the post-quantum cryptography challenge!

References:

D. Hart, D. Kim, G. Micheli, G. Perez, C. Petit and Y.Quek, 2018, ‘A practical cryptanalysis of WalnutDSA’, PKC 2018.

C. Petit and K. Lauter, ‘Hard and easy problems in supersingular isogeny graphs’, EUROCRYPT 2018.

R. Thomas, M. Ordean, T. Chothia and J. de Ruiter, ‘TRAKS: A universal key management scheme for ERTMS’, ACSAC 2017.

C. Petit, ‘Faster algorithms for isogeny problems using torsion point images’, ASIACRYPT 2017.

S. Galbraith, C. Petit and J. Velon, ‘Identification protocols and signature schemes based on supersingular isogeny problems’, ASIACRYPT 2017 [best paper award].