NP-completeness of the Goppa parameterised random binary quasi-dyadic syndrome decoding problem. (2017)

• Record Type: Journal Article
• Authors: Cayrel, Pierre-Louis; Diagne, Mbouye Khady; Gueye, Cheikh Thiécoumba
• Is Part Of: International journal of information and coding theory. Volume 4:Number 4(2017)
• Page Start: 276
• Page End: 288
• Publication Date: 2017
• Subjects: four dimensional matching problem -- NP-complete -- quasi-dyadic Goppa codes -- syndrome decoding problem; Coding theory -- Periodicals; Information theory -- Periodicals; 003.54
• Languages: English
• ISSNs: 1753-7703

Abstract

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).