Key Size Reduction in Code-Based Cryptography

22 concepts23 papers1 proposal

Code-based cryptosystems, such as the classic McEliece scheme, are among the most trusted candidates for post-quantum security. Their security relies on the hardness of decoding a random linear code, a problem that has resisted quantum algorithmic speedups for decades. However, they suffer from a severe practical bottleneck: prohibitively large public keys.

While a standard RSA or elliptic-curve public key requires only a few bits or kilobytes, a secure code-based public key typically requires hundreds of kilobytes to megabytes of storage. This overhead creates a massive barrier to adoption in resource-constrained environments, high-traffic networks, and standard communication protocols.

To understand why these keys are so large—and how modern research is shrinking them—we must look at how code-based cryptography hides information, and how researchers are using algebraic symmetry, alternative metrics, and collaborative decoding to compress this data.


The Information-Theoretic Cost of Security

In a classic McEliece cryptosystem, the private key is an error-correcting code (traditionally a Goppa code) that possesses an efficient decoding algorithm capable of correcting up to $t$ errors. The public key is a scrambled version of this code's generator matrix, $G$.

To make the public key look like a completely random linear code to an attacker, the matrix is typically transformed into systematic form:

$$G_{\text{pub}} = [ I_k \mid P ]$$

Here, $I_k$ is a $k \times k$ identity matrix, and $P$ is a dense, unstructured-looking $k \times (n-k)$ matrix. The matrix $P$ serves as the actual public key. For strong post-quantum security, $k$ and $n$ must be large integers (often where $n$ is several thousand bits). Because $P$ contains no apparent patterns, every single bit of this $k \times (n-k)$ matrix must be transmitted and stored. As noted by Wachter-Zeh et al. and Porwal et al., this requirement forces public keys to scale to sizes that overwhelm constrained hardware and bandwidth.

To solve this, researchers focus on a core challenge: How can we introduce structural patterns into $P$ to compress its size without giving an attacker a foothold to break the encryption?


Compressing Matrices via Algebraic Symmetry

The most direct way to shrink the public key is to force the matrix $P$ to be highly redundant. If a large matrix can be completely reconstructed from just a few rows or columns, the storage footprint drops dramatically.

Quasi-Cyclic and Quasi-Dyadic Structures

One elegant approach is to construct codes using matrices composed of smaller, symmetric blocks. For example, a quasi-cyclic matrix is made of blocks where each row is a right-shift of the row above it. If a block is defined entirely by its first row, we only need to store that single row.

Misoczki advanced this concept by introducing quasi-dyadic Goppa codes. Dyadic matrices feature a symmetric, recursive bit-pattern that allows a massive matrix to be represented by a fraction of its elements. By enforcing this dyadic structure on the underlying Goppa code, the public key size is drastically reduced while preserving the core decoding mechanics.

Moderate Density Parity-Check (MDPC) Codes

Taking structural compression a step further, Misoczki et al. proposed QC-MDPC (Quasi-Cyclic Moderate Density Parity-Check) codes. Instead of relying on the rigid algebraic structure of Goppa codes, MDPC schemes use a parity-check matrix that is sparse (containing a moderate number of 1s).

Because the matrix is quasi-cyclic, the entire public key can be compressed down to just the first row of each circulant block. This shift reduces the public key from hundreds of kilobytes to a few kilobytes, achieving a footprint comparable to traditional non-quantum public keys.


Shifting Metrics from Hamming to Rank

Another foundational strategy alters how we measure "distance" within the code. Traditional code-based cryptography operates in the Hamming metric, where the weight of an error vector is simply the number of non-zero coordinates.

Alternatively, we can use the Rank metric. Here, codewords and errors are treated as matrices over a base field $\mathbb{GF}(q)$, or as vectors over an extension field $\mathbb{GF}(q^m)$. The weight of an error is defined as the rank of its matrix representation.

Hamming Metric:  [ 1, 0, 1, 1, 0 ]  --> Weight = 3 (Count of non-zero elements)

