Paper 2026/1786

Bit Operation Cost of ``Holdout'' Key-Recovery Attacks Against Classic McEliece

Abstract

We present a self-contained conditional arithmetic model and algorithmic specification for a prospective key-recovery attack on binary Goppa codes, combining the binary hold-out operator with heterogeneous Hasse multiplicities, Lucas-minimal derivative levels, augmented binary block Wiedemann, and reconstruction from local flags. The first two reductions give exact, dimension-guaranteed attack-parameter configurations for every Classic McEliece parameter set. We derive the sparse operator, safe-rank-bound sequence state, a relation-generation tally assuming one attempt per relation batch, higher-flag arithmetic, and the downstream solve performed for every guess. At the selected configurations, modeled affine normalization with dense solves ranges from $2^{172.13}$ to $2^{235.09}$ gates, while projective normalization with nested solves ranges from $2^{146.29}$ to $2^{207.83}$. For mceliece348864, a configuration with $c=7$ gives $2^{142.15}$ modeled gates and retains $2^{61.7}$ bits, excluding temporary solver memory. An exhaustive scan of 19,338 admitted singleton (one-position hold-out) configurations finds a $2^{114.35}$ relation-generation floor in the same fixed model; no downstream-only improvement can cross it. A synthetic experiment heuristically supports the Frobenius-phase balance test, but no public pure cross-pairing is known. None of the tallies is an established break: reliable small-field Krylov yield, higher-flag recovery from the priced truncated block, binary reconstruction, cross-anchor independence, and memory-aware implementation remain open. This manuscript is currently a living tracking document.