Will Quantum Computers Surpass Encryption?

Of all the what-if scenarios that keep IT leaders up at night, security and fear of cyberattacks have always ranked high on the list. Looming on the horizon is another worry: with the advent of quantum computing and ever-increasing compute power, there is the possibility that encryption previously considered air-tight could be cracked.

The issue is particularly worrisome to the U.S. National Security Agency (NSA), which believes that while it may be decades at least before such encryption-cracking is a real threat, officials need to start addressing the matter now. Back in 2015, the agency issued an advisory that developers of all national security systems "need to transition to quantum resistant algorithms in the future."

Unlike ordinary bits that are used in today's computers, quantum computers will use "qubits," which the agency memorandum says "will behave in surprising ways, efficiently performing selected mathematical algorithms exponentially faster than a classical computer."

Quantum computers, or what the agency refers to as "crypto analytically relevant quantum computers" (CARQC), could undermine public key algorithms in use at the NSA today.

"Because it can employ quantum phenomena as part of its algorithms, a quantum computer could provide exponential speed up against problems like factoring and discrete logs," the mathematical foundations underlying all of today's commonly used public key cryptography, explains Neal Ziring, technical director, Capabilities Directorate, for the NSA. "Nearly all of our current cryptographic security is based on one or another variant of those two problems,'' he adds. "Therefore, we have to think about what are other mathematical foundations on which we could base public key cryptography?" The focus is on finding algorithms that can be used that will not be vulnerable to attack by a quantum computer, and also be secure against conventional attacks, whether a laptop or a large parallel supercomputer.

Quantum computing is not just a larger and faster computer that will become the next evolution of high performance computing, adds Sage Briscoe, crypto subject matter expert at the NSA. "It's a fundamentally different paradigm of computation." The bottom line? Quantum computers can break public key cryptography in use today.

The private sector also needs to be thinking about encryption-cracking, especially in highly regulated industries like banking where, like the NSA, lots of sensitive information is held in storage.

Echoing the NSA's stance, William Whyte, chief technology officer of On Board Security, a provider to the vehicle-to-vehicle security, trusted computing, and advanced cryptography markets, says, "The problem isn't that quantum computing will come tomorrow, the problem is it takes so long to change our systems to use a different algorithm that if we don't do it now, we might be in trouble." On Board works with companies on cryptographic security and Whyte says there are two algorithms that are most widely used and can be broken by quantum computers: RSA and elliptical curve cryptography (ECC). "Those are the ones we need to migrate away from,'' he says.

The NSA has also stipulated that RSA is among the public key algorithms that are vulnerable, along with Diffie-Hellman, ECDH, and the Elliptic Curve Digital Signature Algorithm, (ECDSA). Meanwhile, the U.S. National Institute of Standards and Technology (NIST) is now accepting submissions so it can develop a standard set of public key quantum-resistant algorithms. Ziring says the NSA will participate in analyzing proposals from a huge community that will include academia, the private sector, and international organizations.

Significant research will still need to be done even after the new algorithms are implemented, and they will come with tradeoffs, says Briscoe, such as larger key size or message size, or slower computation. Depending on the characteristics the new algorithms have, "We have to figure out where the pain points are and what might slow down the Internet as we use these new algorithms," she says.

"NIST may pick several, maybe some that work well for lightweight devices and others that need to go at very high speeds,'' says Ziring. "So the field is wide open for good computer science research in this area."

Whyte agrees NIST is on top of this issue, but worries the private sector is underestimating the time needed to transition to new algorithms. Another risk he sees is that if someone sends an encrypted message now, it could potentially be saved until quantum computing comes along, and then be un-encrypted.

"Now is the time people have to [start] reengineering their systems so that it's safe to swap to new quantum-safe crypto,'' he stresses. "If we start now and finish by 2024, we're probably good." The later organizations start, however, "the greater the risk of a catastrophic break of a financial transaction system."

Esther Shein is a freelance technology and business writer based in the Boston area.