Paper 2026/1786

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

Abstract

We give an itemized conditional arithmetic estimate for ``Holdout'' key recovery on each Classic McEliece parameter set. This attack uses polynomial relations to recover locators, the hidden field values specifying the code. Shortening restricts codewords to zero on selected positions and then deletes those positions. Assuming the public tests uniquely recover enough compatible locator values, one shortened coordinate set suffices for each parameter set, instead of the four or five in the analysis of Ghoshal, Ishai, Jain, and Sun. We make the linear solves reliable using Eberly's random scaling of rows and columns and scalar Lanczos, an iterative solver over a larger field. Returned solutions are mapped back and checked in the original equations. Charging operations with binary coefficients separately from general field arithmetic gives conditional arithmetic estimates of $2^{126.77}$ bit operations for mceliece348864, $2^{145.22}$ for mceliece460896, $2^{137.48}$ for mceliece6688128, $2^{136.65}$ for mceliece6960119, and $2^{137.48}$ for mceliece8192128}. The corresponding working-memory estimates are $2^{51.33}$, $2^{59.10}$, $2^{55.18}$, $2^{54.86}$, and $2^{55.18}$ bits. All five arithmetic estimates lie below the NIST classical-gate reference level for their claimed category; the model excludes address generation and memory traffic and uses budget estimates for some stages.

Note: The supporting artifact can be found at: https://github.com/mjosaarinen/mccost