\(\mathcal{NP}\)-completeness of the Goppa parameterised random binary quasi-dyadic syndrome decoding problem (Q725962)

Summary: In 1978, the syndrome decoding problem (SDP) was proven to be \(\mathcal{NP}\)-complete for random binary codes. Since then, the security of several cryptographic applications relies on its hardness. In 2009, \textit{M. Finiasz} [\url{arxiv:0912.0453}] extended this result by demonstrating the \(\mathcal{NP}\)-completeness of certain subclasses of SDP. In this paper, we prove the \(\mathcal{NP}\)-completeness of the Goppa parameterised quasi-dyadic syndrome decoding problem. We use a reduction to the four-dimensional matching problem (proven \(\mathcal{NP}\)-complete).