Among all public-key encryption systems, the McEliece cryptosystem has the strongest security track record, and is the system of choice for users who want to minimize security risks. See the design rationale and guide for security reviewers for a more detailed review of McEliece security.

Quantifying security stability

When the McEliece cryptosystem uses a code of dimension k = (0.8+o(1))n as n→∞, the original 1962 Prange information-set-decoding attack costs (5+o(1))^t. Here t = (0.2+o(1))n/lg n is the number of errors used in the cryptosystem; lg is logarithm base 2; and o(1) means something that converges to 0 as n→∞. The best non-quantum attacks known today, after many papers studying attacks, also cost (5+o(1))^t. A closer look at the o(1) shows small improvements in the attacks, improvements that do not affect the asymptotic security level of the cryptosystem.

The bottleneck in attacking McEliece's cryptosystem, like the bottleneck in attacking a strong cipher, is a gigantic search. Grover's algorithm can be applied to this search, so quantum attacks cost (5+o(1))^t/2. A closer look shows small inner-loop improvements from random walks in the non-quantum case, and from quantum walks in the quantum case.

More generally, replacing 0.8 with R replaces 0.2 with 1−R and replaces 5 with 1/(1−R). The best security for any given key size is achieved for R close to 0.8.

Comparison to lattice security levels

The following graph is from the "Classic McEliece: conservative code-based cryptography" presentation at the 5th NIST PQC Standardization Conference, updating a graph from the "McTiny: fast high-confidence post-quantum key erasure for tiny network servers" presentation at USENIX Security 2020: 29th USENIX Security Symposium.

The graph shows the advances in asymptotic exponents of non-quantum attacks against "unbroken" lattice-based cryptosystems (red graph), compared to the McEliece cryptosystem (blue graph). The vertical axis is the limit as K→∞ of lg(AttackCost(Y,K))/lg(AttackCost(2024,K)), where AttackCost(Y,K) is the cost of the best attack known in year Y against key size K. The horizontal axis is Y.

The graph shows that, in 2010, lattice-based cryptography was claimed to have 45% higher asymptotic security levels than it was claimed to have in 2024. In 2000, lattice-based cryptography was claimed to have superexponentially higher asymptotic security levels than it was claimed to have in 2024.

A closer look at concrete security levels shows small attack improvements against McEliece, as mentioned above, but much larger attack improvements against lattices. These attack improvements mean that lattice proposals from not many years earlier have to be discarded as falling far short of their target security levels.

The FrodoKEM lattice proposal is labeled as a modified "instantiation and implementation" of a 2010 paper. The 2010 paper proposed dimension-256 lattices giving 575-byte ciphertexts ("4.6 x 10³" bits), and wrote that those parameters "appear to be at least as secure as AES-128". For the same AES-128 security goal, FrodoKEM instead proposes dimension-640 lattices giving 9720-byte ciphertexts.

Further comparisons

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