Mapping the Post-Quantum Terrain
Quantum computers don’t threaten the Internet’s ability to move packets, but they do threaten the cryptographic properties that protocols layer on top of that movement. Confidentiality, authentication and integrity all rest on mathematical problems a sufficiently powerful quantum machine could dissolve. The fix is well understood in principle: replace vulnerable algorithms with post-quantum cryptography. The hard part is everything around that replacement.
A useful way to organize the work ahead is to sort the challenges into five broad kingdoms, borrowing the biological metaphor of classification. These kingdoms — protocols, implementations, standards, community, and research — overlap and feed into one another, but each has its own set of questions that need answers before a post-quantum Internet can become a practical reality.
Protocolla: Where Sizes and Speeds Collide
The protocols that secure the Internet — IPsec, WireGuard, TLS, QUIC, DNSSEC, SSH — are built to deliver confidentiality, authentication and integrity under specific constraints. Those constraints include packet sizes, segment sizes and handshake latency budgets. Adding post-quantum algorithms is theoretically unproblematic; practically, it runs into hard limits.
Consider TCP’s Maximum Segment Size (MSS). IPv4 hosts must handle an MSS of 536 bytes, IPv6 hosts 1220 bytes. DNS over UDP limits answers to 512 bytes without EDNS. Many post-quantum keys, signatures and certificates blow well past those bounds, forcing fragmentation or extra round trips. On the computational side, some lattice-based KEMs perform comparably to fast elliptic-curve cryptography in key exchange experiments, but the public keys themselves are much larger and can enable denial-of-service attacks if a server is forced to store or process many of them.
For TLS, the key exchange phase is the most urgent update, since traffic recorded today could be decrypted later by a quantum computer. The 2019 Cloudflare-Google experiment demonstrated that hybrid lattice-based KEMs can be added to TLS handshakes with minimal performance impact. But the authentication phase is harder. Post-quantum signature algorithms under consideration at NIST produce significantly larger signatures and public keys than classical ones, and their computation times are higher. Even when large signatures fit inside a TCP congestion window, the slowdown can still reach double-digit percentages at average Internet speeds. The ideal early-adoption scenario would see the six signatures and two public keys of a TLS handshake fit within 9kB.
Alternative approaches exist. Certificate-based authentication can be achieved with KEMs instead of signatures. This mechanism, called KEMTLS, adds half a round trip for server-only authentication and a full round trip for mutual authentication, but it performed well in controlled experiments. Delegated credentials allow a server to advertise post-quantum algorithms without changing the entire certificate chain, which may involve actors beyond the server’s control.
Middleboxes add another layer of complication. Some assume the first handshake message from a browser fits in a single packet, an assumption that breaks with larger post-quantum parameters. This is protocol ossification, the same problem TLS 1.3 had to work around carefully, and it is not unique to post-quantum cryptography.
Implementa: From Algorithm to Deployment
Widespread deployment of post-quantum cryptography requires more than standardization. Algorithms need to be efficient at the algorithmic level, in software, and in hardware; they need to avoid side-channel attacks; and they need practical APIs that developers can adopt.
Lattice-based KEMs have made significant progress in closing the speed gap with elliptic-curve cryptography, though their larger parameters create inefficiencies at the protocol level. Isogeny-based schemes remain slow due to expensive isogeny evaluations, though they attracted active research. Hash-based signatures such as XMSS are already usable for specific applications.
The implementation challenges are extensive:
- Making algorithms fast enough for protocol requirements via software optimization, hardware acceleration, or entirely new approaches like Falcon’s use of floating-point arithmetic, which introduces architecture-dependent portability concerns
- Understanding asymptotic complexity in both time and space
- Supporting embedded devices with limited capacity
- Ensuring constant-time execution to prevent side-channel attacks
- Providing robust testing and avoiding security-proof failures or API misuse
- Planning for disaster recovery when an algorithm is weakened or broken, including transition paths to stronger replacements
Open-source libraries like Cloudflare’s CIRCL, which ships high-speed assembly implementations of Kyber, Dilithium, SIKE and CSIDH, are one attempt to ease the transition for developers integrating post-quantum algorithms into their projects.
Regulae: The Standardization Bottleneck
Post-quantum cryptography rests on mathematical foundations that are unfamiliar to much of the engineering community. That makes the standardization process harder. Standards bodies like NIST and the IETF need to evaluate security claims against novel adversary models, such as the Quantum Random Oracle Model, and decide whether to recommend hybrid approaches that combine classical and post-quantum algorithms.
A recurring concern is how to bring the academic research community into the standardization process early enough to catch flaws before deployment at scale. The TLS 1.3 experience is a positive example: formal verification experts helped bridge the gap between academic analysis and practical standard design. The same kind of collaboration is needed for post-quantum cryptography, where trade-offs between theoretical rigor and practical deployability are more acute.
Comunitates: The Human and Systemic Layer
The Internet is a community of operators, vendors, standards bodies and end users. Migrating to post-quantum cryptography requires coordinated action across all of them, even though each system and each protocol may have unique constraints that are not fully known outside a small group of experts.
The community questions are practical and political as much as technical:
- When and how will migration be coordinated across the PKI and other critical infrastructure?
- How will the need for change be communicated to end users?
- How will pre-quantum cryptography be deprecated without breaking existing systems?
- How do you update IoT devices where algorithms are hardcoded at manufacturing time?
- Who will maintain a diverse set of interoperable post-quantum implementations, and is there funding and incentive to do so?
Beyond integration work, foundational research questions remain open. There are no efficient, secure post-quantum non-interactive key exchange (NIKE) schemes. Diffie-Hellman is the canonical NIKE, but its lattice-based successors do not yet meet both efficiency and security requirements. CSIDH is a candidate but is slow and its security is debated. Similarly, post-quantum replacements are lacking for protocols built on oblivious pseudorandom functions, such as Privacy Pass and OPAQUE, and for threshold signatures and credential-based signatures. Formal verification of post-quantum algorithms under new security notions like the QROM is also an unresolved challenge.
Looking Ahead
The past several years of experiments — wide-scale handshake tests, KEMTLS trials, large-signature emulations — have produced useful data on where post-quantum cryptography can fit with acceptable impact. Still missing are tests across broader networks and different architectural environments. The next phase is a larger, wide-scale deployment effort to see how post-quantum algorithms behave under real-world conditions.
Several threads will occupy this work in the coming period:
- The evolution of quantum research and its effects on post-quantum efforts
- Detailed explanations of KEMs, signatures and their security properties
- Protocol integration strategies for post-quantum algorithms
- The role of formal verification, analysis and implementation in the transition
- Practical case studies from making systems like Cloudflare Tunnel and Gokeyless post-quantum
