Post-Quantum Cryptography: What Is It Actually For?

Written By Charles Papin, Lead Product Engineer at Evertrust

Unless you have spent the last two years living with a remote tribe in Micronesia, chances are the subject of post-quantum cryptography has already reached your ears, sometimes in the form of the enigmatic acronym PQC. Indeed, it has become rather fashionable to sprinkle one's polite conversation with "PQC": it sounds sophisticated and up to date.

And yet, rarely has so much conceptual depth been condensed into so few letters. Each of the three words that make up the term deserves a moment of reflection.

Take "cryptography" first. Surely I just need to double my key sizes, since I already moved from RSA 1024 to RSA 2048. Why should this concern me?

Then "quantum". What does quantum physics have to do with my IT estate, which consists entirely of deterministic machines?

And finally "post". What comes after quantum? We do not even have a quantum computer worthy of the name, and we are already planning for what comes next?

Let us try to shed some light on the matter, so that at your next debate among distinguished company at a cybersecurity conference, you can confidently hold an informed position on a subject that will keep us busy for at least the next ten years.

"Cryptography"

As everyone knows, cryptography is the branch of mathematics, and by extension of computer science, dedicated to securing communications between people and between machines. In particular, it aims to provide the following guarantees, though the list is not exhaustive:

• Confidentiality: ensuring that anyone who is not the intended recipient of a message cannot understand its content;
• Integrity: ensuring that a message transmitted between two parties has not been altered in transit, or at the very least that any malicious modification of its content is immediately detected;
• Authentication: ensuring that the identity of the message's sender can be proven;
• Non-repudiation: ensuring that an individual who has performed an action cannot later deny responsibility for it.

These guarantees are absolutely fundamental to our digital ecosystems: they lie at the root of any notion of security in information systems. Without the mathematical machinery underpinning them, a malicious actor could easily circumvent them. With mathematical security proofs, which are not infallible but remain robust given the current state of our knowledge, such circumvention becomes much, much, much harder, if not outright impossible, given the sheer amount of resources it would require.

Naturally, the difficulty of breaking this security depends on the technology available to the attacker. Had we asked a thirteenth-century Chinese scholar to break a 20-bit RSA key, his abacus would not have allowed him to do so in any reasonable amount of time. Today, our classical computers can break keys of up to 829 bits, the current record, set in 2020, at the cost of a diabolical degree of parallel computation. But the problem is structured in such a way that the computational effort explodes as the key size grows, which means the defender always stays one step ahead of the attacker.

With a quantum computer, however, things look rather different.

"Quantum"

The beginning of the twentieth century saw the birth of one of the most beautiful physical theories the human mind has ever constructed, a theory whose relevance and accuracy we have kept confirming ever since, through experiments that its founders were unable to carry out in their own time.

In a few simple words, quantum theory says this: at extremely small scales, smaller than a billionth of a metre, matter behaves differently, following rules other than those governing the tangible world we inhabit. When you toss a ball into the air, an attentive observer can, without much difficulty, estimate where it will land and when it will hit the ground. Physics is deterministic, the laws of gravitation apply, and it would be surprising indeed if the ball suddenly decided to follow any trajectory other than a perfect parabola.

At the nanoscopic scale, by contrast, this notion of determinism no longer holds. The position, velocity, or energy of any given particle cannot be determined in advance. There is a certain probability that the particle is here, moving at this speed, and there is also a certain probability that it is somewhere else entirely, moving at a different speed. The particle therefore does not live in a single state defined by one position and one velocity, but in several states at once, each with a certain probability of being measured. This is known as the superposition of states.

Strange, certainly, but not the strangest part.

The measurement of a particle's position or velocity cannot be arbitrarily precise. At our scale, if you share your GPS location with a friend, they will know very precisely where you are and how fast you are moving. In the infinitely small, you cannot simultaneously know both the position and the velocity of an object with great precision. If you know very precisely how fast it is moving, you will only know roughly which region it occupies, and nothing more. If you know very precisely where it is, you will have a "large" uncertainty about its velocity. Understand that this is not a limitation of the measuring instrument: it is an intrinsic property of the elementary particle itself.

Strange again, but still not the strangest part.

That leaves the phenomenon of entanglement. Take a ball of modelling clay and divide it into two smaller balls. Place the first in a wooden box and the second in a metal box, then ship the wooden box to Rio de Janeiro and the metal box to Kuala Lumpur. Open the wooden box: you discover that the ball has taken on a particular shape during its eventful journey. Open the metal box at the same moment: the ball in Kuala Lumpur has taken on exactly the same shape, 20,000 km away. Obviously, things do not work this way at our scale. But where the rules of quantum physics apply, this type of behaviour is possible, and it has been proven by experiment, notably that of Alain Aspect, winner of the 2022 Nobel Prize in Physics. When two particles prepared in a certain entangled state are separated by a great distance, and the first is measured in a given state, the second will also be measured in that same state.

That, admittedly, was the strangest part.

What, you may ask, does any of this have to do with cryptography?

The new rules made possible by quantum physics, in particular the superposition of states, which we have discussed, and interference, which we have not, open up a whole new playground for mathematicians and computer scientists. Their toolbox is larger, and the rules of computation change.

And it is precisely thanks to this toolbox that Peter Shor discovered, in 1994, a quantum algorithm that breaks the security of RSA. Humanity was still far from imagining that a computer capable of exploiting the quantum properties of matter could ever be built, but the theoretical rules such properties allow already made it possible to devise ways of computing that had previously been beyond our reach.

If breaking RSA amounts to driving in a screw, classical algorithms give us nothing but a pair of tweezers, whereas quantum physics hands us an electric screwdriver. The defender always used to be one step ahead of the attacker, since it was enough to increase the key size to make the problem substantially harder. With the quantum algorithm, doubling the size of an RSA key has only a negligible effect on the attacker: the added complexity is polynomial, not exponential.

Now, the major development of recent years is that this electric screwdriver is becoming an industrial reality: we are now able to build quantum hardware capable of putting into practice the theory devised by Shor and his successors. The technical challenges are far from fully resolved, given that the factorisation record currently stands at a mere 21 bits. Yet the technology is advancing quickly, and given the political momentum and the amount of capital being invested, it is a fairly safe bet, if the regularly surveyed expert panels are to be believed, that a quantum computer worthy of the name will emerge within the next decade. And when it does, RSA will no longer secure anything at all.

It is also quite likely that we will only learn of it long after certain well-informed government agencies do: such a machine would obviously offer delightful decryption capabilities that one might prefer not to advertise right away.

"Post"-Quantum

"Post-quantum" should be understood as shorthand for "in an era when the attacker possesses a quantum computer". We will thus enter a post-quantum world on the day of the so-called "Q-Day", that is, the day a quantum computer powerful enough to break large RSA keys rolls off the production line of an American, Chinese, or, let us hope, European giant.

Post-quantum cryptography, then, is cryptography designed to remain resilient in such a world. It consists of classical algorithms running on classical computers, but built upon mathematical problems whose resolution, unlike that of RSA, is not accelerated by a quantum computer.

It is in this context that the algorithms resulting from the NIST competition were developed (ML-DSA, SLH-DSA, ML-KEM, and soon FN-DSA and HQC), as well as those adopted at the European level and standardised at ISO (FrodoKEM, Classic McEliece). These are "classical" algorithms, written in "classical" programming languages, running on "classical" processors, but resting on mathematical problems believed to be hard to solve efficiently, even on a quantum computer.

Until proven otherwise, of course.