Quantum computing will make encryption techniques obsolete—the U.S. government has a plan

For roughly three decades, experts in digital cryptography have been monitoring a distant threat: that a powerful enough quantum computer could one day render the most widely used forms of encryption—the layer of code protecting everything from national security secrets to personal banking records—obsolete. Today, the U.S. Commerce Department’s National Institute for Standards and Technology (NIST) is unveiling the final version of three new algorithms, long in development, that are designed to counteract the threat. (The White House will also hold an event to celebrate the new standards.) Hopefully, they’re not too late.

Traditional encryption relies on cryptographic algorithms, mathematical equations that must be solved to unlock the data they are encoding. Three of the most widely used cryptographic algorithms in use today—RSA, elliptic curve cryptography, and Diffie-Hellman key exchange—rely on the fact that particular kinds of mathematical problems, involving factoring large numbers and finding “discrete logarithms,” are incredibly labor-intensive to solve using a classical computer.

With current technology, cracking the latest RSA standard, for example, could take a billion years or more. But in 1994, mathematician Peter Shor published a groundbreaking paper showing how, with a theoretical quantum computer, you could break all three of these cryptographic schemes in mere hours. It’s estimated that 90% of internet connections begin by using RSA to establish a secured “handshake,” so the scope of the threat is massive. (Not everything is under direct threat, though: The Advanced Encryption Standard, or AES, a so-called symmetric-key algorithm that’s used to secure highly classified U.S. government data, could potentially be compromised by a different kind of quantum attack than Shor described, but can be secured through a relatively simple change.)

Today’s quantum computers are still too small and error-prone to break current cryptography standards. But according to the Global Risk Institute’s most recent Quantum Threat Timeline Report, published this January, “there is no known fundamental barrier to realizing large-scale quantum computing.” It estimates a 17% to 31% chance of someone developing a Cryptographically Relevant Quantum Computer—i.e., one that can crack RSA encryption in less than 24 hours—within a decade, and a 33% to 54% chance within 15 years.

That may seem like plenty of time to prepare. But experts in the government and private sector insist the time to start is now. “We know cryptographic transitions take a long time,” says Dustin Moody, a mathematician who has led NIST’s post-quantum cryptography effort since 2014. “They can take 10, 15, 20 years. So we can’t wait until the computer’s big enough.” There is also the threat of “harvest now, decrypt later” (HNDL) attacks, in which hackers collect data now in hopes that they will be able to decrypt it later when a quantum computer is available. HNDL attacks would likely target data that has a long shelf life, including things like social security numbers, bank account information, and government or corporate secrets.

“Just ignoring the problem would be a catastrophe,” says Dario Gil, senior vice president and director of research at IBM, one of several corporate partners that helped develop the new standards alongside NIST. “But as always on things that take a little bit of planning, there’s this challenge of urgency. We all have so many problems that the temptation of humans and institutions is to delay, but we shouldn’t.”

As it has in developing other cryptographic standards, NIST turned to the community of mathematicians and cryptographers for input, putting out a formal call for new quantum-safe algorithms in 2016. Of the 82 cryptographic schemes that participants proposed, 69 met the standards and were put through a first round of evaluation. 

Each standard was extensively tested. “Cryptographers could try and attack it,” says Moody. “They could study it, they could do performance benchmarks on it. You could do whatever you want with it, with the idea that the strongest ones survive, the weakest ones are broken and killed off.” 

After three rounds of testing, and five NIST workshops each with a few hundred people in attendance, four proposals were selected for standardization and released in draft form in 2022. “We found that these competitions really get the cryptographic community’s attention and focus,” says Moody, who estimates that up to a couple of thousand people ultimately participated. “And by the time we’re done, everyone’s usually in agreement that these are some good algorithms that are going to see widespread deployment.”

The three algorithms finalized today are called CRYSTALS–Kyber, CRYSTALS–Dilithium, and SPHINCS+. A fourth, called FALCON, is expected to be released next year. The two CRYSTALS algorithms, as well as FALCON, are based on lattices, ]">geometric repeating structures. “Our brains think [of lattices] in two dimensions or three dimensions, but for these lattices, we do the math in 500 or 1,000 dimensions,” says Moody. Decrypting these algorithms involves finding sets of vectors that can be combined to form a specific “key” vector, which is considered such a difficult mathematical problem that even quantum computers would struggle to solve it. The SPHINCS+ algorithm uses something called hash-based cryptography, which turns information into a jumbled code that is hard to decipher. “We wanted to have a few algorithms not based on lattices, in case someone discovers an attack,” says Moody. “SPHINCS+ is one, and we’re likely going to select one or two other algorithms that are not based on lattices to standardize in the future.”

The post-quantum standards come amid rising national security concerns, particularly with regard to China, which is believed to have invested more than $15 billion in quantum computing projects. “I think the first threat [to encrypted data] will come from nation states,” says Gil, from IBM, “because these systems are massive complex things to build at the scale that we’re talking about. China has been invested very heavily in quantum, and I think it’s reasonable to assume that they will succeed. They won’t be the only ones.”

NIST’s National Cybersecurity Center of Excellence, a public-private research partnership dedicated to cybersecurity and the advancement of secure technologies, is ready to help companies and organizations make the transition to quantum-safe cryptography. Says Moody: “One of the first things you want to do is take inventory to find out where you are using cryptography, which cryptographic algorithms you are using, what data is being protected by these algorithms, which products and applications that involves. Make sure your IT people know this is coming and get educated.”

Because the nation states that develop them are likely to keep them secret, “I don’t know if we’ll publicly see the first [cryptographically relevant] quantum computers,” says NIST’s Moody. “I’m not too worried by the threat, though, because we have strong confidence in the algorithms that came out of this process. That’s not a 100% guarantee, but it doesn’t keep me up at night worrying.”

https://www.fastcompany.com/91171841/quantum-computing-will-make-encryption-techniques-obsolete-the-u-s-government-has-a-plan?partner=rss&utm_source=rss&utm_medium=feed&utm_campaign=rss+fastcompany&utm_content=rss