Building Confidence in Quantum-Resistant Algorithms: How much analysis is needed?
February 25, 2021 | Cloud Security Alliance Blog
By Roberta Faux, BlackHorse Solutions, Inc.
This blog post was originally published on the Cloud Security Alliance website. The original post can be found here. NOTE: To download the full whitepaper, an e-mail address and some other information is required.
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 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.
The question remains: how much scrutiny do we need in order to have confidence in a quantum-resistant algorithm?
Roberta Faux, Director of Advanced Cryptography, BlackHorse Solutions
Roberta Faux is a research scientist with expertise in cryptography, algorithm design, and optimization. As the Director of Advanced Cryptography at BlackHorse Solutions, she orchestrates the development efforts on next-generation encryption with a focus on quantum resistant solutions and private AI. Ms. Faux is an active member of the Cloud Security Alliance Quantum-safe Security Working Group. With 12 years of signals intelligence and cryptanalytic experience for the US Department of Defense, she has experience creating sophisticated mathematical and computational techniques to provide analytic solutions for cyber-related problems, often in high-risk high-payoff environments. She has interacted across the US Intelligence Community, Department of State, US Trade Representative, Department of Commerce, Department of Energy, and in supporting the White House Interagency Policy Committee for the Cyber Task Force on Standards and Internet Governance. She is the recipient of numerous awards and honors. She holds a Master’s degree from the University of Colorado.
BlackHorse is a rapidly growing technology company in the national security space with leading capabilities in cyber, electronic warfare, digital operations, artificial intelligence/machine learning, information operations, readiness support, and full spectrum operations. Headquartered in Herndon, VA, and with offices in Tampa, FL, Fayetteville, NC, and Denver, CO, we support our nation’s most pressing national security needs through contracts with the Department of Defense, Intelligence Community, and other Government agencies. BlackHorse has openings in some of the most exciting areas of National Security, which can be found at https://www.blackhorsesolutions.com/. We can also be found on LinkedIn, Twitter, Facebook, and Instagram; follow us!