Paper 2026/1512

The McEliece Cryptosystem After Nearly Five Decades: A Survey of Security, Cryptanalysis, and Future Directions

Abstract

Almost fifty years after its introduction, the McEliece cryptosystem occupies an unusual place in the post-quantum landscape. Its public keys are far larger than those of most competing schemes, its original parameters no longer provide adequate security, and several compact variants proposed to reduce key size have subsequently been broken. Nevertheless, the binary Goppa-code foundation retained in Classic McEliece continues to resist known practical attacks for the selected Classic McEliece parameter sets. This survey asks why McEliece has remained relevant despite these limitations. We trace its development from the original 1978 encryption scheme to the modern Classic McEliece key-encapsulation mechanism and organize nearly five decades of cryptanalysis into generic decoding, structural recovery, attacks on compact variants, protocol-level attacks, implementation leakage, and quantum speedups. We emphasize several distinctions that are often blurred in discussions of the scheme: breaking an obsolete parameter set is not the same as recovering the hidden Goppa structure; distinguishing a public code does not necessarily lead to practical key recovery; and compromising a modified or structured variant does not automatically compromise Classic McEliece. This history does not support either of two simple narratives: that McEliece has remained unchanged or that it has simply been broken. Its longevity reflects a conservative mathematical foundation that has survived repeated reassessment, together with parameters, security models, and implementations that have evolved in response to new attacks. We close by outlining the main questions that will shape its future: whether public-key and key-distribution costs can be reduced without exposing exploitable structure, how far modern algebraic cryptanalysis can be extended, how classical and quantum security estimates should be refined, and how secure implementations can be integrated into practical systems.