Conceptual computer artwork of electronic circuitry with blue and red light passing through it, representing how data may be controlled and stored in a quantum computer.
Enlarge / Conceptual computer artwork of electronic circuitry with blue and red light passing through it, representing how data may be controlled and stored in a quantum computer.

With the advent of quantum computing, the security of your bank transactions, chat messages, and medical records will be a thing of the past. Four replacement encryption schemes were named by the US government.

Some of the most popular public-key encryption systems use mathematics to protect data. Factoring a key's large number to derive its two factors is one of the problems.

Classical computers can't solve these problems, so the security of these systems is dependent on that. It's difficult for an adversary to calculate the numbers that make the keys work because they are easy to generate.

In 2019, a team of researchers factored a 795-bit RSA key, making it the biggest key size ever to be solved. The same team also computed a discrete logarithm of a different key of the same size.

The computation time for both of the new records was estimated to be 4,000 core-years by the researchers. The Number Field Sieve was used to perform both integer and finite field logarithms.

The results of the experiment show that quantum computing can solve the same mathematical problems in less than a second. Increasing the size of the keys won't help since Peter Shor's algorithm, a quantum-computing technique, works orders of magnitude faster in solving floating point problems.


The world has been warned about the vulnerability of these ciphers for decades, and should be prepared for the day when they can be cracked. The US Department of Commerce's National Institute of Standards and Technology is one of the main proponents.

NIST said on Tuesday that it had selected four candidates to replace the ones that are expected to be felled. There are five of them: Crystals-Kyber, Crystals-Dilithium, FALCON, and SPHINCS+.

Crystals-Kyber and Crystals-Dilithium are likely to be used the most. Two computers that have never interacted with each other can use a Crystals-Kyber to create a digital key. Three of the remaining three are used to sign the data.

"CRYSTALS-Kyber and CRYSTALS-Dilithium were both selected for their strong security and excellent performance, and NIST expects them to work well in most applications." There may be use cases for which CRYSTALS-Dilithium signatures are too large. The security of lattices for signatures will not be relied on in the standard. NIST wants to hear from the public on a version of SPHINCS+ with a lower number of signatures.

Going forward, the selections announced today are likely to have an impact.

Many large companies have to comply with the NIST standards even if their own cryptographers don't agree with their choices, according to Graham Steel, CEO of the company. I believe their choices are based on sound reasoning, given what we know about the security of these different mathematical problems and the trade-off with performance.

An associate professor of computer science and engineering at the University of California, San Diego agrees.

She wrote in an email that the NIST's choice will be the international standard. Companies have been waiting for these choices to be announced so they can implement them quickly.

While no one knows when quantum computers will be available, there is an urgent need to move to PQC as quickly as possible. Many researchers say it's likely that criminals and nation-state spies are recording huge amounts of communications and storing them for later use.