Rank Syndrome Decoding Estimator - An Asymptotic and Concrete Analysis

Andre Esser · Javier Verbel · Ricardo Villanueva-Polanco

ePrint 2026/082

Time bound

2^{0.1481 n² + o(n²)}

Space bound

—

Source / version date

19 Jan 2026

Comparison variant

Classical · m = n · worst parameters

Cost scale

2^{c n² + o(n²)}

field-convention

Source abstract normalization; no change-of-base or arbitrary-q extrapolation is asserted.

Assumptions and source notes

Worst-parameter m=n baseline, attained by algebraic and combinatorial methods. The coefficient is quoted in the base-2 normalization of the source abstract. It is not a universal coefficient for arbitrary base fields q; field and bit/field-operation conventions must be kept as in the source.

Source location

Abstract
Version: 2026-01-19

Primary source ↗

@misc{esser-verbel-villanueva2026,
  author = {Andre Esser and Javier Verbel and Ricardo Villanueva-Polanco},
  title = {{Rank Syndrome Decoding Estimator - An Asymptotic and Concrete Analysis}},
  year = {2026},
  url = {https://eprint.iacr.org/2026/082},
  cr_date = {2026-01-19},
  cr_status = {preprint},
  cr_author_ids = {andre-esser; javier-verbel; ricardo-villanueva-polanco}
}