The impending arrival of cryptanalytically relevant quantum computers has forced a fundamental rewrite of the internet's cryptographic foundation. Traditional asymmetric primitives like RSA and Elliptic Curve Cryptography (ECC) rely on the hardness of factoring integers and computing discrete logarithms—problems that Shor’s algorithm solves in polynomial time. As detailed by Vasileios Mavroeidis et al. in The Impact of Quantum Computing on Present Cryptography, the industry is migrating toward Post-Quantum Cryptography (PQC), primarily anchored in lattice-based, code-based, and hash-based mathematical structures.
However, this transition introduces a severe physical challenge: cryptographic payload overhead. While an ECC public key or signature fits neatly into a few dozen bytes, quantum-resistant alternatives require kilobytes to megabytes of data. This article explores why PQC primitives are inherently bulky, how this bloat disrupts existing hardware and network architectures, and the algorithmic strategies researchers are deploying to shrink the post-quantum data footprint.
The Root of the Bloat: Why PQC is Large
To understand why post-quantum payloads are so massive, we must look at their underlying mathematical machinery. Classical cryptography operates over compact algebraic groups where a single scalar or curve point yields high security. In contrast, quantum-resistant algorithms rely on high-dimensional geometric or combinatorial structures.
Lattice-Based Cryptography
Algorithms based on the Learning With Errors (LWE) problem or its ring-based variant (RLWE) hide secrets within high-dimensional lattices perturbed by random noise. A public key is not a single number, but a large matrix or a set of high-degree polynomials. As Wei Dai et al. note in Implementation and Evaluation of a Lattice-Based Key-Policy ABE Scheme, these matrix-vector operations inherently demand substantial memory and computational bandwidth. Instead of transmitting a 32-byte coordinate, a lattice-based protocol must transmit thousands of polynomial coefficients, ballooning public keys and ciphertexts to kilobytes.
Code-Based and Hash-Based Cryptography
Code-based schemes rely on the hardness of decoding random linear codes, requiring the transmission of large generator matrices. Hash-based signature (HBS) schemes, while structurally simple and relying on minimal security assumptions, construct signatures out of verification paths within Merkle trees. As explained by Sabah Suhail et al. in On the Role of Hash-Based Signatures in Quantum-Safe Internet of Things: Current Solutions and Future Directions, an HBS signature must bundle numerous one-way function evaluations and commitment openings, making the resulting payload significantly larger than traditional signatures.
The Architectural Breaking Points
This payload expansion is not merely an efficiency concern; it threatens to break the hardcoded assumptions of modern computing infrastructure.
Classical (ECC) [ 64 Bytes ] -> Fits in a single network packet / hardware buffer
Post-Quantum [ ==== Kilobytes to Megabytes ==== ] -> Causes fragmentation & buffer overflows
1. Network Protocol Violations
Many internet protocols were designed with hardcoded buffer limits optimized for classical cryptography. In a large-scale network study, Jakub K. Sowa et al. demonstrated in Post-Quantum Cryptography (PQC) Network Instrument: Measuring PQC Adoption Rates and Identifying Migration Pathways that PQC keys and signatures can easily exceed the maximum transmission unit (MTU) of standard network packets or the maximum allowed size of HTTP headers. When a cryptographic payload spans multiple packets, it triggers IP fragmentation, increasing packet loss, handshake latency, and causing legacy middleboxes or specialized applications to drop the traffic entirely.
2. Embedded Devices and Hardware Tokens
Resource-constrained environments like Internet of Things (IoT) devices and hardware security keys (e.g., FIDO tokens) operate under strict memory and power envelopes.
- Transmission Limits: Diana Ghinea et al. in Hybrid Post-Quantum Signatures in Hardware Security Keys highlight that large signatures can exceed the physical payload capacities of communication interfaces like Near Field Communication (NFC) or USB.
- Storage and Energy: In To Attest or Not to Attest, This is the Question - Provable Attestation in FIDO2, Nina Bindel et al. emphasize that constrained hardware faces severe storage bottlenecks when managing PQC primitives. Furthermore, transmitting these bloated payloads over low-power wide-area networks forces radio components to remain active longer, rapidly draining battery reserves.
3. Distributed Ledgers and Data Centers
For blockchains and high-throughput data centers, payload size translates directly to operational cost.
- Blockchain Bloat: Distributed ledgers require permanent on-chain storage of signatures for transaction verification. Zhen Liu 0008 et al. in Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Key and Maxime Buser et al. in A Survey on Exotic Signatures for Post-quantum Blockchain: Challenges and Research Directions warn that transitioning to PQC imposes a massive "storage tax." Kilobyte-sized signatures expand the unspent transaction output (UTXO) set, leading to rapid blockchain bloat that threatens decentralization by pricing out smaller node operators.
- Bandwidth Saturation: Even in high-performance environments, large payloads introduce bottlenecks. As Marcos K. Aguilera et al. observe in DSig: Breaking the Barrier of Signatures in Data Centers, high-speed cryptographic schemes that optimize for computational speed often trade off signature size, resulting in payloads that saturate network bandwidth and offset any latency gains achieved by fast execution.
Algorithmic and Structural Solutions
To make PQC deployable, researchers are attacking payload overhead from multiple angles: information theory, combinatorial constraints, and structural optimizations.
Information-Theoretic Compression
One direct way to shrink payloads is to eliminate mathematical redundancy within the keys and ciphertexts themselves. In Reducing Ciphertext and Key Sizes for MLWE-Based Cryptosystems, Antonia Wachter-Zeh and Georg Maringer modeled the encryption-decryption loop of Module Learning With Errors (MLWE) cryptosystems—such as Kyber—as a noisy communication channel. By applying information-theoretic bounds, they demonstrated that public keys and ciphertexts can be compressed by 25% to 39% without degrading the system's underlying quantum security, proving that existing standards still contain compressible slack.
Constraining the Mathematical Puzzle Space
In code-based cryptography, signatures are often derived from zero-knowledge proofs of a syndrome decoding problem. To minimize the size of these proofs, Marco Baldi et al. introduced the Restricted Syndrome Decoding Problem (R-SDP) in Zero Knowledge Protocols and Signatures from the Restricted Syndrome Decoding Problem. By restricting the error vectors in the cryptographic puzzle to specific algebraic subsets or subgroups, the authors significantly reduced the amount of data required to represent the proof, yielding post-quantum signatures as small as 7.2 kB.
Logarithmic Scaling and Zero-Knowledge Optimizations
Advanced cryptographic applications, such as ring signatures and group signatures, traditionally suffer from linear payload growth relative to the number of users or time periods. Researchers are leveraging optimized zero-knowledge arguments to alter this scaling behavior.
Linear Scaling (Traditional PQC): O(N) --> Signature grows with group size N
Logarithmic Scaling (Optimized ZK): O(log N) --> Signature stays compact as N grows
- Logarithmic Accumulators: Benôıt Libert et al. in Zero-Knowledge Arguments for Lattice-Based Accumulators: Logarithmic-Size Ring Signatures and Group Signatures Without Trapdoors redesigned how Merkle tree hash chains are handled within Stern’s zero-knowledge protocol. This structural shift achieved the first lattice-based ring signatures that scale logarithmically with the ring size, drastically reducing the data footprint for privacy-preserving transactions.
- Eliminating Corrector Values: In Efficient and Post-Quantum Zero-Knowledge Proofs for Blockchain Confidential Transaction Protocols, Bin Xiao et al. optimized lattice-based zero-knowledge proofs by replacing costly binary proofs with an "unbalanced linear sum" approach. By eliminating the need for bulky "corrector values" in balance proofs, they sliced proof sizes by up to 50%.
Architectural Offloading
When algorithmic compression is insufficient, researchers look to infrastructure modifications. For instance, mutual authentication requires both the client and server to exchange large PQC credentials. To alleviate this on resource-constrained clients, Jane Kim et al. proposed ExpressPQDelivery : Toward Efficient and Immediately Deployable Post-Quantum Key Delivery for Web-of-Things. Their system offloads the storage and transmission of large post-quantum keys to the existing, geographically distributed DNS infrastructure, reducing handshake latency without modifying the core internet protocols.
Conclusion
The transition to post-quantum cryptography is fundamentally a trade-off between mathematical complexity and physical payload size. As the community moves from theoretical design to real-world deployment, managing the cryptographic payload overhead has become as critical as ensuring algorithmic security. Through a combination of information-theoretic compression, tighter mathematical constraints, and optimized zero-knowledge proofs, modern research is successfully shrinking the post-quantum footprint—ensuring that the quantum-safe internet remains a fast and scalable one.
Key Foundational Work
Fast Discretized Gaussian Sampling and Post-quantum TLS Ciphersuite (2017) — contributed 1 concept elements to this direction.
Implementation and Evaluation of a Lattice-Based Key-Policy ABE Scheme (2017) — contributed 1 concept elements to this direction.
Signature Schemes with Efficient Protocols and Dynamic Group Signatures from Lattice Assumptions (2016) — contributed 1 concept elements to this direction.