Cryptography depends on the difficulty of guessing numbers. Before it can be used, any encrypted data must be decrypted using a digital key, and for our cryptographic systems to work those keys must be impractical to discover just by running through combinations until we get it right.

The size of the “key space” is part of how we ensure that this brute-force approach cannot decrypt our data, but another essential part of it is ensuring that our encryption algorithms are truly unpredictable, rather than pseudo random numbers where a clever decryption program can use predictable patterns of number generation to find results more quickly.

The quantum question

The two common cryptographic foundations for our standardized, ubiquitous PKI systems are RSA encryption and Elliptical Curve Cryptography (ECC).

● RSA depends on prime numbers. Large prime numbers are very difficult for traditional computing platforms to factor and thus are tremendously time-consuming as the computer has no option but to go through all combinations.

● Elliptic Curve Cryptography works by finding two points on an elliptic curve that intersect perfectly to ‘unlock’ an encrypted asset. Solving for two points in this curve is likewise difficult for traditional computers.

Enter quantum computers. Quantum computers take advantage of the nature of quantum physics to create an entirely new computing paradigm, unlike the traditional 0/1 gated computers that we have been using since the 1950s. Instead, they run on quantum bits (known as qubits), which can superpose and entangle themselves in order to perform multiple processes simultaneously. They are neither one, nor zero, but both at the same time!

It happens that due to the fundamentally different architecture of quantum computing, both RSA and ECC are orders of magnitude easier to crack for a quantum computer. Once these algorithms are compromised, the foundational security of all our digital systems will be invalid. Our modern systems of finance, commerce, communication, transportation, manufacturing, energy, government, and healthcare will, for all intents and purposes, cease to function. This eventual outcome is so severe that it is sometimes referred to as the “Quantum Apocalypse.”

Fortunately, we are in the early days of quantum computing and the computers that will break these algorithms are not with us today. They are years off, but not decades, so now is the time to change our basic PKI encryption to be quantum-resistant. A number of experts in the security industry, academia, and government are working on this problem, seeking to discover, define, and codify the best encryption algorithm or algorithms to replace RSA and ECC.

This is a high bar to get over. For an encryption algorithm to meet our needs it must be:

● Fast to encrypt for a traditional computer

● Fast to decrypt for a traditional computer using the private key

● Prohibitively difficult to decrypt in a brute force attack for either a quantum computer or a traditional computer

● Able to produce encrypted data that is efficient in size and not so “bloated” that it is impractical to use

● Compatible with the staggeringly complex array of hardware, software, and services that depend on our standards-based PKI systems today

● Well enough tested and understood that we can be confident it won’t prove highly vulnerable to future, unknown attacks

The essential timing of this task is well expressed in a concept called Mosca’s Inequality. This idea, proposed by the University of Waterloo’s Michele Mosca, can be expressed in a simple equation:

X + Y ≟ Z

X: the time we need to find one or more new algorithms to replace RSA and ECC

Y: the time we need to develop, QA, deploy, and adopt systems globally that will use the new algorithms

Z: the time until quantum computers will be powerful enough to break RSA and ECC

If X+Y is less than Z, then we are able to find and deploy new cryptography in time to obviate the quantum computing threat. If X+Y is greater than or equal to Z, then the Quantum Apocalypse occurs.

So, which will it be? That is an important question and not easily answered. However, there are measures we can take to make X and Y as small as possible. An effort led by the National Institute of Standards and Technology (NIST) seeks to gather and test possible candidate algorithms to help find and settle on algorithmic candidates. Technology vendors and large enterprises are paying great attention to crypto agility, which will decrease the time to deployment. And the industry is looking into increasing the length of the keys we use, which may extend the time before quantum computers can crack our systems.

All these efforts are developing in real time, so we will have to track them to see how they turn out. Either way, we need to be preparing today so that our digital lives keep functioning in a post-quantum world.