Government Must Prepare for When Quantum Computers Can Crack Its Encryption
The agency says the government must develop encryption strong enough to survive a quantum attack.
US lawmakers including Senator John McCain and Dianne Feinstein are attempting to undermine technology companies' efforts to encrypt everyone's communications, citing dangers to law enforcement. But that debate may be moot: Computers are getting so powerful that they will eventually be able to break any encryption.
The National Institute of Standards and Technology, a division of the Commerce Department that vets technology for the federal government, will be calling for proposals from industry and academic groups later this year to help create encryption that can beat the ever-growing abilities of advanced computers.
A report this month from the agency, which helped create the SHA3 and AES encryption standards that are widely used today, predicts that quantum computers will be able to break the popular public key encryption technology RSA by 2030 at a cost of a billion dollars. Quantum computers rely on qubits, which can simultaneously represent both a one and a zero, and can execute calculations thousands of times faster than existing supercomputers.
NIST recommends that federal agencies have post-quantum encryption in place at most 10 years from now.
Encrypted data created and stored in the past would no longer be safe once quantum computers get good enough
"It's the big problem in our field," said encryption expert Matthew Green, associate professor at John Hopkins University's Department of Computer Science. "All of our public key encryption that we use today is vulnerable to quantum algorithms that break it entirely. We don't have anything efficient to replace it yet."
The fundamental pillar keeping RSA encryption intact is the fact that factoring large numbers is still difficult for computers. The highest number Shor's algorithm has been able to factor is 21. According to the Physics arXiv Blog, there have been higher numbers, but those were factored with shortcuts and an incomplete model.
The issue is that encryption is supposed to protect anyone from powerful malicious actors, such as an oppressive government or well-funded criminal organization. But once these powerful quantum computers hit the market, only elite, well-funded players will have access to them. That means that the Russian government, for example, or the NSA will have the resources to break any crypto that an ordinary citizen could use today.
"The problem is finding regular crypto systems that can run on my computer, which is not a quantum computer, that will stand up against quantum computers," he said.
Green says there are efforts to build these systems, but none are efficient enough to be used day to day.
It isn't just data in the future becoming vulnerable. Encrypted data created and stored in the past would no longer be safe once quantum computers get good enough. The NSA runs a huge data center in Utah that is purported to be collecting a large swath of what is found on the internet.
"The NSA classifies things for 30 years and sometimes those secrets, even after 30 years, still matter," said Green. "There were Soviet spies who were still active decades after they'd been recruited. If someone had a way to decrypt Russian messages giving the identity of those spies, even 20 or 30 years later, that could have been valuable information."
Green thinks encryption is one of the only things that keep us safe from governments, and possibly corporations in the future, from spying on us. With programs like XKeyscore, the NSA have the software to continuously monitor someone's internet activity.
"Encryption has a lifespan, and that lifespan is about 20 to 30 years before it will be breakable. That's what has people nervous."
Correction: An earlier version of this piece said that Congressman Ted Lieu has been undermining efforts to encrypt communications; in fact, the opposite is true. He recently introduced a bill to prevent states from writing their own anti-encryption laws.