Paper 2023/1064 Original: eprint.iacr.org/2023/1064 ↗
Decoding Quasi-Cyclic codes is NP-complete
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.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2025-11-04: last updated
- 2023-07-07: published
- Short URL
- https://ia.cr/2023/1064
- License
- https://creativecommons.org/publicdomain/zero/1.0/
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}
}