edoardo nist

FAU Researcher’s Algorithm Part of Final Selection Round for Creating First Post-Quantum Cryptography Standard

August, 2020

Congratulations to Edoardo Persichetti, Ph.D. , assistant professor in the Department of Mathematical Sciences and a member of the FAU's Center for Cryptography and Information Security , whose proposal for a cryptographic encryption scheme made it to the final round of the Post-Quantum Standardization process. This program, created by the National Institute of Standards and Technology (NIST), involved a three year period of phased reviews where NIST, as well as a public audience of researchers and experts, examined new approaches to data protection that could defeat an assault from a powerful quantum computer. NIST has reduced the 69 submissions it initially received down to a final group of 15 (seven finalists, and eight alternates) and has now begun the third round of public review. This “selection round” will help the agency decide on the subset of these algorithms that will form the core of the first post-quantum cryptography standard.

Persichetti highlights the critical importance of this new cryptographic standard to the security of the nation and our sensitive information, “Quantum computers represent a realistic (if not yet tangible) threat to the world of secure communications. In fact, quantum computers with sufficient power and stability will allow us to run powerful algorithms, capable of breaking the vast majority of cryptographic schemes in use nowadays. This is because such schemes are largely based on certain mathematical problems, for which such dedicated quantum attack algorithms exist. As a consequence, it is of fundamental importance to design, implement and standardize entirely new systems, based on different mathematical approaches, to protect our communications for the years to come. Given the desired lifetime of certain encrypted communication (including: classified information, up to 30 years or more) and the time necessary to develop, test and distribute a whole new range of cryptographic schemes, it is necessary to act now.”

The first deadline for this competition was November 30, 2017. The call from NIST aimed to find candidates for two macro areas: the first is encryption/key exchange and the second is signature schemes. Submitters were asked to prepare a full package, including a specification document with all necessary details and theoretical foundations, a working implementation in the language of choice (C or C++), performance benchmarks (timings, memory requirements), and so on. Persichetti was invited to join a project for a submission called “Classic McEliece,” led by professor D. J. Bernstein (renowned scientist and cryptographic personality), in honor of the work of Robert J. McEliece, who is the de facto founder of code-based cryptography. The goal of the submission was to present a conservative candidate for encryption, following McEliece’s original approach but translating it to a modern-day declination.

Persichetti then became part of a number of other submissions. The first, called “BIKE,” is the result of a collaboration with several research groups in France and includes some ties to industry: R. Misoczki, Ph.D., who is a research scientist at Intel and served as the team leader, as well as professor Shay Gueron, Ph.D., from the University of Haifa, Israel and researcher at Amazon Web Services, who served as the lead for implementation.

Persichetti was also involved in a project named “DAGS,” based on an original design from himself, where he was the team leader, and partnered, among others, with researchers in Brazil and Senegal, as well as colleagues at George Mason University.

Finally, Persichetti was approached by P. Gaborit, a well-known researcher from France, to provide protocol expertise on a project of his own, called “HQC,” and was then invited to join this team as part of his fourth submission.

Round one saw 69 submissions accepted as “complete and proper.” The candidates were formally presented at the Inaugural Standardization Conference, which was hosted at FAU, co-located with PQCrypto 2018, one of the major conferences in the area of research. It took until January 30, 2019, to receive feedback, and on that date, NIST announced a subset of candidates, selected to move on to a second round, which foresaw further study on what was deemed the most promising schemes. During the time following the first round presentation, several schemes were attacked, broken, or withdrawn. Unfortunately, this included DAGS, for which a vulnerability was found, and despite a quick and easy fix, NIST deemed to have “not full confidence,” and preferred to move on to candidates whose security had not been disputed. However, Persichetti’s remaining three submissions were all selected for the second round, among a total of 26. The second round allowed for “small” tweaks (that is to say, nothing that structurally changed the underlying design), as well as mergers, the addition of new members, for instance.

In this next phase, the effort was renewed and several additional months of work went into preparing the updated second round package, which was submitted on March 15, 2019; second-round candidates were formally presented at the 2nd Standardization Conference, co-located with CRYPTO 2019, the flagship conference in the area, hosted at UCSB in Santa Barbara in August 2019.

At this stage, all “surviving” candidates were competitive, both in terms of security and performance, and the second review period saw a major challenge for NIST, aiming to further narrow down the field of competitors. In fact, the competition was so fierce that a third round was deemed necessary, in order to get closer to a conclusion. Finally, a smaller subset of candidates was selected and announced for the third round.

NIST mathematician Dustin Moody says, “...this review period will last about a year, after which NIST will issue a deadline to return comments for a few months afterward. Following this roughly 18-month period, NIST will plan to release the initial standard for quantum-resistant cryptography in 2022.”