14 August 2026

Unstructured thoughts on "Quasipolyomial Cryptanalysis of the McEliece Cryptosystem (or: PIR Meets McEliece)", a 2026 preprint by Ghoshal, Ishai, Jain, Sun.

1. I like the fact that McEliece has started attracting attention of researchers. I believe it to be the most secure, and most underrated public-key cryptosystem described in literature.
2. The break is not as devastating as it looks like, but the result is rather impressive.
3. The security of McEliece generally mainly hinges on the difficulty of random linear block codes are NP-hard and generally hard to decode, on average. McEliece's OW-CPA security furher follows from OW-CPA security of a uniform random matrix if the McEliece public key is indistinguishable from a uniform random matrix (of course, finding a distinguishing attack faster than the target OW-CPA security level would render this implication vacuous),
   1. The Classic McEliece security is tangential to distinguishing attacks, but it's important to point out that this is "not a two-way implication---perhaps there are distinguishers even if OW-CPA is secure". Even fast high-probability distinguishers would not be relevant to any of the Classic McEliece security claims.
   2. For an algorithm to have an effect on the Classic McEliece security analysis, it would have to be much faster than the distinguisher from the preprint and would have to be a key-recovery attack or something else that breaks OW-CPA.
   3. The authors truthfully acknowledge that the current gateway to a real attack beyond distinguishing is far fetched.
4. Overall, it's pretty amazing that McEliece held out for 60 years without any substantially faster attack than the reduction to iSD.
5. The idea is very beautiful and conceptually simple: First hold out one column, then compute the space of multilinear homogeneous polynomials of degree whose Hasse derivatives of order below vanish at every remaining column, then check whether those polynomials also vanish at the held-out column. for a Goppa key the answer is forced by Hermite interpolation. for a random matrix it fails with constant probability.