Compact Public Keys for Post-Quantum Code-Based Cryptography

This direction is split into other directions: key size optimization, public key size overhead. Its last version stays readable and citable here.

Version 1 of 137 papers45 conceptsfrozen 2026-10-04

The arrival of quantum computing threatens to break the number-theoretic foundations of modern security, such as RSA and ECC. While we have known of "quantum-resistant" alternatives for decades—most notably the McEliece cryptosystem—they suffer from a practical "bloat" problem. A standard RSA key might be a few kilobits; a secure McEliece public key can exceed a megabyte.

The central challenge in this research direction is shrinking these massive keys to make post-quantum cryptography (PQC) viable for resource-constrained environments like smart cards, IoT sensors, and mobile devices.

The Matrix Bloat Problem

In traditional code-based cryptography, the public key is typically a large, dense generator matrix of an error-correcting code. To encrypt a message, one multiplies it by this matrix and adds a specific amount of "noise" (errors). Decryption is only possible if you possess the secret "trapdoor"—the underlying structure of the code—that allows you to efficiently remove that noise.

As Yoshiyuki Kabashima, T. Murayama, and David Saad observed in Cryptographical Properties of Ising Spin Systems, these matrix-based systems face a fundamental scalability challenge. Unlike Elliptic Curve systems, which Yvonne Hitchcock and colleagues showed could be highly optimized for 32-bit smart cards, code-based systems require storing and transmitting hundreds of thousands of matrix coefficients.

This creates a frustrating trade-off. As Maryam Rajabzadeh Asaar and Mohammad Reza Aref detail in their work on short signature schemes, it is possible to produce very small signatures, but the public keys required to verify them often balloon to near 100 megabytes.

Strategy 1: Imposing Algebraic Structure

The most direct way to shrink a matrix is to make it "quasi-cyclic" or "quasi-dyadic." In a quasi-cyclic matrix, every row is a circular shift of the previous row. This means you only need to store the first row to reconstruct the entire matrix, slashing storage requirements by orders of magnitude.

Researchers have explored several code families to exploit this:

  • QC-LDPC and MDPC Codes: Hossein Khayami and Mohammad Reza Aref utilized Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) codes to reduce secret key sizes to 20% of previous benchmarks. Similarly, Jessalyn Bolkema and Joachim Rosenthal proposed using spatially coupled MDPC codes to thwart structural attacks while maintaining compactness.
  • Polar Codes: Reza Hooshmand and colleagues introduced PKC-PC, which replaces traditional Goppa codes with Polar codes, leveraging their unique recursive structure to reduce key sizes and improve transmission rates.

Strategy 2: Changing the Metric

Most code-based systems use the Hamming metric, which counts the number of positions in which two strings differ. However, the Hamming metric is "inefficient" for security; you need very long codes to make the decoding problem hard for an attacker.

Antonia Wachter-Zeh and her collaborators have pioneered the use of alternative mathematical metrics:

  • Rank Metric: In the rank metric, errors are viewed as matrices rather than vectors. Sven Puchinger and Julian Renner demonstrated that Twisted Gabidulin codes can achieve high security with significantly smaller public keys than Hamming-metric systems.
  • Cover Metric: Sebastian Bitzer and Violetta Weger established the theoretical foundation for the cover metric, proving that its decoding complexity grows exponentially with matrix dimensions, allowing for even more compact data representation.

Strategy 3: Advanced Code Selection

Beyond changing the metric or the structure, researchers are refining the specific classes of codes used within the classic McEliece framework. Luca Mariot, Stjepan Picek, and Radinka Yorgova showed that using punctured self-dual codes with large minimum weights can achieve a ~38.5% reduction in key size.

In a similar vein, Antonia Wachter-Zeh and Alexander Zeh introduced interleaved Goppa codes, which slash key sizes by up to 60% by utilizing "burst errors" to maintain security while reducing the required matrix dimensions.

Why It Works

The intuition behind all these approaches is the same: Information Density.

A random matrix is the least efficient way to represent a linear transformation because every entry must be stored individually. By choosing codes with inherent mathematical symmetries (like quasi-cyclic codes) or by moving to metrics where the "hard problem" is more complex for a given input size (like rank or cover metrics), researchers are increasing the amount of security "work" an attacker must do per bit of public key stored.

As Po‐Jen Chen and Tung Chou demonstrate with their FPGA implementation of Classic McEliece, even with optimized hardware, the fundamental memory requirement remains the primary bottleneck. Solving the key size problem is not just an optimization; it is the prerequisite for a quantum-secure internet.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_compact_public_keys_for_post_quantum_cod_2c25b56e,
  title = {Compact Public Keys for Post-Quantum Code-Based Cryptography},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compact-public-keys-for-post-quantum-code-based-cryptography/rdr_2c25b56ed640493c84f81e6476bdc6c6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_compact_public_keys_for_post_quantum_cod_2c25b56e_v1,
  title = {Compact Public Keys for Post-Quantum Code-Based Cryptography},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/compact-public-keys-for-post-quantum-code-based-cryptography/rdr_2c25b56ed640493c84f81e6476bdc6c6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}