Classic McEliece: Comparison

This page compares Classic McEliece to alternatives on various security axes:

Among all public-key encryption systems, the McEliece cryptosystem has the strongest security track record.
The costs of state-of-the-art attacks are much easier to verify for McEliece than for alternatives.
The QROM IND-CCA2 security of Classic McEliece has a tight connection to the one-wayness of the original McEliece system, while alternatives are usually much less tightly connected to their underlying one-wayness problems.

See the design rationale and guide for security reviewers for a more detailed review of the security of Classic McEliece. The security advantages of Classic McEliece are a major motivation for the third-party integrations, deployments, and recommendations of Classic McEliece.

Stability of attack costs for the underlying problem

Why attack stability matters. The original 1977 announcement of RSA included an RSA-428 challenge, estimated that this would take "40 quadrillion years" to break, and said that the possibility of a "fast algorithm for factoring composites as large as [that]" was "extremely remote". RSA-512 was widely deployed starting in the 1990s. Deployment continued even after public demonstrations of an RSA-428 factorization in 1994 and an RSA-512 factorization in 1999, causing a variety of security failures into the 2010s. By 2015, each RSA-512 key was shown to be breakable for just $75 on Amazon EC2. This was not the result of a single sudden breakthrough: it was the result of a series of algorithmic improvements in many papers.

Lattice-based cryptography is following the same pattern. For example, a 2010 paper says that it provides "theoretically sound lattice-based encryption schemes" based on the "LWE" problem. The paper proposed dimension-256 lattices giving 575-byte ciphertexts ("4.6 x 10³" bits). The paper evaluated attack costs: "For the 'medium security' (n = 256) parameter set, the best runtime/advantage ratio is approximately 2¹²⁰ seconds, which translates on our machine to about 2¹⁵⁰ operations. It seems reasonable to conclude that these parameters currently offer security levels at least matching those of AES-128."

A series of attack papers then removed more and more bits from the LWE security level, making these parameters millions of times less expensive to break than AES-128. Deployment of this dimension-256 cryptosystem would have been a security failure, even if attackers were as slow as the public in finding these attack improvements. Attackers were already recording encrypted data to break later. Messages often require long-term security.

This 2010 paper is not obscure. It has been cited more than 1000 times. FrodoKEM, often described as the "most conservative" lattice-based cryptosystem, says that it is a modified "instantiation and implementation" of the same 2010 paper. For the same goal of matching AES-128, FrodoKEM proposes dimension-640 lattices giving 9720-byte ciphertexts. The long-term safety of these parameters is unclear: the cost of attacks against LWE is continuing to drop.

Stability of McEliece attack costs. For Classic McEliece, the underlying problem is the one-wayness of the original 1978 McEliece system. An extensive literature searching for the best attacks against this problem has produced only a small total change in attack exponents over half a century. Concretely, the following estimated bit-operation counts are from CryptAttackTester, a software tool introduced in a Crypto 2024 paper by Daniel J. Bernstein and Tung Chou:

`isd1`	`isd2`	problem size (n,t)
2^70.05	2^69.78	(1024,50)
2^156.96	2^150.59	(3488,64)
2^275.41	2^257.36	(6688,128)

The isd1 column uses attack techniques from the 1980s. The isd2 column uses current attack techniques. Both of these are examples of "information-set decoding" (ISD), which has always been the state-of-the-art attack strategy against the McEliece cryptosystem.

McEliece's original 1978 paper estimated "about 10¹⁹ ≈ 2⁶⁵" bit operations to break sizes "n = 1024" and "t = 50". This was an underestimate of the cost of attacks known at that point. Subsequent attack improvements still use more than 2⁶⁵ bit operations. The fastest attack software available today takes about 2⁶⁰ CPU cycles (with many bit operations per CPU cycle) to break size (1024,50).

The size (3488,64) is used in mceliece348864, the smallest Classic McEliece parameter set. The size (6688,128) is used in mceliece6688128. The mceliece6* sizes are recommended for long-term security, including security against multi-target attacks and against quantum attacks.

Verifiability of attack costs for the underlying problem

Why attack verifiability matters. The process of publicly searching for the lowest-cost attacks relies on being able to recognize improvements that reduce cost below the state of the art, setting a new baseline for the next round of improvements. Recognizing improvements is difficult when cost analyses rely on lengthy hand calculations, are surrounded by uncertainties, use unclear cost metrics, or are otherwise difficult to check.

For example, the 2021 Kyber documentation included a "preliminary analysis" giving a cost of 2¹⁵¹ bit operations ("gates") to attack an LWE problem related to kyber512, but said that "this number could be affected by a factor of up to 2¹⁶ in either direction" because of "known unknowns". Saying that the current attack cost is somewhere between 2¹³⁵ and 2¹⁶⁷ makes it difficult to tell the difference between a new attack saving a factor 2⁵ and a new attack losing a factor 2⁵.

The calculations in this "preliminary analysis" were difficult enough that no comparable numbers were provided for the other Kyber parameter sets. Scripts were provided for some portions of the calculations, but those scripts did not check that the calculations correspond to any actual algorithms. For example, one 864-line script includes a line estimating that the "cost of sorting" n 32-bit integers is n(log₂ n)(32 + log₂ n) bit operations. Is this an underestimate? An overestimate? What about the estimates for more complicated components of the attack?

A 2022 paper claimed that another approach reduced the security level of kyber512 to 2^137.5 bit operations. NIST responded that, even though "the pre-quantum security of Kyber-512 may be a few bits below the one of AES-128", the costs of accessing memory would add "something like 20 to 40 bits of security". After this was disputed, NIST wrote that NIST's "best guess for the realistic cost of attacking Kyber512 is the equivalent of about 2¹⁶⁰ bit operations/ gates, with a plausible range of uncertainty being something like 2¹⁴⁰ to 2¹⁸⁰".

