Syndrome decoding with MRHS solver

The syndrome decoding problem (SDP) is an NPcomplete problem that has important applications in the development of post-quantum cryptography. Currently, the most efficient algorithms for SDP are based on the Information Set Decoding (ISD) approach that leverages efficiently time-memory and probability trade-offs. In our contribution, we explore a different approach based on transforming an instance of the SDP problem into a so-called Multiple Right-Hand-Sides (MRHS) Equation system. The MRHS system is then solved with a specialized MRHS solver. We explore how difficult is to solve (small) instances of SDP in MRHS form, and which trade-offs and parametric selections lead to the best results. Although our practical results are worse than those obtained by ISD, we believe that they show a better understanding of the connection between SDP and its MRHS representation, and can be a basis for future improvements.