Rank Metric:     | 1  0  1 |
                 | 0  1  1 |        --> Weight = 2 (Rank of the matrix)
                 | 1  1  0 |

As surveyed by Bartz et al., rank-metric codes (such as Gabidulin codes) offer a massive structural advantage: an attacker attempting to decode a random rank-metric code faces a problem that is structurally harder per bit than the equivalent Hamming-metric problem. Consequently, designers can achieve identical security margins using much shorter code lengths ($n$) and smaller fields.

By exploiting this efficiency, Renner et al. successfully repaired the Faure-Loidreau cryptosystem. They demonstrated that by structuring the public key to intentionally defeat structural interleaving attacks, rank-metric systems can deliver highly secure, compact post-quantum keys that bypass the scaling limitations of traditional Goppa-based McEliece systems.


Amortizing Overhead with Interleaved Codes

If compressing the matrix itself is not enough, can we get more utility out of the same public key? This is the intuition behind interleaved codes.

Interleaving involves taking multiple distinct messages and encoding them such that they are transmitted together and share the exact same error positions.

$$\text{Transmission Matrix } Y = \begin{pmatrix} — \text{ Codeword 1 } — \\ — \text{ Codeword 2 } — \\ — \text{ Codeword } s — \end{pmatrix} + \begin{pmatrix} \star & 0 & \star & 0 \\ \star & 0 & \star & 0 \\ \star & 0 & \star & 0 \end{pmatrix} \leftarrow \text{Shared Error Positions}$$

For an attacker, solving this problem remains incredibly difficult; in fact, Porwal et al. developed the "Interleaved Prange" decoder specifically to map out these exact security boundaries and prove that the underlying problem remains hard.

However, for the legitimate receiver, this shared error structure unlocks collaborative decoding. Because the errors occur in the same slots across all parallel codewords, a receiver can look at the cross-correlations between the received streams to pinpoint and correct significantly more errors than would be possible if decoding each codeword independently.

By increasing the error-correcting capacity ($t$) through collaborative decoding, the system can use smaller code parameters to secure the same amount of data. Holzbaur et al. applied this technique to Goppa codes, demonstrating public key size reductions of up to 45%. Similarly, Renner et al. extended interleaving to Loidreau’s rank-metric cryptosystem, compounding the key-shrinking benefits of both the rank metric and collaborative decoding.


Squeezing Efficiency from Decoding Bounds

Finally, researchers can shrink keys by optimizing the mathematical boundaries of the decoding process itself. If a decoder can handle a higher density of errors, designers can shrink the size of the generator matrix without dropping below the target security threshold.

  • List Decoding: Traditional decoders stop working if an error radius is too large because the received vector might map to two different valid codewords. Barbier et al. bypassed this by utilizing list decoding. Instead of demanding a single unique output, the decoder generates a small list of potential decryptions, which can then be easily filtered. This expanded error-correction capacity allows the system to use smaller public keys (up to 21% smaller) while maintaining robust security.
  • High-Distance Self-Dual Codes: Another path involves altering the code family entirely. Mariot et al. explored using punctured self-dual codes with large minimum weights. Because these codes possess an optimized geometric distribution of codewords, they maximize the security return per matrix entry, yielding a 38.5% reduction in public key size for equivalent security baselines.

By combining these mathematical optimizations—compressing matrices via algebraic symmetry, migrating to the rank metric, and leveraging collaborative interleaved decoding—modern code-based cryptography is successfully shedding its storage overhead, transforming a historically bloated quantum-resistant theory into a practical reality for modern networks.

Key Foundational Work

Key reduction of McEliece's cryptosystem using list decoding (2011) — contributed 2 concept elements to this direction.
Compact McEliece Keys from Goppa Codes (2009) — contributed 2 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_public_key_size_overhead_8dd7fc64,
  title = {public key size overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/public-key-size-overhead/rdr_8dd7fc645a4b41078e89e1aa9f4c34dc},
  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_public_key_size_overhead_8dd7fc64_v1,
  title = {public key size overhead},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/public-key-size-overhead/rdr_8dd7fc645a4b41078e89e1aa9f4c34dc/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake