The National Security Agency did a surprising thing last August – it suddenly declared that the algorithms it had spent a decade telling the world were the best way to lock up secret data weren’t safe anymore. The reason? The danger of quantum computers.
The NSA has now released more detail on those fears. “There is growing research in the area of quantum computing, and enough progress is being made that NSA must act now,” says a new Q&A-style document on the problem. It’s aimed at companies and government departments working with sensitive data.
The catch is that no one knows how to make quantum-computer-proof encryption. The NSA can only tell companies building new systems to use certain algorithms “believed to be safe from attack by a large quantum computer.” It says it’s working with the National Institute of Standards and Technology on coming up with some new standard algorithms that could survive in a post-quantum era.
Work in that area is still in an embryonic state, however. Quantum-resistant encryption algorithms that have been proposed by researchers at Microsoft and other places have not been formally proved to be safe against the power of quantum computers.
How close we are to quantum computers that could crack cryptography? The NSA isn’t making any bets, at least not publicly. It will only say that recent advances in the field should make us worry about future-proofing systems being built today to protect critical national infrastructure that will be in service for perhaps decades.
There has been striking progress toward building small proof-of-concept quantum computers in the last couple of years. The leaders of Google’s quantum computing effort say they expect to have one in hand that might even do useful work in just a few years.
Reassuringly, though, breaking cryptographic keys is one of the most difficult things you can hope to do with a quantum computer.
Quantum computers are made up of devices called qubits. Researchers expect that some chemistry simulations and machine-learning problems can be taken on with just hundreds or thousands of qubits. Cracking a cryptographic key of the kind used commonly today would require hundreds of millions of qubits.
That suggests our cryptography may be undefeated for a while even after the quantum computing era properly arrives, perhaps giving us enough time to update it. However, many computers and software in use today aren’t patched against even known security problems for which fixes are readily available. We can probably expect a considerable quantum security hangover even if the NSA does manage to come up with a quantum-resistant cryptography standard.