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

We prove that the problem of decoding a Quasi-Cyclic (QC) code is NP-hard, and the corresponding decision problem is NP-complete. Our proof is based on a new characterization of quasi-cyclic codes closely related to linear random codes. We also discuss the cryptographic significance of this result.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: Quasi-cylic codes Decoding NP-complete
Contact author(s): edominguezfiallo @ nauta cu
History: 2023-07-12: revised; 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}
}