Syndrome decoding with MRHS solver

Authors

  • Miloslav Smičík Faculty of Electrical Engineering and Information Technology, Slovak University of Technology in Bratislava, Bratislava, Slovakia
  • Pavol Zajac Faculty of Electrical Engineering and Information Technology, Slovak University of Technology in Bratislava, Bratislava, Slovakia

DOI:

https://doi.org/10.24425/ijet.2025.153547

Abstract

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.

Published

2025-04-07

How to Cite

Smičík, Miloslav, and Pavol Zajac. “Syndrome Decoding With MRHS Solver”. International Journal of Electronics and Telecommunications, vol. 71, no. 1, Apr. 2025, doi:10.24425/ijet.2025.153547.

Issue

Section

Artykuły