Refined analysis of algorithms solving syndrome decoding problem

The syndrome decoding problem (SDP) for random linear codes is a fundamental NP‑hard problem in coding theory, forming the security foundation for many code‑based post‑quantum cryptographic schemes. Information Set Decoding (ISD) algorithms, especially those using the representation technique (e.g., MMT and BJMM), and dual decoding are important methods for solving SDP. Esser et al. presented an evaluation framework for the ISD algorithms and formed a helpful open-source Syndrome Decoding Estimator (SDE), which is used to estimate the security of concrete parameters for code-based schemes. In this work, we present two improvements to the analysis of SDP. First, we provide a refined concrete complexity analysis for BJMM in SDE without altering the BJMM algorithm or its asymptotic complexity analysis. In particular, we improve the concrete estimated number of iterations in concrete time and space estimation. We achieve this improvement by distinguishing three key lists in the tree-based enumeration process. Experimental results confirm that our estimation is more precise. As an application, we obtain an updated time and space estimate for Classic McEliece. Second, we propose preprocessing variants of advanced ISD algorithms and dual decoding algorithms, enabling a trade-off between offline storage and online computation. This approach is advantageous in multi-instance attack settings to reduce amortized complexity. We also emphasize the limitations of the preprocessing variants in practice and propose practical countermeasures.