Identifying Research Challenges in Post Quantum Cryptography Migration and Cryptographic Agility

• Research should quantify replacement implications across implementation and deployment contexts because PQC candidates generally require more computation, memory, storage, and communication.The resulting performance, security, and implementation considerations need further study.Source: Executive Summary · p. 4
• Live-system introductions, including hybrids, need research that preserves interoperability during industry migration, using formal modeling, automated tools, and approaches for complex infrastructures.Source: Executive Summary · p. 5
• Agility research should broaden its goals, compute domains, modalities, timescales, and methods, with frameworks and interfaces addressing security-complexity tradeoffs and adaptation to evolving threats and policies.Source: Executive Summary · p. 5
• Context agility—automatically selecting algorithms and configuration based on use context—is presented as a long-term research vision.Source: Executive Summary · p. 5
• The agenda calls for research on how policy, process, and people shape PQC adoption, and on applying migration and agility to newer fields such as secure multi-party computation, fully homomorphic encryption, and blockchain.Source: Executive Summary · p. 5

1.1 The Threat of Quantum Computing to Cryptography

• Shor’s algorithm threatens public-key systems based on integer factorization and discrete logarithms, prompting replacement of RSA, ECDSA, ECDH, and DSA with PQC alternatives.Grover’s algorithm also affects symmetric cryptography and hash functions, for which increasing key and output sizes is described as a well-understood response; the paper focuses on public-key replacement.Source: §1.1 · pp. 7–8

1.2 The Problem of PQC Migration: An Approaching Storm

• Replacing widely deployed public-key cryptography is a massive global migration across heterogeneous infrastructure, and previous cryptographic migrations have taken a decade or more.The infrastructure supports many Internet and private-network functions, and the paper notes that migrations such as RSA to ECC took a decade or more.Source: §1.2 · p. 9
• Migration needs lead time because quantum-computing timelines are uncertain, systems may lack drop-in replacements, and adversaries may retain encrypted long-lived data for later decryption.Research during NIST’s selection process could inform proposal evaluation and practical standards and parameter guidelines.Source: §1.2 · pp. 9–10

1.3 The Need for Research

• The 2019 CCC workshop brought cryptographers, applied cryptographers, and industry practitioners together to identify research challenges in PQC migration and cryptographic agility.Participants focused on applying candidate algorithms to contexts and securely realizing migration, as well as ongoing migration to new algorithms and standards.Source: §1.3 · p. 10
• Cryptographic agility generalizes PQC migration to ongoing updates as new attacks and better algorithms motivate changes to cryptographic standards.The paper describes agility frameworks as relevant to a wide variety of system, protocol, and application contexts.Source: §1.3 · p. 10

2. Core PQC Migration Challenges

• Obsoleting deprecated algorithms is difficult in entrenched deployments and frameworks that offer little or no support for phased retirement.PQC migration also differs from a drop-in replacement because algorithms can change key, ciphertext, signature, communication, memory, and computation requirements, and may require state management or entropy.Source: §2 · p. 11

2.1 PQC Algorithms: Charting Implications Across Domains

• Research must quantify how replacing RSA, ECDH, ECDSA, and DSA with PQC alternatives affects varied implementation and deployment contexts.The passage identifies secure communication, signatures, PKI, authentication, identity and access management, and key management as usage domains for exploration.Source: §2.1 · pp. 11–12
• PQC changes in computation and memory can affect implementation strategies, performance, buffering, communication patterns, and side-channel vulnerabilities.Additional requirements include state management for hash-based signatures, Gaussian sampling in lattices, entropy in lattice schemes, and nonzero decryption failure probabilities in code-based encryption.Source: §2.1 · pp. 11–12
• Software and hardware test environments can prototype and experimentally quantify PQC deployment effects across existing cryptography domains.NIST is unlikely to select a single replacement because algorithm trade-offs vary by device and usage context, and quantum-safe selection retains uncertainty.Source: §2 · p. 11, §2.1 · p. 12

Performance Considerations

• PQC’s greater computation, memory, storage, and communication requirements make performance a key industry concern for adoption across deployment contexts.The passage calls for better understanding and quantification of performance considerations.Source: Performance Considerations · p. 12
• Larger keys can alter packetization and latency in protocols such as TLS, affecting network devices optimized for current cryptography.The passage raises questions about implications for network function virtualization in 5G, end-user devices, and applications.Source: Performance Considerations · p. 12
• Optimization research could target algorithm bottlenecks through parallelism, memory-access data structures, or computation reorganized for the underlying architecture.IoT performance must account for compute, memory, and battery constraints.Source: Performance Considerations · p. 13
• FPGA research could explore accelerators for PQC memory and computation bottlenecks, while hardware primitives could inform instruction proposals.The passage points to the historical development of AES and SHA-2 hardware primitives as context.Source: Performance Considerations · p. 13

Security Considerations

• PQC candidates have less-understood trade-offs among configurable key size, ciphertext size, computation time, and scheme-specific parameters, creating a need to assess security against requirements across usage domains.The passage notes that NIST standards specific parameter settings, while guidance on algorithm and security-level selection across contexts and later parameter adjustments may also be needed.Source: Security Considerations · p. 13
• Cryptanalysis research should examine PQC threat models across protocol contexts, including underlying hardness assumptions, their mapping to implementations, practical attacks, and weak entropy sources.The passage describes cryptanalysis as investigating weaknesses under assumptions and adversary models and what it takes to break a scheme.Source: Security Considerations · p. 13
• New memory, timing, communication, cache, and failure patterns may expose PQC implementations to side-channel attacks across platforms from servers to IoT devices.The passage identifies timing, memory-based, differential fault analysis, and speculative execution attacks, and calls for work on possibilities and mitigations.Source: Security Considerations · p. 13

Implementation Considerations

• Data representation, memory hierarchy, and operating-system buffering can introduce vulnerabilities that are not apparent in cryptographic algorithm design.The difficulty extends beyond mathematical algorithm errors to translating algorithms into platform-specific architectures and device contexts.Source: Implementation Considerations · p. 13
• Research is needed on PQC implementation across a broad range of devices, computer architectures, system software stacks, and programming languages.The IoT domain combines cost sensitivity, physical exposure, hard-to-manage embedded interfaces, and insufficient vendor security incentives.Source: Implementation Considerations · pp. 13–14
• Embedded PQC implementations must address limited memory, compute, and power while investigating hardware-software boundaries and side-channel protection.The section also asks which PQC approaches and parameter choices are well- or poorly-matched to embedded devices.Source: Implementation Considerations · p. 14
• NIST PQC reference code is often not ready for industry use, motivating further optimization research and robust software libraries for platform-specific performance characterization.The passage gives Open Quantum Safe as an example of a library effort that could support experimentation.Source: Implementation Considerations · p. 14

2.2 Migration Frameworks: How will we get there?

• Hybrid schemes combine a current standard algorithm with a PQC alternative, easing transition while increasing computation, memory, communication, and other requirements.Participants noted migration may require two stages: moving to hybrids, then from hybrids to standalone PQC algorithms.Source: §2.2 · p. 14
• Research is needed on combiners and key derivation functions for hybrid deployment; prior combiner work had not, to the authors’ knowledge, been applied specifically to PQC algorithms.The cited discussion describes hash and encryption combiners as related research, not as established PQC solutions.Source: §2.2 · p. 14
• Migration frameworks need creative, rigorous research to support transitions without losing interoperability or functionality and to assess each approach’s attack surface and risk profile.The passage notes that practical schemes exist and are being discussed by standards bodies, but calls for more research across domains and platform types.Source: §2.2 · p. 15
• Legacy systems may lack migration mechanisms or field-upgrade options, raising questions about quantum-safe interaction with migrated systems and transparent migration frameworks.Examples include unsupported legacy IoT devices and system software that is no longer actively developed or supported.Source: §2.2 · p. 15
• Algorithm deprecation is difficult because legacy systems, outdated cryptographic libraries, and weak organizational security oversight can keep deprecated algorithms in use.The research question is how to design deprecation into migration so deprecated algorithms do not operate in perpetuity.Source: §2.2 · p. 15
• Migration timing research must account for dependencies across research, standards, hardware and software providers, libraries, system stacks, and certification frameworks.Participants suggested risk management as one possible part of investigating when migration should occur.Source: §2.2 · p. 15

Formal Modeling

• Formal methods could test whether hybrid, combiner-based, negotiation-based, or other migration schemes deliver their presumed security robustness.The section presents this as an open question despite industry’s ability to build such schemes.Source: Formal Modeling · p. 15
• For hybrid and combiner schemes, formal models should examine whether they introduce vulnerabilities relative to the strongest component and assess attack surfaces, misuses, implementations, and adversary assumptions.The questions span key encapsulation mechanisms, encryption schemes, and digital signatures.Source: Formal Modeling · p. 15
• Formal modeling is also needed to analyze migration frameworks inserted into protocols such as TLS, which could be divided into classical and quantum-resistant components for analysis.Other named protocol and application areas include Diffie-Hellman key exchange, PKI, IPSec, SSH, HTTPS, S/MIME, PGP, and VPNs.Source: Formal Modeling · p. 15

Automated Tools

• Automated tools are needed because cryptographic infrastructure is extensive and migration is described as nearly unachievable without them.The proposed research spans multiple spheres of migration work.Source: Automated Tools · p. 15
• Infrastructure scanning research could identify where public-key cryptography is used and which algorithms and versions are deployed across complex, dependency-rich organizations.Suggested active and passive sources include network traffic, open ports, devices, binaries, and source-code repositories.Source: Automated Tools · p. 16
• Automation could analyze migration mechanisms in protocols, specifications, and source code by tracing dependencies, identifying runtime control flow, probing vulnerabilities, and verifying libraries and mechanisms.The passage notes that application source code can be too large for manual scanning and too complex for programmer analysis.Source: Automated Tools · p. 16
• Automated testing research could develop tools to explore migration failure modes, synthesize migration and validation code, add test cases to developer toolchains, and modify legacy binaries.Source: Automated Tools · p. 16

Complex Infrastructures

• PQC migration challenges in complex infrastructures remain little studied; these environments combine architectural complexity with deeper software-stack layering and heterogeneity.Examples include private and public clouds, hybrid and federated architectures, edge computing, and smart homes or buildings.Source: Complex Infrastructures · p. 16
• Changing a cryptographic library at one stack layer may not suffice because certificates, keys, and network-security mechanisms can depend on other layers.Research is needed for mechanisms that reveal such cross-layer dependencies.Source: Complex Infrastructures · p. 16
• Infrastructure-level frameworks are needed to prioritize migration domains and dependencies, model whole-infrastructure migration, audit progress, establish end-to-end quantum-safety evidence, and address vulnerabilities.Source: Complex Infrastructures · p. 16
• Methods and tools do not currently exist to measure PQC migration across a geographic region of the Internet or the global Internet.Source: Complex Infrastructures · p. 16

2.3 Case Study: Authentication Using PQC

• At a 112-bit security level, NIST digital-signature standards DSA, RSA, and ECDSA use keys of 2048, 2048, and 224 bits, respectively.The passage notes that algorithms are generally fast and efficient, particularly ECDSA.Source: §2.3 · p. 16
• Multivariate signatures offer small signatures but require 500-700KB keys and substantially more computation for key generation and signing.Rainbow is given as an example.Source: §2.3 · p. 16
• Lattice-based schemes offer key sizes roughly equivalent to DSA and RSA but require significantly more computation for signatures.CRYSTALS-Dilithium is given as an example.Source: §2.3 · p. 17
• Hash-based signatures offer well-understood security under comparatively few assumptions, but stateful schemes require one-time secret keys and secure management of precomputed keys.Stateless alternatives such as SPHINCS+ avoid statefulness but have much larger keys.Source: §2.3 · p. 17
• The effects of larger stateless-scheme resource requirements and stateful key-management demands across authentication applications remain open questions.Participants considered stateful schemes a poor match for many distributed settings, resilience-focused contexts, hardware security schemes, and PKI certificates.Source: §2.3 · p. 17

3. A New Science of Cryptographic Agility