There were then two papers saying how to improve attacks so that memory-access costs add far fewer bits of security than NIST had claimed. Meanwhile a 2023 paper questioned whether the 2022 paper worked, but a 2025 paper claimed that a revised approach used 2^139.5 bit operations. New papers continually appear with claims of lower lattice security. Each paper has another complicated new analysis with many steps that are not computer-checked.

Verifiability of McEliece attacks. A wide range of old and new ISD algorithms have been systematically implemented as combinations of bit operations, along with formulas for the bit-operation counts and success probability of each algorithm. The formulas are systematically computer-checked against attack experiments for many different sizes, experiments that monitor actual bit-operation usage and success probability. All of this is enforced by CryptAttackTester, providing high assurance of accuracy.

CryptAttackTester can handle any sequence of bit operations: for example, it also tests attacks against AES. Any improvements in McEliece attacks, whether from ISD or from another approach, can be integrated into CryptAttackTester and distinguished from non-improvements, the same way that a variety of small improvements in McEliece attacks over the past half century are already visible in CryptAttackTester.

Tightness of the connection of the cryptosystem to the underlying problem

Why a tight connection matters. Even when a cryptosystem says it is based on an underlying problem studied by cryptanalysts, attacking the cryptosystem often turns out to be easier than any known attacks against the underlying problem. The main technique used to control this risk is proofs, but these proofs often have gaps. Each gap is a security risk.

For example, a lattice-based cryptosystem named Round2 claimed to provide "a proof of IND-CCA security for Round2.PKE" assuming the hardness of "Learning with Rounding with sparse trinary secrets", which in turn it claimed to prove "based on the hardness of the LWE problem with uniformly random secrets in ℤ_q and Gaussian errors". An update of Round2 named Round5 made similar claims. Gaps in these supposed connections were then exploited by a feasible attack against Round5 using decryption failures, and by an attack demo against Round2 using hash overlaps.

As another example, the FrodoKEM documentation says that FrodoKEM's "security derives from cautious parameterizations of the well-studied learning with errors problem, which in turn has close connections to conjectured-hard problems on generic, 'algebraically unstructured' lattices". Concretely, QROM IND-CCA2 security of FrodoKEM is claimed to be proven assuming one-wayness of FrodoPKE, which in turn is claimed to be proven assuming "worst-case" hardness of a lattice problem called "BDDwDGS". However, neither of these proofs is tight. The cost of breaking QROM IND-CCA2 for FrodoKEM, or even ROM IND-CCA2 for FrodoKEM, could be much lower than the cost of breaking one-wayness for FrodoPKE, which in turn could be much lower than the worst-case hardness of lattice problems such as BDDwDGS. One of these looseness gaps has already been exploited to identify a feasible large-scale attack against FrodoKEM-640, disproving the claim that "the FrodoKEM parameter sets comfortably match their target security levels with a large margin".

Regarding lattice problems more broadly, it has been claimed that "the underlying worst-case problems – e.g., approximating short vectors in lattices – have been deeply studied by some of the great mathematicians and computer scientists going back at least to Gauss, and appear to be very hard". In fact, BDDwDGS is a new problem that was never studied by Gauss. Gauss encountered some 2-dimensional lattices, easily found the shortest nonzero vector in those, and never suggested that higher-dimensional lattice problems were difficult.

As a third example, the Kyber documentation reports a QROM IND-CCA2 proof for Kyber assuming hardness of an "MLWE" distinguishing problem; treats "the hardness of the MLWE problem as an LWE problem"; and then focuses on the cost of one-wayness attacks against LWE. Each of these steps has a gap creating a security risk. The proof is not tight, so Kyber's QROM IND-CCA2 security level can be below the hardness of MLWE distinguishers. MLWE can be easier to break than LWE. Distinguishing attacks can be easier than one-wayness attacks.

A 2026 paper reports MLWE being a few bits easier to break than LWE for the Kyber parameters. This is not devastating by itself, but it illustrates that treating MLWE as LWE is erroneous. MLWE could be much weaker than LWE without contradicting any known proofs. This risk for Kyber is highlighted in the FrodoKEM documentation ("Given the unpredictable long-term outlook for algebraically structured lattices, and because any post-quantum standard should remain secure for decades into the future—including against new quantum attacks—we have based our proposal on the algebraically unstructured, plain LWE problem with conservative parameterizations"), but the broader problem of a disconnect between cryptosystems and cryptanalysis is shared by Kyber and FrodoKEM.

Tightness for Classic McEliece. The QROM IND-CCA2 security of Classic McEliece follows tightly from the one-wayness problem extensively studied by cryptanalysts, the one-wayness of the original McEliece cryptosystem. Two features of the McEliece cryptosystem are important for this QROM IND-CCA2 connection:

The McEliece decryption algorithm recovers all of the randomness that was generated for encryption.
The McEliece decryption algorithm has no decryption failures on valid inputs: outputs of the encryption algorithm always decrypt to the original plaintexts.

Correctness of the decryption formulas has been formally verified in Lean and in HOL Light.

This does not address the risk of IND-CCA2 security being lower than QROM IND-CCA2 security. The risk here is that the selected hash function allows faster attacks than a "random oracle" would, for example because of weaknesses in the hash function or because of interactions between the hash function and the public-key cryptosystem. To minimize this security risk, Classic McEliece selects SHAKE256 as the hash function.

For further information, see the guide for security reviewers.

Other comparisons

Classic McEliece Comparison Task Force, "Classic McEliece vs. NTS-KEM", 2018.06.29: vsntskem-20180629.pdf

Version: This is version 2026.06.19 of the "Comparison" web page.