Paper 2026/1947

A Generalized ISD Framework for Large-Weight Syndrome Decoding

Abstract

Syndrome decoding ($\mathsf{SD}$) over $\mathbb{F}_2$ has long been a central problem in code-based cryptography. Large-weight syndrome decoding ($\mathsf{LWSD}$) is a recent variant whose ternary case was introduced by Debris-Alazard, Sendrier and Tillich (ASIACRYPT '19) in the security analysis of the $\mathsf{Wave}$ signature. It has different hardness characteristics from the classical low-weight $\mathsf{SD}$ problem. However, the security analysis of $\mathsf{LWSD}$ is still limited, and existing work mostly focuses on ternary instances. In this work, we study information set decoding (ISD) algorithms for $\mathsf{LWSD}$ over non-binary fields. Building on the ternary work of Bricout et al. (SAC '19), we give a generalized ISD framework for $\mathsf{LWSD}$ over $\mathbb{F}_q$. The framework is formulated as a single binary merge tree that unifies splitting-based, representation-based, and hybrid ISD algorithms. In particular, it captures known large-weight decoding algorithms as special cases and allows the merge pattern to be optimized together with the other ISD parameters. We evaluate the framework both asymptotically and concretely. For the asymptotic analysis, we give algorithmic landscapes for the whole $\mathsf{LWSD}$ regime and show which ISD algorithm gives the smallest asymptotic complexity for each instance. We also provide representative asymptotic complexities for several $\mathsf{LWSD}$ instances, including those corresponding to existing work. For the concrete analysis, we provide bit complexity estimates for the $\mathsf{Wave}$ parameter sets. These estimates remain above the claimed security levels.