• Cryptographic agility should address architectures for ongoing migrations over time, rather than only transitions to a new set of standards.The paper argues that algorithm replacement within an implementation is too narrow a view and should be treated as a broader design challenge.Source: §3 · p. 18

3.1 Definitions, Goals, and Scope

• A principled agility science should broaden goals, compute domains, modalities, time scales, and research methods.Illustrative goals include effectiveness, measurability, interpretability, enforceability, security, and acceptable performance.Source: §3 · p. 18, §3.1 · p. 18
• Agility frameworks should span algorithm, code, protocol, application, service, system, infrastructure, cloud, and vertical-domain contexts.The paper also calls for research methods including formal analysis, hardware-software co-design, performance evaluation, and systems analysis.Source: §3.1 · p. 18

Frameworks

• Framework research should move beyond existing libraries, hybrids, and cipher-suite negotiation toward secure, auditable reconfiguration across varied contexts.Existing libraries still require manual developer integration; the paper identifies substantial room for approaches beyond the limited sampling represented by hybrids and negotiation.Source: Frameworks · pp. 19–20

Interfaces

• Agility interfaces need syntax and semantics amenable to formal security analysis, testing, and validation, with abstractions suited to different users and domains.The paper identifies limited existing work on interface design and user behavior across developers, administrators, manufacturers, and auditors.Source: Interfaces · pp. 20–21

Security and Complexity Tradeoffs

• Added agility complexity can create attack opportunities, including downgrade attacks and exposure to less secure suites or less-tested implementations.Research should examine attack surfaces and prevent schemes from enabling bad algorithms or malicious implementations.Source: Security and Complexity Tradeoffs · p. 21

Other Defining Challenges

• Agility research should identify system components for future reconfiguration, develop companion testing and validation, and address legacy systems lacking reconfiguration hooks.The proposed testing work includes automated tools for checking and enforcing agility design goals.Source: Other Defining Challenges · p. 21

3.2 Context Agility: A Research Vision

• Context agility would select algorithms and configurations according to use, including data sensitivity, location, regulation, device resources, and time scale.The paper also envisions self-configuring frameworks that recommend or audit configurations and respond to changing requirements.Source: §3.2 · p. 22

4.1 Policy, Process, People

• Policy and economic research should examine incentives for vendors and developers, including procurement, certification, customer pressure, and marketplace rewards.Cryptography work can be treated by development teams as overhead without product revenue, while PQC adoption timing varies among organizations and industries.Source: §4.1 · pp. 22–23
• Adoption research requires clearer technical definitions and metrics for cryptographic agility that industry can translate into actionable requirements.The paper notes that neither clear definitions nor associated evaluation metrics are currently available.Source: §4.1 · p. 23

4.2 Frontiers of Cryptography

• PQC migration and agility research should address emerging fields such as blockchain, MPC, FHE, and identity- or attribute-based encryption.Questions include how migration applies to these approaches and whether they can help provide agility or facilitate migration.Source: §4.2 · p. 23
• Blockchain migration raises questions about replacing legacy signatures, while blockchains or other schemes might provide distributed certificate ledgers or trust anchors.The passage notes that many techniques are not yet widely deployed and may therefore be agile with new features.Source: §4.2 · p. 24

5. Conclusions

• PQC migration research should quantify implementation and deployment implications, address resource demands, and develop interoperable transition approaches for live systems.The proposed work includes performance, security, and implementation analysis, formal modeling, and automated tools.Source: §5 · p. 25
• Cryptographic agility research should broaden its goals, domains, modalities, time scales, methods, frameworks, interfaces, and analysis of security-complexity tradeoffs.Context agility—automatic algorithm and configuration selection based on use context—is presented as a long-term research vision.Source: §5 · p. 25
• Social and policy research matters because people, process, and policy influence whether and when PQC adoption occurs.The conclusion raises incentives involving software developers, vendors, government, customers, and the Internet marketplace.Source: §5 · p. 25
• Research should examine how PQC migration and agility apply to newer cryptographic fields and whether those technologies can support migration.Examples named include secure multi-party computation, fully homomorphic encryption, and blockchain.Source: §5 · p. 25