Building Confidence in Quantum-Resistant Algorithms: How much analysis is needed?

Published 02/25/2021

Written Roberta Faux, Lead Author and Quantum-safe Security Working Group Member

The CSA Quantum-Safe Security Working Group has produced a new white paper, “Confidence in Post Quantum Algorithms.” This paper attempts to measure the published analysis of post-quantum or quantum-resistant cryptography as we prepare to upgrade the global public key infrastructure. It is hoped that this document will serve as a much-needed start in determining how much analysis is needed to solidify our confidence in future quantum-resistant cryptography.

Types of Quantum-Resistant Cryptographic Algorithms

There is a wide variety of quantum-resistant cryptographic algorithms which generally fall into a few classes: lattice-based, multivariate, hash-based, code-based, and supersingular isogeny. Each class is based on a particular mathematical hard problem. The focus of our paper is on the cryptanalytic and mathematical research that offers confidence in an algorithm's security as evidenced in publications.

In July 2020, NIST announced the Round Three selection for cryptographic algorithms to address the now well-recognized threat from future large-scale quantum computers. This marks five-years since NSA recommended preparing for transitioning to quantum-resistant cryptosystems. It is essential that we strengthen our confidence in these algorithms by understanding how much security analysis has been done.

Analysis of NIST Round Three Candidates

A fundamental step towards adopting quantum-resistant cryptography is standardization. NIST solicited nominations for public key quantum-resistant schemes in December 2016. There were 82 submissions, 69 of which were accepted. Those were later down-selected to 26. In July 2020, NIST announced the Third-Round candidates consisting of 15 algorithms, 7 of which are considered finalists and the other 8 are alternatives for potential future standardization.

Just months after NIST’s latest announcement, attacks have emerged identifying serious weaknesses in two of the Third-Round candidates. It remains to be seen if the severity of the attack on the algorithms will remove them from future standardization. In any event, this underscores how critical on-going analysis is.

The global cryptographic community has provided an invaluable analysis throughout the NIST standardization process. Our white paper attempts to examine one metric, specifically IACR ePrint publications, to quantify this cryptanalytic effort.