The implications of sufficiently large quantum computers for widely used public-key cryptography is well documented, and increasingly discussed by the security community. An April 2016 report by the National Institute of Standards and Technology (NIST), notably, calls out the need for new standards to replace cryptosystems based on integer factorization and discrete logarithm problems, which have been shown to be vulnerable to Shor’s algorithm. Specifically, widely used RSA, ECDSA, ECDH, and DSA cryptosystems will need to be replaced by post-quantum cryptography (PQC, also known as quantum-resistant cryptography) alternatives. To realize this, NIST has actively led a PQC standardization effort since December of 2016, leveraging a large and international research community.  The effort is expected to take five or more years to vet proposals, and to select alternatives that are believed to be secure against both quantum and classical computers.

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. There are some important reasons why this migration problem has urgency to many industries and governments worldwide: risk stemming from an uncertain quantum computing development timeline, the time and complexity of migration (historically, cryptographic standards migrations can take a decade or more), concern over the possibility of “data vaulting” (in which an adversary captures encrypted data for later attack when quantum computers become available), and the likelihood that migration considerations will inform NIST’s evaluation of PQC proposals.

The overall objective of this workshop was to identify academic research challenges in PQC migration and cryptographic agility.  That is, organizers wanted to identify aspects of the complex and global migration to new public-key cryptography standards that could benefit from a more rigorous study and analysis.  The technical space broadly centered around two key themes:

1. Identifying constituent challenges in PQC migrationWhile the NIST PQC standardization effort looks in depth at cryptographic algorithms, workshop organizers believe there is a rich space of challenges to be addressed surrounding the application of candidate algorithms to specific contexts and understanding how migration will be accomplished.

   How well do PQC families and specific approaches “fit” or “not fit” a broad range of public-key cryptography usage domains–PKI, key management systems, authenticated web communication (TLS), secure point-to-point communication (SSH), transport security (IPSec), key agreement, identification and authentication, password authenticated key exchange (PAKE), and more? For each domain and platform type, what migration approaches will support the transition to new PQC algorithms without loss of interoperability and functionality during the transition period?  What is the attack surface and risk profile associated with each approach? Can these approaches be shared across platforms and application contexts to develop migration frameworks? Are there frameworks that can be applied transparently to protocols or systems that lack inherent migration mechanisms?

2. Reimagining the scope and science of “cryptographic agility”While “cryptographic agility” is frequently seen as a narrow implementation concern (i.e., the ability to replace component algorithms), we believe there is a need to broaden and recast the scope of agility to that of developing secure frameworks that enable ongoing cryptographic advancements in a wide variety of system, protocol, and application contexts.

   Could there be a principled science of cryptographic agility that more rigorously considers a broad spectrum of frameworks, a robust analysis of correctness and security, a deeper understanding of attack surfaces, and an exploration of domain-specific (e.g., protocol, application, system) issues? What does it mean for an algorithm, a piece of code, a protocol, an application, a system, an entire infrastructure to be cryptographically agile?  What are the defining challenges, problem domains, and applications of cryptographic agility, broadly defined?

To discuss these challenges, the workshop brought together researchers and thought leaders from three distinct communities: PQC researchers who are involved in the design and analysis of cryptographic algorithms, applied cryptography researchers who focus more extensively on the application and implementation of cryptography to a variety of spheres, and systems security researchers who use cryptography as a building block in real-world security architectures and solutions (e.g., trusted computing, cloud security).