Code-based cryptography is one of the most enduring candidates for post-quantum security. Cryptosystems like the classic McEliece scheme rely on a simple, elegant premise: decoding a generic linear code with intentional errors is computationally hard. However, this security comes at a steep price. The public key in a standard McEliece system is a large generator matrix $G$. To prevent attackers from solving the underlying decoding problem, this matrix must be massive—often requiring hundreds of kilobytes or even megabytes of storage. This footprint creates a severe bottleneck for real-world network protocols and memory-constrained devices.
To make code-based cryptography practical, researchers have developed techniques to shrink these public keys. These approaches fall into three main categories: structural compression (forcing the matrix to possess algebraic symmetries), algorithmic leverage (using advanced decoding techniques to tolerate more errors per unit of code length), and alternative metrics (shifting from the traditional Hamming distance to rank-metric spaces).
Structural Compression: Quasi-Cyclic and Quasi-Dyadic Symmetries
The most direct way to shrink a matrix is to ensure that its rows are not independent, random sequences, but are instead deterministic permutations of a much smaller set of vectors. If a matrix can be reconstructed entirely from a few seed vectors, the public key only needs to store those seeds.
Quasi-Cyclic Configurations
In a quasi-cyclic code, the generator matrix is composed of blocks where each row is a right-cyclic shift of the row above it. As a result, storing the first row of each block is sufficient to reconstruct the entire block.
Misoczki et al. applied this principle by integrating Moderate Density Parity-Check (MDPC) codes with quasi-cyclic configurations. Because the parity-check matrices of MDPC codes have a somewhat sparse distribution of ones, they can be decoded efficiently using bit-flipping algorithms. By forcing these matrices to be quasi-cyclic, the authors drastically compressed public key sizes down to a few thousand bits for standard security levels, while maintaining fast decryption times (under three milliseconds on standard processors).
Quasi-Dyadic Configurations
An alternative to cyclic shifts is dyadic symmetry, where matrix blocks are defined by dyadic permutations (often related to Walsh-Hadamard matrices).
Quasi-Cyclic Block (Shifted):
[ a b c d ]
[ d a b c ]
[ c d a b ]
[ b c d a ] -> Only store [a, b, c, d]
Quasi-Dyadic Block (Permuted):
[ a b c d ]
[ b a d c ]
[ c d a b ]
[ d c b a ] -> Only store [a, b, c, d]
Misoczki demonstrated that constructing McEliece keys using a specific subclass of Goppa codes—quasi-dyadic Goppa codes—achieves public keys that are smaller than generic Goppa codes by a factor roughly equal to the number of correctable errors ($t$). This optimization brings code-based key sizes much closer to traditional RSA keys.
To expand this utility to digital signatures, Barreto et al. modified the quasi-dyadic code generation algorithm for Courtois-Finiasz-Sendrier (CFS) signatures. By relaxing a stringent condition in the original quasi-dyadic construction, the authors achieved a higher density of decodable syndromes. This modification yielded up to a 4x reduction in public key size, making the highly compact CFS signature variant far more practical.
Algorithmic Leverage: Boosting Error Capacity to Shrink Codes
The size of a code-based public key is intrinsically tied to the code's length ($n$) and dimension ($k$). To maintain security against information-set decoding (ISD) attacks, the number of intentional errors ($t$) added during encryption must remain high. Under traditional unique decoding algorithms, correcting more errors requires a longer code, which quadratically expands the size of the generator matrix ($k \times n$).
However, if the receiver can deploy a more powerful decoding algorithm that corrects more errors for the same code length, the system designer can shrink $n$ and $k$ while maintaining the same security margin.
Traditional Unique Decoding:
[ Shorter Code Length (n) ] ---> Can only correct few errors (t) -> Vulnerable to attacks
[ Longer Code Length (n) ] ---> Corrects enough errors (t) -> Secure, but massive key size
Advanced Decoding (List/Collaborative):
[ Shorter Code Length (n) ] ---> Corrects MORE errors (t) -> Secure AND compact key size
List Decoding
Traditional decoders stop searching once they find a single codeword within a radius $t$ of the received vector. List decoding relaxes this constraint: it allows the decoder to output a small list of potential codewords.
Barbier et al. applied list decoding to the McEliece cryptosystem, enabling the correction of an error count that exceeds the traditional unique decoding bound. This expanded error-correcting capacity allows the underlying code to be significantly shorter. The authors demonstrated up to a 21% reduction in public key size for the dyadic variant of McEliece. The trade-off for this structural efficiency is an increase in computational overhead, as the recipient must spend more time processing the candidate list during decryption.
Interleaved Codes and Collaborative Decoding
Another way to break past the unique decoding barrier is to transmit multiple codewords in parallel such that they share the same error positions. This is known as interleaving.
Holzbaur et al. designed a collaborative decoding algorithm for interleaved Goppa codes. Because the decoder looks across multiple parallel instances simultaneously, it can resolve error patterns that would defeat a single-code decoder. By implementing this collaborative framework within the McEliece cryptosystem, the authors reduced public key sizes by up to 45% for standard security levels.
High-Distance Codes and Alternative Metrics
Instead of compressing standard codes or changing the decoder, some approaches alter the underlying mathematical structure of the code itself to optimize the relationship between code length and error capacity.
High-Distance Self-Dual Codes
Self-Dual codes are linear codes that are equal to their own duals. When these codes are engineered to have exceptionally large minimum distances, they offer an inherently higher error-correction capacity relative to their length.
Mariot et al. proposed integrating binary self-dual codes with high minimum distances into McEliece-type cryptosystems. Because these codes can handle a higher density of intentional errors during encryption, they allow the system to use much smaller generator matrices. In subsequent work, Mariot et al. demonstrated that a punctured version of a newly constructed self-dual code of length 1064 achieves a 38.5% reduction in public key size at equivalent security levels compared to traditional Goppa codes, offering a viable alternative for bandwidth-constrained environments.
Rank-Metric Cryptography
Traditional code-based cryptography operates under the Hamming metric, where the weight of an error is the number of altered coordinates. Rank-metric cryptography, by contrast, treats codewords as matrices over a base field, and the weight of an error is defined as the rank of the error matrix. This metric shift fundamentally alters the underlying combinatorial bounds, allowing for much smaller keys.
- Interleaved Rank-Metric Schemes: Renner et al. combined interleaving with Loidreau's rank-metric cryptosystem. By combining multiple rank-metric codewords and introducing a novel random error construction, they reduced public key sizes by approximately 16% for a 130-bit security level without sacrificing resistance to structural or algebraic attacks.
- Unstructured Rank-Metric KEMs: Many compact code-based schemes rely on ideal or cyclic structures, which occasionally introduce vulnerabilities to structural attacks. To avoid this, Aragon et al. introduced LowMS, an unstructured rank-metric Key Encapsulation Mechanism (KEM). By pairing a classic masking technique with a "multiple syndromes" approach, the authors achieved a 128-bit security level with a total communication overhead of roughly 5.9 KB—three to four times smaller than leading unstructured lattice-based designs like FrodoKEM.
- Blockwise Structures: To further optimize rank-metric efficiency, Song et al. introduced a blockwise structure to the Rank Decoding Problem using Low Rank Parity Check (LRPC) codes. By organizing errors and codes into blocks characterized by disjoint supports, the authors boosted the system's decoding capacity. This blockwise framing allowed rank-metric cryptosystems like RQC and ROLLO to shrink their communication overhead by 50% while maintaining robust security.
Parallel Paradigms: Storage Efficiency in Symmetric Primitives
The tension between security guarantees and storage overhead is not unique to public-key cryptography. Similar optimization patterns appear in symmetric primitives, such as non-malleable codes used to protect hardware against tampering attacks.
In the split-state model, traditional information-theoretic non-malleable codes often require massive expansion factors, resulting in long codewords. Venturi addressed this by shifting from information-theoretic bounds to a computational security model. By introducing a weaker block cipher security notion called "entropic fixed-related-key security," the author constructed ultra-short non-malleable codes with compact codeword lengths. This approach drastically reduces storage overhead compared to traditional split-state codes, demonstrating that across both public-key and symmetric settings, redefining the underlying security assumptions or mathematical structures remains the primary mechanism for achieving compact cryptographic implementations.
Key Foundational Work
Quasi-Dyadic CFS Signatures (2010) — contributed 2 concept elements to this direction.
Compact McEliece Keys from Goppa Codes (2009) — contributed 1 concept elements to this direction.