Paper 2026/1747

Extending Distinguishing to Key Recovery for Subfield Subcodes of GRS codes

Abstract

We present two key-recovery attacks against subcodes of generalized Reed–Solomon codes, including alternant and Goppa codes, extending the distinguisher recently introduced by Ghoshal, Ishai, Jain, and Sun. Both attacks recover the full secret key from a single run of the distinguisher. Because the public columns are evaluations of secret polynomials, they lie (up to scaling) on a hidden algebraic curve. The distinguisher holds out one column and finds polynomials vanishing with high multiplicity at the remaining columns, which forces them to vanish identically along the entire curve. From these polynomials, we recover the local geometry of the curve at the held-out column. Two finishing routes then turn the local geometry into the key. In the first route, a bootstrapping step uses this local geometry to recover the tangent planes of the curve at all public columns. From these planes, we construct a minor code, which heuristically turns out to be a full GRS code with the same hidden support, allowing the standard Sidelnikov–Shestakov attack to recover it. Based on a similar idea, the second route uses the local geometry to find two quadratic forms whose ratio at the public columns directly gives an equivalent support. After recovering the support, both routes end by reconstructing the full key, including the support elements removed by any preliminary shortening. We implemented both routes and recovered the secret keys of the TII McEliece challenges TII-173, TII-249, and TII-253, the first two of which had not been solved before, to our knowledge. We also succesfully tested the attacks on randomly generated binary Goppa codes, wild Goppa codes, alternant codes, and GRS subcodes. Under the stated rank and solver assumptions, the whole key recovery costs essentially one run of the distinguisher. In particulat, for Classic McEliece parameters, we estimate this cost at $2^{89.9}$ to $2^{98.6}$ bit operations.

Note: The revision adds improved attacks, new experimental results, and updated complexity estimates. Under the stated assumptions, key recovery now costs essentially one run of the distinguisher. None of the concerns raised in ePrint 2026/1810 are applicable to this revision.