Waterloo researchers leading quest to protect against quantum attacks

The University of Waterloo emerged as the Canadian institution with the largest involvement in the latest round of submissions selected by the United States National Institute of Standards and Technology (NIST) in the Post-Quantum Cryptography Standardization process.

After three years of review, four submissions involving Waterloo researchers in the Department of Combinatorics and Optimization are among the seven finalists and eight alternates, still in the running for potential standardization in the future, selected by NIST in the third round of the competition-like process. There were originally a total of 69 submissions received from around the world.

Cryptographic standards are particularly important, as they enable secure communication and commerce at a global scale. These standards take a long time to develop, and the cryptographic standards available today were developed before cryptographers really took the threat of quantum computers seriously.

NIST is looking to find the best ways to establish a secret key between two parties on different communications channels to ensure the privacy of the communications between them, with the aim of selecting the best of these methods to become the new standard.

John Schanck, a post-doctoral fellow, is involved in two submissions shortlisted among the seven finalists.

Schanck is the team lead for NTRU, which is the oldest system based on hard math problems around lattices in the competition. NTRU’s age, a long history of failed attempts to attack it, and the fact that its patents have now expired are among the reasons it emerged as a finalist.

“I was employed by Security Innovation from 2011 to 2016, while they owned NTRU Cryptosystems,” Schanck explains. “While I was there, I made several small improvements to the design, and these changes were incorporated into the NIST submission.”

Schanck is also a member of the team behind Crystals-Kyber, a much more recent design that offers a higher level of security than NTRU for a fixed performance budget.

“Another finalist, Saber, is a tweak on the Crystals-Kyber design,” Schanck shares. “We expect there will be a significant discussion between the two teams in the third round, and hopefully some consensus will emerge on which of the two systems is the better design.”

Douglas Stebila, an associate professor, is a co-submitter of the alternate candidate, FrodoKEM. Some of the partners on FrodoKEM include Microsoft Research and Google.

FrodoKEM belongs to the family of lattice-based cryptography, which also includes the NTRU and Crystals-Kyber submissions.

“The difference with FrodoKEM is that the mathematical problems it relies on have less structure,” Stebila says. “On the one hand, having less structure means that there are potentially fewer avenues of attack, but this does come at the cost of being less efficient and having larger communication overhead.”

Outside of the NIST process, earlier this year, FrodoKEM was selected by the German government’s Federal Office for Information Security as one of two post-quantum algorithms suitable for immediate use for long-term protection of information against quantum adversaries.

Professor David Jao and Geovandro Pereira, a post-doctoral fellow in Waterloo’s Institute for Quantum Computing, are the lead author and co-submitter respectively for alternate candidate SIKE. Jao and Pereira have partnered with the likes of Amazon, Microsoft Research, IBM Research Zurich, Infosec and LinkedIn Corporation on the project.

SIKE is a family of post-quantum key encapsulation mechanisms based on a key exchange protocol called Supersingular Isogeny Diffie-Hellman (SIDH), invented by Professor Jao. It contains two algorithms that make it difficult for hackers to intercept the key with either a classical or quantum computer.

“A notable advantage of SIKE is that it has smaller encryption keys than any other proposed candidate,” explains Jao. “This feature makes SIKE suitable for devices and applications where size is at a premium.”

The review process for the third round will last about a year, with NIST aiming to release the first standard for quantum-resistant cryptography in 2022.