NP-completeness of Certain Sub-classes of the Syndrome Decoding Problem

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.

• Publication year

  2009

• Venue

  arXiv.org

• Publication date

  2009-12-02

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 0912.0453
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the inherent intractability of certain coding problems (Corresp.)

  1978cited by this paper

• Code-based Cryptography: Lecture Notes

  2023cites this paper
• A New variant of the McEliece cryptosystem based on the Smith form of convolutional codes

  2018cites this paper
• On the security of short McEliece keys from algebraic and algebraic geometry codes with automorphisms. (Étude de la sécurité de certaines clés compactes pour le schéma de McEliece utilisant des codes géométriques)

  2018cites this paper
• PKC-PC: A Variant of the McEliece Public Key Cryptosystem based on Polar Codes

  2017influential citation
• NP-completeness of the random binary quasi-dyadic coset weight problem and the random binary quasi-dyadic subspace weight problem

  2016influential citation
• A NOVEL VLSI BASED CRYPTOCODING TECHNIQUE USING ERROR CONTROL ALGORITHM

  2015cites this paper
• Secret Key Cryptosystem Based on Non-systematic Polar Codes

  2013cites this paper
• Attacking and Defending Code-based Cryptosystems

  2012cites this paper