What is the purpose of post-quantum cryptography?

Getting your Trinity Audio player ready...

What is the purpose of post-quantum cryptography? The basic, white bread answer would be “to keep all your secret stuff safe in the apparently imminent age of quantum computing, when standard cryptographic algorithms will be worth less than the paper on which you print them out.”

That’s it in a nutshell. Quantum computing, a development that’s set to massively increase the processing power and speed of computers as we know them, is, according to plenty of cryptographic experts, likely to pull on the thread of all known, pre-quantum cybersecurity, and keep pulling until all our carefully constructed cryptography is just a pile of numbers around our naked, exposed ankles.

Post-quantum cryptography is a collective term for an ever-growing group of methods that will allow quantum computing to exist while still protecting all our secrets (like bank account numbers, Netflix passwords etc, but also like access codes to nuclear or chemical laboratories, government buildings, national critical infrastructure systems and more). Without the ability to have and keep secrets, the world as we’ve come to know it would stop functioning in a big, big hurry.

Public-key encryption.

The problem as it exists is that a lot of our pre-quantum cybersecurity is based on public-key technology. What’s public-key? Essentially, it’s just a large numerical value that we use to encrypt our data. Imagine, say, ten Rubik cubes, linked together through the center. Every move you make to solve one cube makes the same move on every other cube, each of which have a different initial configuration.

It’s theoretically possible to solve all the puzzles together, but it a) takes quite the computational genius, and b) takes the computers we have a good deal of time, during which, a handful of cheerful alarms can be set off and security teams can come metaphorically running to intercept and throw out the potential hacker.

That’s great, so long as everyone’s using the same kind of computer, because it creates an unlikely but usefully level playing field.

The reason quantum computing is expected to be so fast is that it will be able to handle not only comparatively vast numbers of numbers simultaneously, but also vast numbers of computations simultaneously.

It’s likely to look at the intricately constructed mega-puzzle that is pe-quantum public-key encryption, smile indulgently, say “Cute,” solve the whole thing in the time it takes to say “Cute,” and go about its Wikileaky day, leaving everything that had been protected by public-key encryption exposed to the elements, the hackers, the blackmailers and the hostile nation states.

In theory…

At least, that’s the theory. We don’t technically know that quantum computing will be able to do that, and there’s a sense of Millennium Bug planning about the whole thing. But as with Millennium Bug planning, if the nightmare scenario of quantum computing does come true and leave everything using public-key encryption open and exposed, we’re going to feel mighty foolish for the half-hour or so before the world dissolves into chaos, anarchy, James Bond movie plots and possibly a primitive non-computer dystopia.

Incidentally, it’s true of course that public-key is only half the story of pre-quantum cryptography. There’s also a private-key element, which is usually individual-specific. But it’s widely considered that if quantum computers can crack public-key cryptography, then private-key is likely to be little more than an hors d’oeuvres of decryption, the easy sudoku before it moves on to the cryptic version.

Hence the need to be prepared for the era of quantum computing by deploying post-quantum cryptography. But what really is the purpose of post-quantum cryptography? What does it really mean, and perhaps more to the point, how do we really do it? If the giant number-cruncher is coming for all our precious secrets, how in the world do we protect them?

The Science.

Naturally enough, the way post-quantum cryptography works depends on understanding the purpose behind it, and the way the quantum computers are most likely to work.

Behind our folksy, easily digestible Rubik cube analogy, pre-quantum public-key cryptography tends to rely on three hard math problems: the integer factorization problem, the discrete logarithm problem, and the elliptic-curve discrete logarithm problem.

Feel free to look them up if you want to go beyond the Rubik cube analogy. Google will pretend to be your friend.

Post-quantum cryptography, perhaps perversely, will still most likely use public-key as its core approach, but will likely focus on any one or more of a handful of other techniques, given that quantum computers are expected to be able to solve the existing security problems in a handful of digital heartbeats, thanks to their ability to rapidly deploy Shor’s algorithm.

Potential methods of delivering post-quantum cryptography.

In brief, the front runner types of public-key algorithms that are most likely to deliver post-quantum cryptography are:

Lattice-based cryptography.

In particular, it’s worth keeping an eye on NTRU lattice-based cryptography, which has some significant testing behind it (with, admittedly, current computers), and has so far withstood years of attempts to crack it. That’s why NTRU lattice-based cryptography – or at least something called the Stehle–Steinfeld variant of NTRU – is being promoted for study as a potential standard of post-quantum cryptography by the Post Quantum Cryptography Study Group sponsored by the European Commission.

Hash-based cryptography.

Less fun than they sound, hash-based cryptographic algorithms have been around since the 1970s (and as such, we might think them useless in fighting 2020s or 2030s quantum computer intrusion). Actually though, their fundamental nature as alternatives to numerical digital signatures might have some skin in the post-quantum cryptography fight. As yet, they’re less supported for investigation than the likes of lattice-based cryptography, but there’s nothing fundamental that says evolutions of the likes of Lamport or Merkle signatures might not have a part to play in the post-quantum world.

Code-based cryptography.

Another contender favored by the European Commission, code-based cryptographic algorithms tend to rely on error-correcting codes. Ironically, one algorithm called the McEliece signature has withstood attempts to crack it for over 40 years by using random codes. Researchers that have tried to add more structure to the McEliece signature have invariably made it weaker and less stable, suggesting that useful randomness may have a part to play in post-quantum cryptography.

Supersingular elliptic curve isogeny cryptography.

While it might not exactly trip off the tongue, supersingular elliptic curve isogeny cryptography might well prove useful for forward secrecy (useful for avoiding the likes of mass surveillance by unfriendly governments). It’s also essentially a quantum-resistant version of an already widely-used version of public-key cryptography, the elliptic curve Diffie-Hellman key, so there are arguments in favor of it being a minimal-hassle upgrade.

Symmetric key quantum resistance.

Another alternative that more or less already exists is symmetric keys. Public-key cryptography is one thing, symmetric key cryptography another, but it’s another that already exists and is in use, and is expected to be quantum intrusion-resistant. That means there are many organizations suggesting we simply switch out public-key cryptography for symmetric key cryptography altogether.

Whether that will deliver a long-term solution remains as yet hard to judge – at least until we see fully-powered quantum computers, up, running, and on their game. But it’s certainly a theoretical way of deferring the problem while robust long-term post-quantum cryptographic algorithms are tested and developed in the field.

Multivariate cryptography.

One of the longer shots in the field right now, multivariate cryptography is exactly what it sounds like – cryptography based on the solving of multivariate equations. In its current form, it’s not been particularly effective in testing, and in principle, the idea of essentially making public-key cryptography just a little more complex probably won’t survive more than a couple of rounds of evolution of fully-powered quantum computers.

Still, the idea of doing more complex things with existing math appeals in the here and now, and if, for instance, the quantum cryptography apocalypse never arrives in the dramatic fashion that’s being forecast, multivariate cryptography might yet have a future as a heightened evolution of pre-quantum cybersecurity.

Whichever options withstand the power of quantum computing best will undoubtedly shape the direction of corporate, government and personal cybersecurity for at least a generation. Which options those turn out to be… we’ll have to wait and see. But ultimately, what is the purpose of post-quantum cryptography? It’s to make sure business continues as usual in a world of the casual supercomputer in your pocket, on your desk, and everywhere else.