Paper 2026/1747

Extending Distinguishing to Key Recovery for Subfield Subcodes of GRS codes

Abstract

The McEliece cryptosystem based on binary Goppa codes is the oldest public-key scheme to have resisted both classical and quantum cryptanalysis. Ghoshal, Ishai, Jain, and Sun recently gave a quasipolynomial-time distinguisher for subcodes of Generalized Reed-Solomon codes, including alternant and Goppa codes. We derive two key-recovery attacks from it, both using derivative spaces of the hidden curve. The first attack recovers high-order derivative spaces at a few positions, guesses the partial GRS support at those positions, and tests whether the guessed partial support admits a compatible curve. Once the partial support is found, the attack recovers the remaining support elements point-by-point via linear algebra. The second - a minor-code attack - requires only order-1 derivative spaces. In the non-subfield case, these spaces directly yield an auxiliary minor code that, with high probability, is itself a full GRS code with the original support. In the subfield case, the recovered derivative spaces have an additional Frobenius ambiguity. We handle this by constructing a generalized minor code and extracting a full GRS code from it. In both cases, the standard Sidelnikov-Shestakov attack then recovers the support without enumeration. Both attacks were verified end-to-end over $\mathbb{F}_4$. For binary Goppa codes, derivative flag recovery remains out of computational reach, but the other components have supporting evidence. Conditioned on our assumptions, for Classic McEliece parameters the minor-code attack costs essentially a several runs of the distinguisher (well below the claimed security levels). Concurrently, a later revision of the work of Ghoshal et al. gave an independent key recovery based on different ideas.

Note: The previous revision introduced a second, more efficient attack route and reorganized the presentation. This revision improved the minor-code attack for alternant and Goppa codes by removing Frobenius alignment step.