Can quantum computing prevent an encryption meltdown?
Source: Matt Leonard
“Almost everyone is prepared for the worst,” ABC News correspondent Steve Osunsami reported in 1999, as computer scientists worked to resolve the Y2K problem before computer systems malfunctioned when two-digit date fields rolled over for the year 2000.
Today, "the worst" looks like the cracking of the encryption scheme that protects banking, communications and national security applications.
RSA public-key encryption relies on the mathematical task of dividing large numbers into their prime factors, a job too difficult for today's computers to solve quickly enough to be practical, according to Douglas Stebila, an associate professor at the University of Waterloo working on cryptography. “But quantum computers would be able to do it efficiently,” he said.
The issue becomes more urgent when considering that quantum computers, once they’re a reality, will be able to break RSA-encrypted messages that are intercepted today, stored until decryption capabilities exist and then broken, Stebila explained.
“A quantum computer could retroactively break confidentiality, so information that I encrypt today using vulnerable public key encryption like RSA, an adversary who records that and gets a quantum computer 20 years in the future could go back and retroactively decrypt that information,” he said.
That means we should be concerned about protecting “information that has a long lifespan -- like health records, military secrets -- that need to be kept confidential for 20, 50, 100 years … against quantum computers even though they don’t exist,” he said.
Fortunately, the National Institute of Standards and Technology is already working on a post-quantum cryptography standard and is on track to have a new quantum-resistant standard by 2022 or 2024.
“We know it is going to take time to finalize the crypto in a standard, have industry start to implement it in products and then get the infrastructure refreshed with the new encryption,” NIST Computer Security Division Chief Matthew Scholl said at an Information Security and Privacy Advisory Board (ISPAB) meeting said earlier this month. “So with all of that work ahead of us, it’s important that we do this now.”
“We will either have the ability to have a natural migration through product evolution, or we might have to do a Y2K-type effort,” he said, referring to level of effort involved, Scholl later told GCN.
In 2016, the agency put out a call for post-quantum cryptographic algorithms. NIST received 69 initial submissions from 16 countries. Many of the submissions weren't necessarily new ideas, but were based on research that had been around for years without being widely adopted.
“There was nothing really particularly different than what we already knew five years ago,” said Vadim Lyubashevsky, the lead scientist for IBM Research Zurich, who was involved with three submissions. “I mean, there [were] a few improvements here and there, but really many of the schemes are based on exactly the same ideas we [had] five to 10 years ago.”
Stebila worked on two submissions and said they were based on research that began in 2014 before NIST made its announcement.
This is why Lyubashevsky and Chris Sciacca, a spokesperson for IBM Research Zurich, said quantum-safe encryption doesn't depend on a NIST standard. “Clients don’t need to wait … however many years it takes to develop these standards,” Sciacca said. “They can already begin preparing today.”
At the very least, companies and organizations need to begin to audit their systems to determine where they might be vulnerable to quantum attacks, Stebila said.
The White House has acknowledged the importance of quantum research. The National Cyber Strategy, released in September this year, highlighted the efforts being made by NIST and said the federal government plans to make a switch to post-quantum encryption.
“The United States must be at the forefront of protecting communications by supporting rapid adoption of these forthcoming NIST standards across government infrastructure and by encouraging the Nation to do the same,” it stated.
“Folks are incredibly eager" to transition to post-quantum, Scholl told the ISPAB board.
NIST plans to announce which algorithms made it into the second phase of the standard-development effort by late 2018 or early 2019. The next phase will focus more on the performance, size and agility of the algorithms. The final outcome will be a “suite of options,” less than 10, but more than two algorithms that can hold fast against quantum, Scholl said.
The big gray area in the entire conversation is that no one knows when quantum computers will become a reality. Technically, there are quantum computers today, but they are nowhere near powerful enough to crack current encryption. And when they will be strong enough is still just a best guess.
“We knew when Y2K was coming, so that was an easy item,” Scholl said. “We’re currently just projecting when we think a quantum-relevant computer is going to come.”
| }
|