That means they could create an enormous security headache if they are used to crack the encryption that currently secures everything from emails and medical records to bank transactions.
As research into quantum computers has progressed in recent years, governments and tech companies have realised that if someone does build a large-scale quantum computer, then a new quantum-resistant form of encryption will need to be ready and waiting.
NIST is asking for comments on a new process to find and evaluate public key cryptographic algorithms that can't be cracked by quantum computers.
"If large-scale quantum computers are ever built, they will be able to break many of the public-key cryptosystems currently in use. This would seriously compromise the confidentiality and integrity of digital communications on the internet and elsewhere," NIST said.
Researchers have estimated that a quantum computer capable of breaking 2000-bit RSA in a matter of hours could be built by 2030 for a budget of about $1bn. "This is a serious long-term threat to the cryptosystems currently standardized by NIST," the Institute warned in its recent report on Post-Quantum Cryptography.
The goal is to develop systems that are secure against both quantum and classical computers, and that can interoperate with existing communications protocols and networks.
NIST said that some engineers are predicting that within the next 20 years someone will build quantum computers big enough to break essentially all the public key schemes currently in use. As it has taken almost 20 years to deploy our modern public key cryptography infrastructure, that means "we must begin now to prepare our information security systems to be able to resist quantum computing", said NIST.
New crypto approaches required
Many cryptographic algorithms base their security on the difficulty that conventional computers have with factoring very large numbers, which is something that quantum computers can do much more efficiently. But different mathematical approaches might be able to trip up quantum computers, so researchers are looking at some exotically-named types of cryptography. These include methods based on lattices, codes, multivariate polynomials, and hashes; other proposals are based on evaluating isogenies on supersingular elliptic curves, the conjugacy search problem, and related problems in braid groups, noted NIST.
NIST is exploring preliminary evaluation criteria for quantum-resistant public key cryptography standards, a process that's due to be finalised by the end of this year. NIST will then begin accepting proposals for quantum-resistant public key encryption, digital signatures, and key exchange algorithms, with a deadline in late 2017. This will be followed by three to five years of public scrutiny before they are accepted as standards.
So, while new encryption algorithms should protect future communications against attack, what about all that old data secured with existing cryptographic standards? Will it be at risk at some future date? Professor Alan Woodward of the University of Surrey thinks it's unlikely.
"Some intelligence agencies might keep some high-value communications from targets of interest, but to the general public it will be a threat from the point it emerges rather than retrospectively," he said.
Woodward also noted that the public-key encryption algorithms are those that are at risk -- and these are only used for key exchange, and most employ forward secrecy anyway so that the key changes for each dialogue.
"Someone who had stored the encrypted messages would not be helped by quantum computers as the messages themselves are actually encrypted using symmetric key encryption schemes. Someone would not only have had to store the messages by the dialogue that exchanged the key, but also know exactly which key relates to which message," he said.