Title: NP-completeness of the Goppa parameterised random binary quasi-dyadic syndrome decoding problem

Authors: Pierre-Louis Cayrel; Mbouye Khady Diagne; Cheikh Thiécoumba Gueye

Addresses: Laboratoire Hubert Curien, Jean-Monnet University of Saint Etienne, UMR CNRS 5516, Bâtiment F 18 rue du professeur Benoît Lauras, 42000 Saint-Etienne, France ' LACGAA, Faculté des Sciences et Techniques, Université Cheikh Anta Diop, DMI, Dakar, Sénégal ' LACGAA, Faculté des Sciences et Techniques, Université Cheikh Anta Diop, DMI, Dakar, Sénégal

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

Keywords: four dimensional matching problem; NP-complete; quasi-dyadic Goppa codes; syndrome decoding problem.

DOI: 10.1504/IJICOT.2017.086917

International Journal of Information and Coding Theory, 2017 Vol.4 No.4, pp.276 - 288

Received: 24 Feb 2017
Accepted: 05 Mar 2017
Published online: 02 Oct 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article