In the not-too-distant future—as little as a decade, perhaps, nobody knows exactly how long—the cryptography protecting your bank transactions, chat messages, and medical records from prying eyes is going to break spectacularly with the advent of quantum computing. On Tuesday, a US government agency named four replacement encryption schemes to head off this cryptopocalypse.

Some of the most widely used public-key encryption systems—including those using the RSA, Diffie-Hellman, and elliptic curve Diffie-Hellman algorithms—rely on mathematics to protect sensitive data. These mathematical problems include (1) factoring a key's large composite number (usually denoted as N) to derive its two factors (usually denoted as P and Q) and (2) computing the discrete logarithm that key is based on.

The security of these cryptosystems depends entirely on how difficult it is for classical computers to solve these problems. While it's easy to generate keys that can encrypt and decrypt data at will, it's impossible from a practical standpoint for an adversary to calculate the numbers that make them work.

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 researchers estimated that the sum of the computation time for both of the new records was about 4,000 core-years using Intel Xeon Gold 6130 CPUs (running at 2.1 GHz). Like previous records, these were accomplished using a complex algorithm called the Number Field Sieve, which can be used to perform both integer factoring and finite field discrete logarithms.

Quantum computing is still in the experimental phase, but the results have already made it clear it can solve the same mathematical problems instantaneously. Increasing the size of the keys won't help, either, since Shor's algorithm, a quantum-computing technique developed in 1994 by American mathematician Peter Shor, works orders of magnitude faster in solving integer factorization and discrete logarithmic problems. //

algorithms are vulnerable and have been cautioning the world to prepare for the day when all data that has been encrypted using them can be unscrambled. Chief among the proponents is the US Department of Commerce's National Institute of Standards and Technology (NIST), which is leading a drive for post-quantum cryptography (PQC).

On Tuesday, NIST said it selected four candidate PQC algorithms to replace those that are expected to be felled by quantum computing. They are: CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON, and SPHINCS+. //

pabs Seniorius Lurkius et Subscriptor

plectrum wrote:

jhodge wrote:
Is this intended to displace AES? AES is hardware accelerated pretty much everywhere, so replacing it will mean a whole lot of hardware is about to become obsolete. Not right away, but possibly by enough to shorten the lifecycle of equipment being sold now unless the transition period is long.

AES is symmetric crypto. These algorithms relate to public key aka asymmetric crypto. AES is not affected by factorisation or discrete logs being broken.

To elaborate on this comment a bit more. Symmetric encryption and cryptographic hashes will also be affected by quantum computers (see Grover's algorithm), but this can be generally* addressed by doubling the size of the key or digest, respectively.

The security of asymmetric encryption relies on the assumption that the discrete logarithm problem and integer factorization problem do not have polynomial-time solutions, and Shor's algorithm breaks that assumption.

• Technically there is still an issue with the birthday bound for block ciphers like AES with a small block size, but that can be addressed without requiring an entirely new approach.