NIST looks for defense against code-cracking quantum machines
- By Brian Robinson
- Dec 22, 2016
The National Institute of Standards and Technology has taken the first steps to tackle the dangers to current data encryption methods posed by quantum computers. While the computers themselves are still some years away from being used to break encryption codes, NIST believes the time needed to develop quantum-resistant encryption is getting short.
NIST issued a formal call for proposals for Post-Quantum Cryptography Standardization on Dec. 20, focusing on gathering ideas that would lead to a “complete and proper” candidate algorithm for public key standards.
The algorithm would complement three existing NIST products: the FIPS 186-4 Digital Signature Standard and Special Publications 800-56A Revision 2 and 800-56B, which refer to “pair-wise” key-establishment schemes.
The new NIST program is on a fairly tight deadline as far as these complex algorithm developments are concerned, with Nov. 30, 2017, set as the deadline for proposals to NIST. Those algorithms that meet NIST’s acceptability requirements will be presented at an open workshop in early 2018. The evaluation that follows could take from three to five years.
NIST made its concerns clear in a report on the status of quantum computing research earlier this year, stating that, while in the past it wasn’t even clear that quantum computers were physically possible, “many scientists now believe it to be merely a significant engineering challenge.”
IBM, for example, is trying to build an all-purpose quantum computer that will be able to tackle a range of different problems and applications, similar to the way most classical computers work. Earlier this year, it made a five-qubit system available through the cloud for researchers and the general public to experiment with, to see how various algorithms and experiments would work with its quantum processor.
The company said it sees a 50- to 100-qubit, “medium sized” quantum processor being available within the next 10 years, which is substantially faster than was thought possible just a few years ago. Other companies like Microsoft and Google are also looking at ways to take advantage of quantum computing.
Canadian company D-Wave, which takes a different approach to quantum computers than IBM and other companies, is already delivering working machines. So far, it has Lockheed Martin, Google and the Los Alamos National Laboratory as customers, and it recently introduced a 2,000-qubit machine, double the size of its other system.
LANL is experimenting with the D-Wave machine to develop algorithms that will work with the company’s “quantum annealing” approach, which is currently thought most suitable for best-approximation applications. NASA is working with D-Wave to see how quantum computers can help with artificial intelligence and machine vision, and Lockheed Martin, which bought its D-Wave system in 2010, is using it to verify and validate mission-critical software.
However, neither LANL nor Lockheed expect to see quantum computers as standalone assets any time soon -- rather they’ll be used as “co-processors” along with other, classical computers.
Despite the very early stage that quantum computing is in right now, NIST officials have been getting nervous because, once the faster quantum machines do arrive, they can be used to break codes such as the widely used RSA (Rivest-Shamir-Adleman) public key encryption in far less time than it would take classical computers. Pulling together quantum-resistant cryptography will take time, and NIST feels that, unless it starts now, that new cryptography won’t be ready.
NIST mathematician Dustin Moody said the three products mentioned in the call for proposals are considered the ones most vulnerable to quantum computing. He said he expects there will be more than one post-quantum algorithm that will result from the new program, which will ultimately replace those three current standards.
NIST wants to get as many people around the world involved in developing quantum-resistant encryption, he said, so “we can have increased confidence in the results.”
“Post-quantum algorithms haven’t received nearly the same amount of scrutiny and cryptanalysis as those we currently use on today’s conventional computers,” Moody said. “We need that to change.”
Brian Robinson is a freelance technology writer for GCN.