NP-completeness of the Goppa parameterised random binary quasi-dyadic syndrome decoding problem. (2017) - Cayrel, Pierre-Louis; Diagne, Mbouye Khady; Gueye, Cheikh Thiécoumba
In 1978, the syndrome decoding problem (SDP) was proven to be NP-complete for random binary codes. Since then, the security of several cryptographic applications relies on its hardness. In 2009, Finiasz extended this result by demonstrating the NP-completeness of certain subclasses of SDP. In this paper, we prove the NP-completeness of the Goppa parameterised quasi-dyadic syndrome decoding problem. We use a reduction to the four-dimensional matching problem (proven NP-complete).