Syndrome Decoding

The hard problem behind code-based cryptography — recovering an error pattern from its syndrome — NP-complete since 1978.

Core Principles & Analysis

• Proven NP-complete by Berlekamp, McEliece, and van Tilborg in 1978 — the same year the McEliece cryptosystem appeared.
• Decoding a random linear code is easy with the secret structure, intractable without it.
• Half a century of information-set decoding improvements have only shaved constants, not broken the exponent.

Specifications & Metrics

• TYPE: Hard problem
• YEAR: 1978