Subject: ROUND 3 OFFICIAL COMMENT: Classic McEliece
From: "D. J. Bernstein" <djb@cr.yp.to>
Date: Thu, 16 Jun 2022 20:23:26 +0200
To: pqc-comments@nist.gov
Cc: pqc-forum@list.nist.gov
Message-ID: <20220616182326.231314.qmail@cr.yp.to>

The following observation may be of interest for people quantifying the
stability of state-of-the-art attacks against Classic McEliece.

Our PQCrypto 2008 ISD algorithm is faster than the Eurocrypt 2022 ISD
algorithm, on the CPUs selected in the new paper, for the challenges
selected in the new paper, according to a direct comparison of (1) our
measurements of the 2008 software (the 2+2 case of the 2008 algorithm)
and (2) the speeds reported in the new paper for that paper's software.

Instructions for reproducing our measurements appear in README in the
following package, along with a review of the known opportunities for
further speedups: https://cr.yp.to/software/lowweight-20220616.tar.gz

The new paper's comparison to previous work does not appear to account
for various speedups described in the 2008 paper, such as the usage of
2^l-bit tables and the "c" parameter. These speedups are particularly
important for the 2+2 case, also influencing comparisons of the 2+2 case
to other cases.

---D. J. Bernstein, T. Lange, and C. Peters