Finite-Regime Quantum Complexity of Representation-Based Information Set Decoding (MMT/BJMM) under Realistic Circuit and Memory Cost Models

The concrete security of code-based post-quantum schemes such as Classic McEliece, HQC and BIKE against generic attacks is measured by the cost of information set decoding (ISD). A 2019 finite-regime analysis (Baldi et al., Algorithms 12(10):209) derived explicit concrete-parameter complexity formulas for all major classical ISD variants and partial quantum estimates, but left the quantum attack landscape incomplete: it provided no finite-regime quantum complexity formulas for the representation-based MMT and BJMM variants - the paper explicitly set aside the then-available quantum re-elaborations of MMT/BJMM because "no finite regime complexity formulas are provided" for them - and its reported quantum numbers are lower bounds for non-reversible circuits, obtained by forgoing reversible-circuit implementation overheads. Subsequent literature resolved the paper's stated future-work item (practical validation via record computations up to McEliece-1284) and substantially advanced the related classical-side questions (memory-aware classical estimates, and DOOM speedups transferred to MMT/BJMM), and fully worked out the quantum circuit cost only for the basic Prange variant. What remains open is the quantum analysis of the advanced variants: derive explicit finite-regime quantum complexity formulas for MMT/BJMM-class ISD under a stated realistic quantum cost model in which reversible computation (with explicit uncomputation and memory management) and quantum memory-access costs are counted, optimize the free parameters for standardized parameter sets, and settle whether representation-based variants retain any advantage over quantum Prange at cryptographic sizes.

Background

Code-based public-key cryptography (the McEliece and Niederreiter cryptosystems) derives its security from the hardness of decoding random linear codes. In the syndrome decoding problem (SDP), one is given a parity-check matrix $H$ of a binary linear code and a syndrome $s$, and must find an error vector $e$ of low Hamming weight with $He=s$; the codeword finding problem (CFP) asks for a low-weight nonzero codeword of a code. Both are NP-hard and equivalent in difficulty, and they set the cost of the best generic (structure-blind) attacks on these cryptosystems.

Information set decoding (ISD) is the family of such attacks. The basic algorithm due to Prange repeatedly samples a random subset of coordinates (an information set), hopes it is error-free, and recovers a candidate error by linear algebra. Stern's algorithm added a meet-in-the-middle collision step; the MMT algorithm (May, Meurer and Thomae, 2011) and the BJMM algorithm (Becker, Joux, May and Meurer, 2012) exploit representations — the fact that a solution error vector can be written as a sum of lower-weight vectors in many ways — to build and merge exponentially large intermediate lists, lowering the exponential complexity constant. Modern descendants accelerate the list processing with nearest-neighbor search techniques. All complexities remain exponential, roughly $2^{cn}$ for code length $n$ with progressively smaller constants $c$.

Asymptotic exponents do not decide security at the concrete parameters of deployed schemes, so security estimates use finite-regime (concrete-parameter) formulas: explicit work factors as functions of the code length $n$, dimension $k$, and error weight $w$ of the target instance, with the variant's free parameters optimized for those values. The source paper (Baldi, Barenghi, Chiaraluce, Pelosi and Santini, 2019) computed such finite-regime temporal and spatial complexities for the major classical ISD variants and assessed quantum speedups in the finite regime, using the NIST post-quantum standardization parameter suites as a validation set.

On the quantum side, Grover's search algorithm and its generalization, amplitude amplification, square-root the cost of the outer random sampling of ISD; Bernstein (2010) quantified this for Prange's algorithm. Quantum walks (Kachigar and Tillich, 2017) give asymptotic quantum versions of the list-based MMT/BJMM framework, and Kirshanova (2018) combined quantum walks with the May-Ozerov nearest-neighbor technique. However, these asymptotic results assume quantum-accessible memory (QRAM/QRAQM): exponentially large lists are held in quantum states and accessed coherently at unit or uncounted cost. A real quantum computer must run reversible circuits — every intermediate result must be uncomputed — with explicit qubit counts and memory-management costs. Esser, Ramos-Calderer, Bellini, Latorre and Manzano (PKC 2022) showed that fully-fledged quantum Prange can be implemented reversibly with only logarithmic overhead in circuit depth, and Perriello, Barenghi and Pelosi (2021-2023) constructed complete quantum circuit designs with quantitative security margins for NIST parameters; but no comparable realistic-cost treatment exists for the representation-based variants, whose exponentially large lists would have to live in quantum memory. This matters practically: if reversible and memory costs erase the advantage of the advanced variants, the relevant quantum attack is quantum Prange, which changes the quantum security margin of every code-based parameter set.

