The race for quantum-proof cryptography

Lawmakers briefed on quantum computing’s threat to encryption and the urgent need for mathematical research.

One of the biggest threats to privacy and national security is the ability of the immensely powerful quantum computers to break prevailing methods of encryption almost instantaneously. Once quantum computers become a reality, something that could conceivably happen in the next decade or two, all of the data protected by encrypted systems on the internet will become decrypted and unprotected, accessible to all individuals, organizations or nation-states.

Dr. Jill Pipher, President of the American Mathematical Society, VP for Research, and Elisha Benjamin Andrews Professor of Mathematics at Brown University led a briefing last week for lawmakers on Capitol Hill called “No Longer Secure: Cryptography in the Quantum Era” about the threats that quantum computing poses to existing cryptographic systems that support national and economic security. Senator Jack Reed (D-RI) began the briefing by saying “we’re acutely aware of the potential advantages and disadvantages that quantum presents. And we’re also very concerned that some of our adversaries and competitors are investing a great deal in quantum computing.”

Reed, who sits on the Senate Intelligence, Armed Services and Appropriations committees, is concerned that the Trump Administration has dropped the ball in getting ready for the complex threat of quantum computing. “We really need a whole of government approach. With this administration, it’s not whole of government. It’s fragmented.”

Congressman Jim Langevin (D-RI) called quantum computing a “fascinating and scary topic” because all of the assumptions “that so much of the internet is based on today don’t seem to apply.” Right now, Langevin said, “trying to brute force cryptographic locks is nearly impossible. It would take billions of years using the fastest computer to do that today.” But, within decades it’s possible for the far more powerful quantum computers to guess current encryption keys within a fraction of a second. “Deploying new algorithms is a policy challenge in and of itself. Certainly, Congress needs to look at it sooner rather than later.”

“The future of the powerful quantum computing threatens the cryptographic infrastructure that we’ve spent decades developing,” Dr. Pipher said, in making the case for faster development of quantum-proof cryptography while governments and companies race to build quantum computers. “About four or five years ago it became rather urgent for companies and governments to develop cryptography that would resist the speed ups afforded by a quantum computer.”

Encryption that will survive quantum

Modern cryptography, which was developed in the 1970s and is based on securely exchanging cryptographic keys using a method developed by mathematicians Whitfield Diffie and Martin Hellman, is now essential to our online commerce, our national security, and our privacy, Pipher said. “Quantum computers of the future threaten the security of this infrastructure.”

One encryption solution that might survive quantum computing advocated by Pipher is one she herself pioneered with fellow mathematicians Jeffrey Hoffstein and Joseph Silverman in 1996 called NTRUEncrypt. NTRUEncrypt is an alternative to the prevailing encryption methods known as RSA (Rivest-Shamir-Adelman) or ECC (elliptical-curve cryptography).

Their goal in developing NTRUEncrypt was to find a “hard problem,” such as factoring a product of large prime numbers, upon which RSA encryption is based, but do it more efficiently. The hard problem they developed is based on something called a lattice, a regular array of points like a crystal lattice. “In a thousand dimensions, it’s actually a really hard problem” and not as big as the prime number products undergirding RSA, she said, “so that’s where the efficiency lies.”

NTRUEncrypt, which is now fully accepted to IEEE P1363 standards under the specifications for lattice-based public-key cryptography (IEEE P1363.1) but is nevertheless still considered relatively new and untested, should withstand even quantum computers because of its difficulty to solve, Pipher said. “We discovered that the crypto system we built then cannot be broken by a quantum computer.”

More research (and more mathematicians) needed

Regardless of whether quantum computing is achieved in ten or twenty years, we “must begin now to prepare all our information security systems to be able to resist quantum computing,” Pipher warned. “We need a lot more research in this area. We simply need a lot more mathematical research in quantum cryptography to do things. First, to realize the power of quantum computing and [secondly] to protect against the perils of quantum computing.”

When it comes to cryptographic breakthroughs that might protect us in an era of quantum computing, Pipher stressed that time is of the essence because of how long testing of various systems takes. It can take years to develop proof that any cryptographic system works, and even now the RSA system widely used across computing systems and the internet still has no proof per se of its validity.

“We can only rely on the constant scrutiny and efforts of many people in many different fields trying to break that system,” she said. “This is why it’s very important to begin now to work on new cryptographic systems because they are going to have to go through the test of time before they really can be relied upon to be completely secure.”

In terms of what companies should be doing now to get ready for what is going to be the inevitable reality of quantum computing, Pipher pointed back to her lattice-based cryptography and said that there are some algorithms based on lattices that some companies have started to lay over their existing protocols, which is a good start.

More importantly, though, “be sure to have somebody on board who understand the technicalities to protect against cryptographic breaks. Have them evaluate the products that are out there. Every company should be hiring mathematicians.”

Making a case for collaboration

Regarding the national security implications of quantum computing, two countries — the U.S. and China — stand out as leading the way, Pipher said, even though the mathematical research in this area results from a truly global collaboration of countries working together. “On fundamental research, it’s truly important to have every mind working together.”

It’s not likely that one organization or country can secretly achieve quantum computing to obtain, in essence, access to all the world’s secrets first, Pipher said. “A quantum computer that is going to break all this cryptography is going to require two to four thousand qubits, much bigger than we have right now.”

Moreover, secrecy around such a breakthrough would be very hard to maintain. “I suppose anything is possible,” she said. But “it’s hard to keep a discovery like this secret in a world of eavesdropping and spying and so forth. People are so happy to make these discoveries that they announce them as quickly as they can.”

This story, "The race for quantum-proof cryptography" was originally published by CSO.

Related:
  
Shop Tech Products at Amazon