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

Markku-Juhani O. Saarinen

ePrint 2026/1786

Time bound

2^126.77–2^145.22 conditional bit operations across parameter sets

Space bound

2^51.33–2^59.10 bits

Source / version date

15 Sept 2026

Comparison variant

Classical · conditional concrete estimates

Cost scale

Concrete bit-operation estimates

mceliece348864

time 2^126.77; memory 2^51.33 bits

mceliece460896

time 2^145.22; memory 2^59.10 bits

mceliece6688128

time 2^137.48; memory 2^55.18 bits

mceliece6960119

time 2^136.65; memory 2^54.86 bits

mceliece8192128

time 2^137.48; memory 2^55.18 bits

assumption

Compatible locator values are uniquely recovered by public tests

Assumptions and source notes

Conditional arithmetic estimates excluding address generation and memory traffic; not unconditional work factors.

Source location

Abstract
Version: 2026-09-15

Primary source ↗

@misc{saarinen2026-holdout,
  author = {Markku-Juhani O. Saarinen},
  title = {{Bit Operation Cost of ``Holdout'' Key-Recovery Attacks Against Classic McEliece}},
  year = {2026},
  url = {https://eprint.iacr.org/2026/1786},
  cr_date = {2026-08-24},
  cr_status = {preprint},
  cr_author_ids = {markku-juhani-o-saarinen}
}