NIST readies 'post-quantum' crypto competition

Your mission, should you choose to accept it, is to help the National Institute of Standards and Technology (NIST) defend cryptography against the onslaught of quantum computers.

It hasn't happened yet, but it's pretty widely agreed that quantum computers pose a significant risk to cryptography. All that's needed is either a quantum computer specifically built to implement Shor's algorithm (which sets out how to factor integers using quantum computers); or a truly quantum Turing machine that can be programmed to run whatever program it's asked to run.

However, it's generally agreed that such machines will exist, and that's why NIST would like to start moving early. So at the end of last week, it started the wheels rolling.

The agency has announced that it's planning a competition similar to that which gave the world the SHA-3 algorithm to create “quantum resistant” encryption.

In this paper, Report on Post-Quantum Cryptography, NIST's boffins note that a successful crypto-cracking quantum computer would mean that algorithms such as RSA, elliptic curve cryptography (for example, the elliptic curve digital signature algorithm and Diffie-Hellman elliptic curves), and finite field cryptography (like the digital signature algorithm) would no longer be secure.

It's not all doom and gloom, however: NIST reckons that AES can survive in a post-quantum world if the key size is large enough, and the SHA-2 and SHA-3 hash algorithms can survive with larger outputs.

NIST also wants to see increased work on new algorithm types, such as lattice-based cryptography, multivariate polynomial cryptography, code-based systems such as the 1978 McEliece scheme (which is still unbroken but needs very large keys), and new hash-based signatures.

NIST mathematician Dustin Moody says the competition "will be a long process involving public vetting of quantum-resistant algorithms … and we're not expecting to have just one winner. There are several systems in use that could be broken by a quantum computer—public-key encryption and digital signatures, to take two examples — and we will need different solutions for each of those systems." ®