Quest to find new quantum-resistant standards
A competition to develop encryption tools which could one day protect against quantum computers has revealed its shortlist of candidates.
The National Institute of Standards and Technology (NIST) announced that 26 potential algorithms have advanced to the post-quantum cryptography ‘semi-finals’, narrowing the field of schemes that could protect sensitive data stored on mainstream PCs, servers, and smartphones.
Although still in the arena of prototypes, quantum computers have the potential to render most current modes of encryption obsolete.
The security of schemes such as RSA and Diffie-Hellman is undermined by the difficulty of factoring the products of two large prime numbers using conventional computers.
The mathematics of elliptic curves, which forms the basis of one-way functions used in other modern crypto schemes, would likewise be vulnerable to attack from future quantum computers.
This threat remains at least 10 years away, but work in developing quantum-resistant cryptography is already well advanced.
NIST opened its competition in December 2016, receiving 82 submissions, out of which 69 met minimum acceptance criteria – this has been narrowed down to a shortlist of 26, following a year-long review process.
“These 26 algorithms are the ones we are considering for potential standardization, and for the next 12 months we are requesting that the cryptography community focus on analyzing their performance,” said NIST mathematician Dustin Moody. “We want to get better data on how they will perform in the real world.”
Of this number, 17 candidates cover public-key encryption and key-establishment algorithms, while a further nine offer a way forward for digital signatures.
Moody told The Daily Swig that NIST was looking to take forward two to three approaches in each category, so there may be as many as five or six ‘winners’ when the competition eventually ends. At minimum, two schemes will be implemented.
The selected algorithms will “supplement or replace three standards considered to be most vulnerable to a quantum attack”.
The three at-risk approaches are: FIPS 186-4 (which specifies how to use digital signatures), NIST SP 800-56A, and NIST SP 800-56B (both of which specify how to establish the keys used in public-key cryptography).
Quantum leap
The second round will involve evaluating the submissions’ performance on a wide variety of systems and devices, from mainframes and smartphones to devices with limited computing power, such as smart cards and IoT kit.
“A wide range of mathematical ideas are represented by these algorithms,” Moody explained.
“Most fall into three large families – lattice, code-based, multivariate – together with a few miscellaneous types. That’s to hedge against the possibility that if someone breaks one, we could still use another.”
Lattice, code-based, and multivariate systems are thought to be resistant to the type of brute force number-crunching attack that could be run using a quantum computer.
By contrast current encryption approaches relying on either integer factorization or the elliptic-curve discrete logarithm problem, the basis of most of the public key crypto tech used today, are not resistant.
A sufficiently strong (and as yet hypothetical) quantum computer would be able to run one of a class of algorithms designed with quantum computers in mind to factor the products of prime numbers in short time.
That would break the whole foundations of schemes such as RSA and simply increasing the key length, as is the current approach, to make keys resistant to brute force attacks from the most powerful conventional computers, would no longer do the trick.
Small steps
In practice, even leading vendors in the nascent field such as IBM and D-Wave Systems have only advanced as far as developing prototype quantum computing devices, way below what would be needed to do integer factorization, a technique that would slice right through public key cryptographic systems.
IBM currently offers 5-qubit and 16-qubit quantum computing systems available through the cloud on the IBM Q Experience.
The system, first established in May 2016 and periodically upgraded since, is built on IBM’s prototype quantum processors.
“Companies, academic institutions, and startups use IBM Q technology and collaborate with IBM Research to advance quantum computing,” according to IBM.
Google, Intel, Microsoft, and others are all also active in the field of quantum computing. Working prototype systems have advanced to be capable of handling between 50-70 qubit at the top end – still a yawning chasm from the thousands of qubits thought necessary to break modern encryption schemes.
It might be possible that there could be quantum computers capable of breaking modern encryption schemes “within 10-15 years”, but “no-one knows for sure” when the industry might be advanced enough to deliver of such lofty targets, Moody told The Daily Swig.
Vendors working on quantum computer systems have steadily advanced the number of qubits they support over time, but there has been “no big breakthrough,” he added.
Seconds out. Round two
Quantum computers may still be years away but that doesn’t mean that developing algorithms to protect secrets in a post-quantum world can be sidelined or put off indefinitely.
NIST will allow the submitting teams to tweak their specifications and implementations before a March 15 deadline. The second phase of evaluation and review is expected to last between 12-18 months.
If anything, the field of post-quantum cryptography is more advanced than quantum computing.
Vendors, including Cloudflare, are already experimenting with post-quantum cryptography. The European Telecommunications Standards Institute (ETSI) is also promoting research in the area by helping to run workshops on quantum safe cryptography.
“It’s a growing field of research,” Moody concluded, adding that NIST was coordinating its work on post-quantum cryptography with ETSI, among other organizations.
Trail of Bits has a more detailed primer on post quantum cryptography that explores the topic in some depth.
