Decoding Quasi-Cyclic codes is NP-complete

Ernesto Dominguez Fiallo; Pablo Freyre Arrozarena; Luis Ramiro Piñeiro

Paper 2023/1064

Decoding Quasi-Cyclic codes is NP-complete

Ernesto Dominguez Fiallo

, Institute of Cryptography, Havana University

Pablo Freyre Arrozarena, Institute of Cryptography, Havana University

Luis Ramiro Piñeiro, Institute of Cryptography, Havana University

Abstract

This paper establishes the computational complexity of the Quasi-Cyclic Syndrome Decoding Problem (QC-SDP). We introduce a novel characterization of Quasi-Cyclic (QC) codes that generalizes their structure and reveals connections to random codes. Building on this characterization, we prove that QC-SDP is NP-hard and that its decision variant is NP-complete. These results provide the first formal complexity treatment of QC-SDP in its general form, addressing a fundamental open question in code-based cryptography. We also discuss the practical implications and limitations of these theoretical findings for cryptographic applications.

Note: This version contains updated exposition and minor corrections throughout; the statements of all theorems and the main results are unchanged.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: Quasi-cylic codes Decoding NP-complete
Contact author(s): edominguezfiallo @ nauta cu
History: 2025-11-04: last of 2 revisions; 2023-07-07: received; See all versions
Short URL: https://ia.cr/2023/1064
License: CC0

BibTeX

@misc{cryptoeprint:2023/1064,
      author = {Ernesto Dominguez Fiallo and Pablo Freyre Arrozarena and Luis Ramiro Piñeiro},
      title = {Decoding Quasi-Cyclic codes is {NP}-complete},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1064},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1064}
}