\(\mathcal{NP}\)-completeness of the Goppa parameterised random binary quasi-dyadic syndrome decoding problem (Q725962): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
| (3 intermediate revisions by 2 users not shown) | |||
| Property / author | |||
| Property / author: Cheikh Thiecoumba Gueye / rank | |||
| Property / author | |||
| Property / author: Cheikh Thiecoumba Gueye / rank | |||
Normal rank | |||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
| links / mardi / name | links / mardi / name | ||
Latest revision as of 01:05, 5 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | \(\mathcal{NP}\)-completeness of the Goppa parameterised random binary quasi-dyadic syndrome decoding problem |
scientific article |
Statements
\(\mathcal{NP}\)-completeness of the Goppa parameterised random binary quasi-dyadic syndrome decoding problem (English)
0 references
2 August 2018
0 references
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).
0 references
four dimensional matching problem
0 references
\(\mathcal{NP}\)-complete
0 references
quasi-dyadic Goppa codes
0 references
syndrome decoding problem
0 references
