Overcoming Payload Overhead in Post-Quantum Cryptography

41 concepts34 papers2 proposals

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.

3. Distributed Ledgers and Data Centers

For blockchains and high-throughput data centers, payload size translates directly to operational cost.


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

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.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_cryptographic_payload_overhead_dd03be84,
  title = {cryptographic payload overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/cryptographic-payload-overhead/rdr_dd03be84038c47c2871272ba85a5bc52},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_cryptographic_payload_overhead_dd03be84_v1,
  title = {cryptographic payload overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/cryptographic-payload-overhead/rdr_dd03be84038c47c2871272ba85a5bc52/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake