McEliece security levels

[Max Heiser]

Hey,

I came across the paper "Revisiting the May-Meurer-Thomae Algorithm - Solving McEliece-1409 in one day" (https://eprint.iacr.org/2024/393). This paper claims to decrease the security of Classic McEliece level 3 to 191 bits. This is only mere 1 bit less than 192, but is 16 bits less than the 207 bit security requirements for level 3 (equivalent to 2^192 AES operations).

Moreover, in one of the memory models the authors proposed (which seems more aligned to experimental results when solving the challenge), security is further decreased to 179 bit security.

In this memory model, levels 1+5 are also decreased slightly below the required security levels.

Has anyone been able to corroborate these results?

Max

[D. J. Bernstein]

'Max Heiser' via pqc-forum writes:
> Has anyone been able to corroborate these results?

The CryptAttackTester (CAT) paper from https://eprint.iacr.org/2023/940
already presents precise analyses for a spectrum of fully defined ISD
algorithms in a fully defined bit-operation metric, backed by computer
experiments on small sizes showing perfect matches of the cost analyses
and very close matches of the probability analyses.

This is a big step up in verifiability compared to other ISD papers
(and papers attacking other cryptosystems): it structurally enforces
complete definitions, makes sure that every bit operation is counted,
and makes sure that all major probability factors are accounted for. The
framework can express arbitrary circuits: as a non-ISD example, CAT
already includes brute-force AES attacks.

For parameters (4608,3360,96), CAT's analyses predict

* 2^202.30 bit operations for isd0 (basically 1988 Leon);
* 2^198.93 for isd1 (basically 1988 Stern);
* 2^197.20 for isd2 with p' = 2p'' and C = 0 (basically 2011 MMT);
* 2^195.91 for isd2 with p' = 2p''-2 and C = 0 (basically 2012 BJMM);
* 2^190.50 for isd2 with C = 1 (basically 2013 Hamdaoui--Sendrier).

"Basically" refers to the fact that the older algorithms didn't include
some tricks to reduce linear-algebra costs. In particular, CAT includes
random walks as in 1998 Canteaut--Chabaud, 1998 Canteaut--Sendrier, and
2008 Bernstein--Lange--Peters; removing random walks slows down 1988
Leon by 6 bits, slows down 1988 Stern by 0.7 bits, slows down MMT by 0.1
bits, and has no effect on the 195.91 or 190.50 (where the lists being
built are so large that the linear algebra is invisible).

The C = 0 case has an unnecessary intermediate weight constraint imposed
by MMT and BJMM. The C = 1 case eliminates that weight constraint, as in
Table 3 in 2013 Hamdaoui--Sendrier. The benefit of C = 1 doesn't seem to
have been quantified before the CAT paper.

The 2024 paper https://eprint.iacr.org/2024/393 says it analyzes "the
behavior of the multiple weight distributions of binary vectors
occurring in the list construction phase". This sounds like the 2013
C = 1 speedup that was already analyzed in the CAT paper. The 2024 paper
doesn't cite the CAT paper, and, quantitatively, doesn't report a larger
speedup compared to MMT than the CAT paper does.

Regarding "179" in the 2024 paper, this already has an explanation from
https://eprint.iacr.org/2023/940.pdf#appendix.F: there's a formula in
https://eprint.iacr.org/2021/1243 for the cost of finding collisions
between two lists, but the actual number of bit operations for finding
collisions is much larger than that formula, explaining gaps above 10
bits. The same formula appears to be used in the 2024 paper via
https://eprint.iacr.org/2023/589.

Integrating attacks into CAT makes clear that different costs (such as
the numbers listed above: 202.30 and 198.93 in the 1980s, and then
197.20, 195.91, 190.50) come from the actual costs of different
algorithms rather than from different ways of estimating costs.

The submission has always assigned parameter sets to NIST's "categories"
on the basis of considering realistic communication costs, but also says
that if NIST decides to count just bit operations (which is what CAT now
does with computer support) then the "categories" are "1, 2, 4, 4, 5":
https://classic.mceliece.org/mceliece-security-20221023.pdf#subsection.3.5

---D. J. Bernstein (speaking for myself)

[narisada shintaro]

Dear Dr. Max Heiser and Prof. Daniel J. Bernstein,

Thank you very much for the insightful comments and discussions.
We agree with your comments.

In the forthcoming revision, we will add citations to your paper and
provide proper explanations addressing your comments.

Best regards, 

Shintaro

2024年3月24日日曜日 4:59:26 UTC+9 D. J. Bernstein: