2009/12/02 by Matthieu Finiasz, Finiasz, Matthieu
Computer Science · Engineering · #Coding theory and cryptography #Computational Complexity (cs.CC) #Cryptographic Implementations and Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #cs.CC #cs.CR #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.0912.0453
arxiv created 2009/12/02 · openalex publication_date 2009/12/02 · arxiv updated 2009/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The problem of Syndrome Decoding was proven to be NP-complete in 1978 and, since then, quite a few cryptographic applications have had their security rely on the (provable) difficulty of solving some instances of it. However, in most cases, the instances to be solved follow some specific constraint: the target weight is a function of the dimension and length of the code. In these cases, is the Syndrome Decoding problem still NP-complete? This is the question that this article intends to answer.