UK firm reaches final stages of the NIST quest for quantum-proof encryption algorithms

Post Quantum's Classic McEliece algorithm is the only remaining contender in the code-based category of algorithms designed to protect communications from attacks using quantum computers

London-based encryption specialist Post Quantum has reached the final stage of the NIST competition to find practical encryption standards capable of withstanding attacks by a quantum computer.

The US National Institute of Standards and Technology (NIST) launched its competition for Public-Key Post-Quantum Cryptographic Algorithms, in 2016 with the aim of arriving at quantum-safe standards by 2024. Successful candidates will enhance or replace the three paradigms considered most vulnerable to quantum attack: the digital signature standard FIPS 186-4 and the public key cryptography standards NIST SP 800-56A and NIST SP 800-56B.

Many of the current encryption algorithms use one-way functions to derive encryption/decryption key pairs, for example factorising very large integers into primes. This method is used by the general purpose RSA algorithms that form the basis of the secure internet protocols SSL and TLS. Elliptic curve cryptography, often preferred in IoT and mobile devices, also uses a one-way mathematical function. Unfortunately both are vulnerable to attack by quantum computers.

Last year NIST whittled down the original 69 candidates to 26, and in a third round announced last week reduced this number to 15: seven finalists "most likely to be ready for standardisation soon after the end of the third round", and eight ‘alternate candidates' "regarded as potential candidates for future standardisation". Candidates fall into three functional categories: Code-based, multivariate and lattice-based cryptography, which cover the variety of different use cases for which post quantum (PQ) encryption will be required. In addition, some candidates are suitable for public key exchange while others are better suited to digital signatures.

NIST third round candidates. Source: NIST

The only remaining candidate in the code-based category is Classic McEliece, which is a merger of Post Quantum's Never-The-Same Key Encapsulation Mechanism (NTS-KEM) and work done in the same area by a team led by Professor Daniel Bernstein of University of Illinois at Chicago. The joint candidate is based on the McEliece cryptosystem first proposed in the 1970s.

It works by injecting random error codes into the cyphertext. The error correction codes allow the recipient of the encrypted message to cut out the random noise added to the message when decrypting it, a facility not available to any eavesdropper intercepting the message.

"Classic McEliece has a somewhat unusual performance profile—it has a very large public key but the smallest ciphertexts of all competing KEMs [key-encapsulation mechanisms]. This is not a good fit for general use in internet protocols as they are currently specified, but in some applications, the very small ciphertext size could make Classic McEliece an appealing choice," NIST says, offering a possible use case as protecting VPNs.

Cheng said he was pleased to join forces with Bernstein's team, adding that the need for viable PQ encryption is urgent.

"The entire world needs to upgrade its encryption, and we last did that in 1978, when RSA came in. The stakes couldn't be higher with record levels of cyber-attack and heightened nation state activity - if China or Russia is the first to crack RSA then cyber Armageddon will begin," Cheng said.

"This isn't an academic exercise for us, we are already several years down the commercialisation path with real-world quantum-safe products for identity authentication and VPN. If you work for an organisation with intellectual property or critical data with a long shelf life, and you're working from home during lockdown, you should already be using a quantum-safe VPN."