NP-completeness of the Goppa parameterised random binary quasi-dyadic syndrome decoding problem
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).
- NP-completeness of the random binary quasi-dyadic coset weight problem and the random binary quasi-dyadic subspace weight problem
- Some new NP-complete coding problems
- scientific article; zbMATH DE number 1759341
- A NP-complete problem in coding theory with application to code based cryptography
- An algorithm for generalized syndrome decoding problem
This page was built for publication: \(\mathcal{NP}\)-completeness of the Goppa parameterised random binary quasi-dyadic syndrome decoding problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q725962)
