Subject: [pqc-forum] ROUND 3 OFFICIAL COMMENT: Classic McEliece From: 'Edoardo Persichetti' via pqc-forum Date: Fri, 19 Nov 2021 14:24:30 +0000 To: "pqc-comments@nist.gov" CC: pqc-forum Message-ID: <7BB76006-12CE-4577-8C63-671506EDC78F@fau.edu> x-mailer: Apple Mail (2.3654.120.0.1.13) Dear all NIST has sent email to the Classic McEliece team requesting information about "the concrete security of Classic McEliece's parameter sets." This is a reply from the Classic McEliece team. An optimized version of the latest BJMM/MMT variants in 2021 by Esser, May, and Zweydinger, running on real hardware, is barely faster than a 2008 Stern-type attack. See the round-3 Classic McEliece talk: https://www.nist.gov/video/third-pqc-standardization-conference-session-vii-performance-and-candidate-updates https://csrc.nist.gov/CSRC/media/Presentations/classic-mceliece-round-3-presentation/images-media/session-7-classic-mceliece-lange.pdf As for cryptographic sizes, the state-of-the-art cost analyses are from a 2021 script https://github.com/Crypto-TII/syndrome_decoding_estimator.git by Bellini and Esser. See also https://eprint.iacr.org/2021/1243, the accompanying paper by Esser and Bellini. Running import sys from sd_estimator.estimator import sd_estimate_display for n,w in (1024,50),(3488,64),(4608,96),(6688,128),(6960,119),(8192,128): m = 10 while 2**m < n: m += 1 k = n-w*m sd_estimate_display(n=n,k=k,w=w,memory_access=2) sys.stdout.flush() outputs the tables shown below. The tables again show how small the improvements have been after Stern's 1989 attack. The smallest costs in the tables (not counting quantum attacks) are 2^158.6 for mceliece348864, 2^201.0 for mceliece460896, 2^278.2 for mceliece6688128, 2^279.2 for mceliece6960119, and 2^315.6 for mceliece8192128, and footnote 11 of the paper indicates that the actual cost is higher. Changing "memory_access" to "0" gives bit-operation counts that much more obviously underestimate actual costs, such as 2^65.1 bit operations for a Stern attack (using cost-0 access to megabytes of RAM) against McEliece's original parameters, 2^141 bit operations (using cost-0 access to >2^80 RAM) for mceliece348864, and 2^246 bit operations for mceliece6960119. (See Table 2 of https://eprint.iacr.org/2021/1243 for more of these bit-operation counts.) This matches what Section 8.2 of the Classic McEliece submission has always said regarding the originally proposed mceliece6960119 size: Subsequent ISD variants have reduced the number of bit operations considerably below 2^256. ... We expect that switching from a bit-operation analysis to a cost analysis will show that this parameter set is more expensive to break than AES-256 pre-quantum and much more expensive to break than AES-256 post-quantum. This 2021 script supersedes a 2019 paper by Baldi et al. The numbers in the 2019 paper for MMT in particular were much better than for BJMM (and Stern)---which is impossible since BJMM structurally includes MMT, so it was always clear that the MMT numbers had to be disregarded. NIST stated that BJMM "is widely considered to be an improvement over MMT" and asked "Is this analysis correct? If so, it seems like this could threaten not just some of the McEliece parameters, but also some of the parameters of the other code-based schemes." Kirshanova explained in https://crypto.stackexchange.com/questions/92074/number-of-bit-operations-required-for-information-set-decoding-attacks-on-code-b the "conclusion that BJMM algorithm is worse than MMT is incorrect because MMT is a special case of BJMM." An MMT/BJMM calculation error in the 2019 paper is pinpointed in https://eprint.iacr.org/2021/1243, Appendix A. The error would also have been caught by simple consistency checks against experiments. The tables output by the script appear below. ========================================================================== Complexity estimation to solve the (1024,524,50) syndrome decoding problem ========================================================================== The following table states bit complexity estimates of the corresponding algorithms including an approximation of the polynomial factors inherent to the algorithm. The quantum estimate gives a very optimistic estimation of the cost for a quantum aided attack with a circuit of limitted depth (should be understood as a lowerbound). +----------------+---------------+---------+ | | estimate | quantum | +----------------+------+--------+---------+ | algorithm | time | memory | time | +----------------+------+--------+---------+ | Prange | 84.8 | 19.3 | 49.2 | | Stern | 73.2 | 26.1 | -- | | Dumer | 74.1 | 26.2 | -- | | Ball Collision | 74.2 | 26.1 | -- | | BJMM (MMT) | 73.1 | 24.2 | -- | | BJMM-pdw | 71.8 | 21.1 | -- | | May-Ozerov | 70.6 | 21.1 | -- | | Both-May | 71.5 | 21.2 | -- | +----------------+------+--------+---------+ =========================================================================== Complexity estimation to solve the (3488,2720,64) syndrome decoding problem =========================================================================== The following table states bit complexity estimates of the corresponding algorithms including an approximation of the polynomial factors inherent to the algorithm. The quantum estimate gives a very optimistic estimation of the cost for a quantum aided attack with a circuit of limitted depth (should be understood as a lowerbound). +----------------+----------------+---------+ | | estimate | quantum | +----------------+-------+--------+---------+ | algorithm | time | memory | time | +----------------+-------+--------+---------+ | Prange | 178.3 | 21.6 | 95.4 | | Stern | 162.8 | 32.6 | -- | | Dumer | 163.2 | 32.6 | -- | | Ball Collision | 163.2 | 32.6 | -- | | BJMM (MMT) | 162.2 | 30.6 | -- | | BJMM-pdw | 160.3 | 26.8 | -- | | May-Ozerov | 158.6 | 24.6 | -- | | Both-May | 159.8 | 24.9 | -- | +----------------+-------+--------+---------+ =========================================================================== Complexity estimation to solve the (4608,3360,96) syndrome decoding problem =========================================================================== The following table states bit complexity estimates of the corresponding algorithms including an approximation of the polynomial factors inherent to the algorithm. The quantum estimate gives a very optimistic estimation of the cost for a quantum aided attack with a circuit of limitted depth (should be understood as a lowerbound). +----------------+----------------+---------+ | | estimate | quantum | +----------------+-------+--------+---------+ | algorithm | time | memory | time | +----------------+-------+--------+---------+ | Prange | 222.1 | 22.7 | 140.3 | | Stern | 205.3 | 33.6 | -- | | Dumer | 205.8 | 33.6 | -- | | Ball Collision | 205.8 | 33.6 | -- | | BJMM (MMT) | 204.8 | 31.6 | -- | | BJMM-pdw | 203.4 | 28.7 | -- | | May-Ozerov | 201.0 | 25.5 | -- | | Both-May | 202.2 | 26.5 | -- | +----------------+-------+--------+---------+ ============================================================================ Complexity estimation to solve the (6688,5024,128) syndrome decoding problem ============================================================================ The following table states bit complexity estimates of the corresponding algorithms including an approximation of the polynomial factors inherent to the algorithm. The quantum estimate gives a very optimistic estimation of the cost for a quantum aided attack with a circuit of limitted depth (should be understood as a lowerbound). +----------------+----------------+---------+ | | estimate | quantum | +----------------+-------+--------+---------+ | algorithm | time | memory | time | +----------------+-------+--------+---------+ | Prange | 301.2 | 23.6 | 219.9 | | Stern | 283.0 | 35.3 | -- | | Dumer | 283.3 | 35.3 | -- | | Ball Collision | 283.3 | 35.3 | -- | | BJMM (MMT) | 282.3 | 33.3 | -- | | BJMM-pdw | 280.4 | 29.4 | -- | | May-Ozerov | 278.2 | 26.4 | -- | | Both-May | 279.4 | 26.8 | -- | +----------------+-------+--------+---------+ ============================================================================ Complexity estimation to solve the (6960,5413,119) syndrome decoding problem ============================================================================ The following table states bit complexity estimates of the corresponding algorithms including an approximation of the polynomial factors inherent to the algorithm. The quantum estimate gives a very optimistic estimation of the cost for a quantum aided attack with a circuit of limitted depth (should be understood as a lowerbound). +----------------+----------------+---------+ | | estimate | quantum | +----------------+-------+--------+---------+ | algorithm | time | memory | time | +----------------+-------+--------+---------+ | Prange | 302.2 | 23.6 | 220.4 | | Stern | 283.9 | 35.6 | -- | | Dumer | 284.3 | 35.6 | -- | | Ball Collision | 284.3 | 35.6 | -- | | BJMM (MMT) | 283.3 | 33.6 | -- | | BJMM-pdw | 281.4 | 29.7 | -- | | May-Ozerov | 279.2 | 26.6 | -- | | Both-May | 280.3 | 27.0 | -- | +----------------+-------+--------+---------+ ============================================================================ Complexity estimation to solve the (8192,6528,128) syndrome decoding problem ============================================================================ The following table states bit complexity estimates of the corresponding algorithms including an approximation of the polynomial factors inherent to the algorithm. The quantum estimate gives a very optimistic estimation of the cost for a quantum aided attack with a circuit of limitted depth (should be understood as a lowerbound). +----------------+----------------+---------+ | | estimate | quantum | +----------------+-------+--------+---------+ | algorithm | time | memory | time | +----------------+-------+--------+---------+ | Prange | 339.5 | 23.9 | 257.6 | | Stern | 320.7 | 36.3 | -- | | Dumer | 321.0 | 36.4 | -- | | Ball Collision | 321.0 | 36.3 | -- | | BJMM (MMT) | 320.0 | 34.4 | -- | | BJMM-pdw | 318.6 | 31.4 | -- | | May-Ozerov | 315.6 | 27.2 | -- | | Both-May | 317.0 | 27.6 | -- | +----------------+-------+--------+---------+ Best, Edoardo