Classic McEliece

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.

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

Ten years ago, lattice-based cryptography was claimed to have 42% higher asymptotic security levels than it is claimed to have today (in 2020). Twenty years ago, lattice-based cryptography was claimed to have superexponentially higher asymptotic security levels than it is claimed to have today.

The following 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(2020,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.

degradation of claimed security of lattice-based cryptography, compared to security of the McEliece cryptosystem

Picture credit: Daniel J. Bernstein and Tanja Lange, McTiny: fast high-confidence post-quantum key erasure for tiny network servers, presentation accompanying refereed paper at USENIX Security 2020: 29th USENIX Security Symposium.

Further comparisons

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


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