Commonwealth Cyber Initiative researchers hone cryptographic algorithms to stand against powerful quantum threat

As the race to develop large-scale, reliable quantum computers gains speed, fortification efforts are ramping up to protect digital systems from a technology that could utterly obliterate their security. Commonwealth Cyber Initiative researchers at Virginia Tech and George Mason University are developing security protocols to fend off cyberattacks — both from today’s computers and from quantum computers coming down the pike.

In the interest of “prudence,” the U.S. National Institute of Standards and Technology (NIST) called upon the world’s cryptographers to craft and scrutinize encryption techniques that could resist attacks from powerful quantum computers. Six years later, in July 2022, NIST announced its first finalists, and Commonwealth Cyber Initiative researchers from Virginia Tech are among those who are working to make the selected algorithms more efficient and secure.

Prudent protocols

Sensitive data like personal identifying information, online bank accounts, and medical records ­ as well as government and military communications are protected by cryptography — algorithms that safeguard data through encryption. Quantum computers can solve certain problems much faster than classical computers, thus sweeping aside the cryptosystems currently in place.

But what is the rationale for mounting a defense against a technology that’s still in development? 

“First of all, we need to have techniques ready to prevent attacks before they become real-world problems. People are working on quantum computers as we speak, and they are making progress,” said Jason LeGrow, assistant professor of mathematics and Commonwealth Cyber Initiative fellow. “We need to be thinking about future-proofing our privacy. We don’t want the messages we send now to be compromised when someone has the means to decrypt them using more powerful technology than is available now.”

Authenticity, integrity, and encryption

Cryptography is the science of secret messages — but it’s not just about keeping information secret; it also verifies the authenticity of the person who sent the message and preserves message integrity so no one can tamper with it, said Travis Morrison, assistant professor in the Virginia Tech Department of Mathematics in the College of Science.

Different cryptographic protocols perform different jobs. The cryptographic algorithms selected by NIST are designed for two main cryptographic tasks: digital signatures, used for identity authentication and data integrity, and public-key encryption, which allows two parties to have a secure conversation without ever meeting each other.

“Take Amazon or Microsoft: Anybody or everybody wants to communicate with them, and they can’t do a new cryptosystem for each person,” said William Mahaney, a Commonwealth Cyber Initiative graduate researcher in math working with Morrison.

In public-key cryptography, a user has a public key and a private key. Sharing the public key doesn’t divulge the private key, but the two are mathematically linked. It is theoretically possible to tease out the private key from the public key.

“One way to think about it is if you mix salt and sand — very easy to do, very difficult to undo. They are linked in the mixture,” said Gretchen Matthews, math professor and director of the Commonwealth Cyber Initiative Southwest Virginia. “Could you separate them? Yes, but it would take a long time.”

When it comes to the currently deployed cryptosystems, a “long time” is usually good enough.

“It’s not that this problem is impossible,” said Morrison. “We all factored in grade school. But if the key is long enough, then the amount of time it would take to factor is on the order of the age of the universe. This is what classical public-key cryptography bases its security on — that the problem is hard or takes a long time to solve.”

It’s also all about having the right tools for the job; a Bunsen burner makes separating salt from sand easy. With a quantum computer, most public-key cryptosystem problems become trivial.

The threat and wonder of quantum computation

“Quantum computers are dangerous to some cryptosystems because, in a matter of hours or days, they can solve the underlying math problems that would have taken more than a lifetime before,” said Mahaney, who is also the Julian Chin Ph.D. Fellow in Cybersecurity. 

Classical computers deal in bits — 0s and 1s, this or that, yes or no, said Matthews.

“But when we consider quantum bits, a whole spectrum of possibilities opens up between 0 and 1,” said Matthews. Based on quantum mechanics, quantum computers behave in fundamentally different ways so that algorithms for certain types of computations are incredibly fast.

Post-quantum protection

“Post-quantum cryptographic systems are protocols that run on ordinary computer, but which we believe are secure even when an attacker has a quantum computer,” said LeGrow. You can run them on your cell phone, according to Morrison.

There are multiple subfields in mainstream post-quantum cryptography, said LeGrow, and experts in each subfield devise algorithms based on different mathematical frameworks. The families of algorithms have their respective strengths and weaknesses.

Code-based cryptography, which is in Matthews’ field of expertise, is the oldest scheme under consideration. These protocols are slower than some of the other systems, but researchers have had more time to scrutinize them for vulnerabilities.

Lattice-based systems, which Mahaney and Morrison are exploring, are faster but have large key sizes compared with current systems – not ideal for memory and bandwidth.

Isogeny-based schemes, which LeGrow and Morrison study, are at the other extreme, offering very small keys but running slower than other post-quantum schemes on average.

The NIST process aimed to define a suite of post-quantum cryptographic standards that use varied approaches for encryption and could serve as a toolbox of algorithms for different situations. The submissions were public so that the global cryptanalysis community could vet each one. Once an algorithm was submitted, “cryptanalysts would use every trick they could to break it,” said Mahaney. They swarmed and burrowed into every cranny of the system, sniffed out weakness in implementation or code, even in some cases how a computer or a network is set up – because if they didn’t find the cracks at this point, a hacker would later, when it could reveal private, proprietary, or classified information.

The NIST candidate pool was winnowed down until July, when NIST released the four initial candidates selected for standardization and announced a follow-up round for two remaining candidates — all from an original list of 82.

Among the schemes selected for standardization is a digital signature protocol known as FALCON. Morrison and Mahaney focus on algorithms to optimize the FALCON cryptosystems, which will be released as a full standard in the coming months. In collaboration with Krzysztof Gaj, a Commonwealth Cyber Initiative researcher from George Mason University, they are also looking at how susceptible these schemes are to side-channel attacks that take advantage of information leakage through timing, power consumption, and electromagnetic radiation.

Both candidates in the follow-up round are code-based algorithms, and Matthews and her team are developing families of codes with the goal of speeding up the algorithms without sacrificing security. Morrison’s and Matthews’ projects are both supported by the Commonwealth Cyber Initiative in Southwest Virginia.

As the NIST process comes to a close, an energized field of post-quantum cryptography continues to generate new techniques and algorithms for a wide array of security applications that will safeguard information today and in a quantum future.