David Ott (VMware Research) and Chris Peikert (University of Michigan) provided contributions to this post. 

On January 31-February 1, 2019, the Computing Community Consortium (CCC) held a workshop in Washington, D.C. to discuss research challenges associated with PQC migration entitled, “Identifying Research Challenges in Post Quantum Cryptography Migration and Cryptographic Agility.” Workshop organizers, David Ott (VMware) and Chris Peikert (University of Michigan), are pleased to announce the release of the final workshop report.

The implications of sufficiently powerful quantum computers for widely used public-key cryptography is well documented and increasingly discussed by the security community. Specifically, widely used RSA, ECDSA, ECDH, and DSA cryptosystems will need to be replaced by post-quantum cryptography (PQC) alternatives (also known as quantum-resistant or quantum-safe cryptography). Failure to transition before sufficiently powerful quantum computers are realized will jeopardize the security of public key cryptosystems which are widely deployed within communication protocols, digital signing mechanisms, authentication frameworks, and more.

To avoid this, NIST has actively led a PQC standardization effort since 2016, leveraging a large and international research community. While NIST’s standardization effort aims to determine which PQC algorithms are robust enough to provide suitable alternatives for the threat of quantum computers, that effort does not address the problem of migration from today’s widely deployed algorithms to future PQC alternatives across the diversity of computer systems that serve our society. The extensiveness of public key cryptography usage across the Internet means that an industry-wide migration to quantum safe cryptography standards (i.e., PQC) will be a massive undertaking, and one that is complicated by the layered complexity and heterogeneity of the worldwide compute infrastructure we operate.

CCC workshop discussion centered around two key themes: identifying constituent challenges in PQC migration and imagining a new science of “cryptographic agility.”

Key findings for PQC migration include:

• There is an important need for research to understand and quantify the implications of replacing today’s public cryptography algorithms (e.g., RSA, ECDH, ECDSA, DSA) with PQC alternatives across a wide variety of implementation and deployment contexts.
• Given that PQC algorithms generally have greater computation, memory, storage, and communication requirements (e.g., larger key sizes, more complex algorithms, or both), research and prototyping is needed to better understand performance, security, and implementation considerations.
• Research is needed on approaches to introducing new PQC algorithms (e.g., hybrids) within live systems that must remain interoperable with other systems during the period of massive industry migration. This includes such areas as formal modeling, automated tools, and approaching transition in complex infrastructures.

Key findings for cryptographic agility include:

• There is a need to broaden and recast traditional notions of cryptographic agility in light of the size and complexity of global PQC migration. A new science of cryptographic agility should include an expanded set of goals, a more comprehensive set of compute domains, a broader range of agility modalities and time scales, and the full range of security research methodologies.
• Research on cryptographic agility should include frameworks and architectures that enable agility across a wide variety of compute contexts, usable interfaces addressing various user roles, a better understanding of security and complexity tradeoffs, and other defining challenges.
• Context agility, or cryptographic frameworks that automatically select among algorithms and configuration based on the context of use, represents a long-term research vision that could shape the field.
• Cryptographic agility, independent of PQC migration, offers the benefit of making security systems more robust against algorithmic breakthroughs, revealed implementation flaws, emerging hardware accelerators, and other threats. It enables change in response to evolving security policy within an organization and support for new cryptographic features.
• In the context of PQC, it enables agility across multiple standards likely to be approved by NIST.

Additional findings include:

• Fundamental research is needed on policy, process, and people since these determine whether and when PQC adoption occurs at all.
• Research is needed on the frontiers of cryptography; that is, how PQC migration and cryptographic agility will apply to newer cryptography fields like secure multi-party computation, fully homomorphic encryption, blockchain, and more.

See the full report here to learn more.