A hybrid algorithm for the regular syndrome decoding problem

Abstract. The regular syndrome decoding (RSD) problem is a variant of the classic syndrome decoding problem where the error vector is constrained to have a regular structure, namely exactly one non-zero entry in each of several equal-sized blocks. RSD underlies the security of several code-based cryptographic schemes. In this work, we propose a hybrid algorithm for solving the RSD problem that combines information set decoding techniques with meet-in-the-middle approaches. Our algorithm achieves a significant improvement over the state-of-the-art, reducing the computational complexity for solving RSD across a wide range of parameters. We provide theoretical analysis of the algorithm’s complexity and validate it through experimental results, demonstrating the concrete security implications for schemes relying on the hardness of RSD.