Two further strands frame the problem. First, the memory cost of classical list-based ISD became an active research line: time-memory trade-offs (Esser and Zweydinger, Eurocrypt 2023), low-memory security re-estimates (Li and Wang, 2023), memory-limited analyses of MMT (Narisada, Fukushima and Kiyomoto, 2023), and high-assurance cost-accounting frameworks (Bernstein and Chou's CryptAttackTester, 2024). Second, attacking one out of many syndromes (DOOM) and exploiting quasi-cyclic structure gives multiplicative speedups whose assumptions have been verified and transferred to MMT/BJMM (Esser, May and Zweydinger, PKC 2022; Wu and Zhuang, 2022). With these classical-side questions largely settled, the source paper's surviving open core is the quantum analysis of the advanced variants under realistic cost models.

Problem Statement

Derive the missing quantum part of the finite-regime ISD attack landscape, in the same concrete-parameter style as the source paper's classical analysis. Specifically: (1) give explicit, algorithmically evaluable quantum complexity formulas - quantum time (circuit depth) and quantum space (qubits), as functions of the code length $n$, dimension $k$, error weight $w$, and the variant's free parameters - for the representation-based ISD variants, at minimum MMT and BJMM, under an explicitly stated realistic quantum cost model in which all computation is reversible with explicit uncomputation and memory-management costs counted, and quantum memory access (coherent access to the exponentially large intermediate lists) is explicitly accounted; (2) optimize the free parameters of each variant over the code-based parameter sets of the NIST standardization effort used as the source paper's validation suite (Classic McEliece, NTS-KEM, BIKE, LEDAcrypt), optionally extended to the current standardized successor sets such as HQC; and (3) produce a like-for-like comparison, under the same cost metric, of all ISD variants from Prange to the BJMM class, thereby settling, relative to the explicitly stated cost model, whether the representation-based variants retain their classical advantage over Prange in the quantum finite regime once reversible-circuit and memory-access overheads are included. Establish explicit finite-regime quantum time and space formulas for the representation-based variants (at minimum MMT and BJMM) under one stated realistic cost model that counts the reversible-circuit and quantum memory-access overheads the source forwent, optimized over the targeted parameter sets and compared under the same cost metric against the basic variants (Prange, Lee-Brickell, Leon, Stern) evaluated under that same stated realistic cost model, replacing the source's lower-bound model of non-reversible circuits, so as to determine, relative to that cost model, whether the representation-based variants retain any advantage over quantum Prange at cryptographic sizes. All three requested results serve this single objective of completing the quantum attack landscape; the formulas ground the optimization, and the optimization grounds the comparison.

References

1. Marco Baldi, Alessandro Barenghi, Franco Chiaraluce, Gerardo Pelosi, Paolo Santini (2019). A Finite Regime Analysis of Information Set Decoding Algorithms. Algorithms 12(10):209. DOI 10.3390/a12100209. https://doi.org/10.3390/a12100209
2. Daniel J. Bernstein (2010). Grover vs. McEliece. Post-Quantum Cryptography (PQCrypto 2010). DOI 10.1007/978-3-642-12929-2_6. https://doi.org/10.1007/978-3-642-12929-2_6
3. Alexander May, Alexander Meurer, Enrico Thomae (2011). Decoding Random Linear Codes in $\tilde{O}(2^{0.054n})$. ASIACRYPT 2011. DOI 10.1007/978-3-642-25385-0_6. https://doi.org/10.1007/978-3-642-25385-0_6
4. Anja Becker, Antoine Joux, Alexander May, Alexander Meurer (2012). Decoding Random Binary Linear Codes in $2^{n/20}$: How $1+1=0$ Improves Information Set Decoding. EUROCRYPT 2012. DOI 10.1007/978-3-642-29011-4_31. https://doi.org/10.1007/978-3-642-29011-4_31
5. Ghazal Kachigar, Jean-Pierre Tillich (2017). Quantum Information Set Decoding Algorithms. Post-Quantum Cryptography (PQCrypto 2017). DOI 10.1007/978-3-319-59879-6_5. https://doi.org/10.1007/978-3-319-59879-6_5 (also arXiv:1703.00263)
6. Elena Kirshanova (2018). Improved Quantum Information Set Decoding. arXiv:1808.00714. https://arxiv.org/abs/1808.00714
7. Andre Esser, Sergi Ramos-Calderer, Emanuele Bellini, Jose I. Latorre, Marc Manzano (2022). Hybrid Decoding - Classical-Quantum Trade-Offs for Information Set Decoding. Public-Key Cryptography (PKC 2022). DOI 10.1007/978-3-031-17234-2_1. https://doi.org/10.1007/978-3-031-17234-2_1 (preprint arXiv:2112.06157, posted under its original title "An Optimized Quantum Implementation of ISD on Scalable Quantum Resources")
8. Simone Perriello, Alessandro Barenghi, Gerardo Pelosi (2021). A Quantum Circuit to Speed-Up the Cryptanalysis of Code-Based Cryptosystems. CT-RSA 2021. DOI 10.1007/978-3-030-90022-9_25. https://doi.org/10.1007/978-3-030-90022-9_25
9. Simone Perriello, Alessandro Barenghi, Gerardo Pelosi (2021). A Complete Quantum Circuit to Solve the Information Set Decoding Problem. IEEE International Conference on Quantum Computing and Engineering (QCE 2021). DOI 10.1109/QCE52317.2021.00056. https://doi.org/10.1109/QCE52317.2021.00056
10. Simone Perriello, Alessandro Barenghi, Gerardo Pelosi (2023). Improving the Efficiency of Quantum Circuits for Information Set Decoding. ACM Transactions on Quantum Computing. DOI 10.1145/3607256. https://doi.org/10.1145/3607256
11. Andre Esser, Alexander May, Floyd Zweydinger (2022). McEliece Needs a Break - Solving McEliece-1284 and Quasi-Cyclic-2918 with Modern ISD. Public-Key Cryptography (PKC 2022). DOI 10.1007/978-3-031-07082-2_16. https://doi.org/10.1007/978-3-031-07082-2_16 (also IACR ePrint 2021/1634)
12. Andre Esser, Floyd Zweydinger (2023). New Time-Memory Trade-Offs for Subset Sum - Improving ISD in Theory and Practice. EUROCRYPT 2023. DOI 10.1007/978-3-031-30589-4_13. https://doi.org/10.1007/978-3-031-30589-4_13 (also IACR ePrint 2022/1329)
13. Andre Esser, Emanuele Bellini (2022). Syndrome Decoding Estimator. Public-Key Cryptography (PKC 2022). DOI 10.1007/978-3-030-97121-2_5. https://doi.org/10.1007/978-3-030-97121-2_5 (also IACR ePrint 2021/1243)
14. Yu Li, Li-Ping Wang (2023). Security analysis of the Classic McEliece, HQC and BIKE schemes in low memory. Journal of Information Security and Applications. DOI 10.1016/j.jisa.2023.103651. https://doi.org/10.1016/j.jisa.2023.103651
15. Shintaro Narisada, Kazuhide Fukushima, Shinsaku Kiyomoto (2023). Multiparallel MMT: Faster ISD Algorithm Solving High-Dimensional Syndrome Decoding Problem. IEICE Transactions on Fundamentals. DOI 10.1587/transfun.2022cip0023. https://doi.org/10.1587/transfun.2022cip0023
16. Qian Guo, Thomas Johansson, Vu Nguyen (2024). A New Sieving-Style Information-set Decoding Algorithm. IEEE Transactions on Information Theory. DOI 10.1109/TIT.2024.3457150. https://doi.org/10.1109/TIT.2024.3457150
17. Lynn Engelberts, Simona Etinski, Johanna Loyer (2024). Quantum Sieving for Code-Based Cryptanalysis and Its Limitations for ISD. arXiv:2408.16458. https://arxiv.org/abs/2408.16458
18. Haoxuan Wu, Jincheng Zhuang (2022). Syndrome decoding meets multiple instances. arXiv:2209.06656. https://arxiv.org/abs/2209.06656
19. Naoto Kimura, Atsushi Takayasu, Tsuyoshi Takagi (2023). Memory-Efficient Quantum Information Set Decoding Algorithm. ACISP 2023. DOI 10.1007/978-3-031-35486-1_20. https://doi.org/10.1007/978-3-031-35486-1_20
20. Yu Li, Yue Cao, Sen-You Hou, Baosheng D. Huang (2026). An Improved Quantum Both-May ISD Algorithm. 2026 8th International Conference on Electronic Engineering and Informatics (EEI). DOI 10.1109/EEI70303.2026.11640518. https://doi.org/10.1109/EEI70303.2026.11640518
21. Daniel J. Bernstein, Tung Chou (2024). CryptAttackTester: high-assurance attack analysis. CRYPTO 2024. DOI 10.1007/978-3-031-68391-6_5. https://doi.org/10.1007/978-3-031-68391-6_5 (also IACR ePrint 2023/940)
22. Andre Esser, Javier Verbel, Floyd Zweydinger, Emanuele Bellini (2024). SoK: CryptographicEstimators - a Software Library for Cryptographic Hardness Estimation. ACM AsiaCCS 2024. DOI 10.1145/3634737.3645007. https://doi.org/10.1145/3634737.3645007
23. Sourabh Biswas, Indivar Gupta, Debasish Bera (2024). On the Comparative Study of Recent Information Set Decoding (ISD) Attacks for QC-LDPC Code-Based McEliece Cryptosystem. IEEE PKIA 2024. DOI 10.1109/PKIA62599.2024.10727868. https://doi.org/10.1109/PKIA62599.2024.10727868
24. Hiroki Furue, Yusuke Aikawa (2025). An Improved Both-May Information Set Decoding Algorithm: Towards More Efficient Time-Memory Trade-Offs. Post-Quantum Cryptography (PQCrypto 2025). DOI 10.1007/978-3-031-86599-2_4. https://doi.org/10.1007/978-3-031-86599-2_4