Information-Set Decoding
Information-set decoding is the family of algorithms that attacks code-based cryptography head-on: given a random-looking linear code and a corrupted codeword, it hunts for the low-weight error pattern that a legitimate holder of the private key strips out instantly. It’s the best known attack on the whole family, classical or quantum, and its defining property is that it stays exponential no matter how cleverly it’s refined. Ed Prange published the first version in 1962, and 60-plus years of improvement since (Stern, MMT, BJMM) have shaved the exponent without changing its shape. That stubborn exponential cost is exactly what code-based cryptographers count on. It’s also what forces the large keys of Classic McEliece, BIKE, and HQC, because a big code is the price of pushing the attack out of reach.
The short version:
- Information-set decoding (ISD) is the leading attack on code-based schemes. It tries to solve the same decoding problem the private key solves, but without the hidden structure, so it has to search.
- Every known variant runs in exponential time in the code parameters. Decades of refinement have lowered the exponent’s constant, never removed the exponential.
- The lineage runs Prange (1962) → Stern (1988) → MMT (2011) → BJMM (2012), each buying a smaller exponent with more memory and cleverer collision-finding.
- A quantum computer helps only modestly. There’s no Shor’s-style collapse here; the quantum versions get roughly a Grover-like square-root speedup on the search, so parameters are simply set larger to absorb it.
- ISD is why code-based keys are big. The security level is tied to how expensive the best ISD attack is, so hitting a target strength means choosing a code large enough that the attack’s exponential cost clears the bar.
Picture a very long combination lock where you know that exactly, say, 50 of the 3,000 dials are turned off-zero, but not which 50. The legitimate owner has a wiring diagram that reveals them at a glance. You don’t, so your only move is to guess which dials might be the untouched ones, solve a quick linear system on that guess, and check whether the leftover weight is small enough. Guess right and it falls open in one step. Guess wrong, which is almost always, and you try again. Information-set decoding is that guess-solve-check loop, and its cost is governed by how rare a lucky guess is. Every improvement in 60 years has been a smarter way to make each guess cover more ground, and none has escaped the fact that lucky guesses stay exponentially rare.
What is information-set decoding?
Information-set decoding is a method for solving the syndrome decoding problem: recover a low-weight error vector from a random-looking linear code and a corrupted codeword. An “information set” is a subset of coordinate positions that, if you assume the error avoids them, lets you pin down the rest of the error by ordinary linear algebra. The attacker guesses such a set, does a fast Gaussian-elimination step, and checks whether the recovered error has the low weight a real solution must have. If not, guess again.
The general decoding problem this attacks is NP-hard, which is the theoretical floor under the whole family. ISD is what the floor looks like in practice: the concrete, best-we-know algorithm whose running time sets the actual security estimate a scheme is parameterized against.
Source: E. Prange, “The use of information sets in decoding cyclic codes,” IEEE Transactions on Information Theory 8(5), 1962, DOI 10.1109/TIT.1962.1057777, which introduced the information-set idea that the entire attack lineage builds on.
The reason this matters for a cryptosystem is direct. A code-based public key is a scrambled code plus, in encryption, a ciphertext that’s a codeword with a deliberate error added. Anyone can add the error; only the private key’s hidden structure removes it cheaply. An attacker without that structure is left with exactly the problem ISD solves, and the scheme is secure precisely to the degree that ISD is slow.
Why does information-set decoding stay exponential?
Information-set decoding stays exponential because success on each attempt depends on a lucky event whose probability shrinks exponentially as the code grows. The attacker needs the guessed information set to interact with the unknown error in just the right way, and the fraction of guesses that do falls off geometrically with the code length and error weight. No known reformulation removes that dependence; the improvements attack how much work each attempt does and how many candidate errors a single pass can test, not the exponential rarity of a good outcome.
That’s the load-bearing fact for the transition. Code-based security rests on a problem where the best attack has resisted a sub-exponential breakthrough for over half a century, which is the longest such record in post-quantum cryptography. The confidence in Classic McEliece comes almost entirely from this: the McEliece cryptosystem has stood since 1978, and the reason is that ISD, its natural attack, has never dropped below exponential.
Source: NIST IR 8545, Status Report on the Fourth Round of the NIST PQC Standardization Process, March 2025, which standardizes the code-based KEM HQC on the strength of this decoding hardness.
How have the attacks improved over time?
The attacks have improved by making each guess-solve-check pass cover more candidate errors, usually by trading memory for a smaller time exponent. The lineage is a chain of refinements, each measured by the constant in a running time of the form 2^(cn) for a code of length n.
| Algorithm | Year | Core idea | Effect on the exponent |
|---|---|---|---|
| Prange | 1962 | Guess an information set, solve, check weight | The baseline exponential |
| Stern | 1988 | Split the search and match halves with a birthday-style collision | First major exponent drop |
| MMT (May-Meurer-Thomae) | 2011 | Represent the error many ways to enlarge the collision search | Lowered the constant to ~0.0537 |
| BJMM (Becker-Joux-May-Meurer) | 2012 | Push the representation technique further, using that 1+1=0 in binary | Lowered the constant to ~0.0494 |
Source: J. Stern, “A method for finding codewords of small weight,” Coding Theory and Applications, LNCS 388, 1989 (presented 1988), SpringerLink, the birthday-collision refinement of Prange.
Source: A. Becker, A. Joux, A. May, A. Meurer, “Decoding Random Binary Linear Codes in 2^(n/20): How 1+1=0 Improves Information Set Decoding,” Eurocrypt 2012, IACR ePrint 2012/026, which states its running time of 2^(0.0494n), improving the prior 2^(0.0537n) bound of May, Meurer, and Thomae.
The pattern to hold onto: every step lowered the constant c and every step left the 2^(cn) shape intact. The exponent got a little smaller; the exponential never went away. That’s why designers respond to a new ISD result by nudging parameters up, not by abandoning the family.
Does a quantum computer break information-set decoding?
A quantum computer speeds up information-set decoding, but only in the mild way it speeds up any search, so it doesn’t break the family. The core of ISD is a search over candidate information sets, and Grover’s algorithm gives a square-root speedup on unstructured search. Applied to ISD, that roughly halves the exponent, turning a 2^(cn) attack into something near 2^(cn/2). The published quantum versions of Prange’s and Stern’s algorithms deliver exactly this order of improvement.
Source: G. Kachigar and J.-P. Tillich, “Quantum Information Set Decoding Algorithms,” PQCrypto 2017, IACR ePrint 2017/213, which develops the Grover-accelerated quantum ISD variants.
What matters is the contrast with Shor’s algorithm. Shor’s collapses factoring and discrete logs from exponential to polynomial, which is what ends RSA and elliptic-curve cryptography. Nothing like that is known for decoding. The best quantum ISD is still exponential, just with a smaller exponent, so the fix is the same one that handles Grover against symmetric keys: pick a larger code. Code-based parameters already fold this square-root headroom into their security levels, which is part of why the keys are as large as they are.
Why does information-set decoding make the keys so big?
Information-set decoding makes code-based keys big because the security level is defined by the attack’s cost, and the attack’s cost is exponential in the size of the code. To claim a given strength (say, matching AES-128 against the best known attack), a scheme must choose a code long enough that the cheapest ISD run exceeds that many operations. Bigger code, bigger public key. The key size is essentially the invoice for buying enough exponential distance from ISD.
This lands hardest on Classic McEliece, whose binary-Goppa-code public keys run from hundreds of kilobytes up toward a megabyte, precisely because it’s parameterized conservatively against ISD with generous margin. HQC and BIKE use quasi-cyclic codes, a structured shape that lets one row generate the whole code and shrinks the key by a large factor, while still resting on the same ISD-governed hardness for the underlying decoding problem.
Source: NIST IR 8545, March 2025, which records HQC as the selected code-based KEM and its size profile relative to Classic McEliece.
So the tradeoff at the center of code-based cryptography traces straight back to this attack. You want the confidence of a decoding problem that ISD has failed to crack for 60 years, and the entry fee for that confidence is a public key sized to keep ISD exponentially far away.
Common misconceptions
“Information-set decoding was broken, so code-based crypto is weak.” ISD has been improved many times and never broken the exponential barrier. Each refinement lowered the exponent’s constant and prompted a small parameter bump, which is routine maintenance, not a break. The family’s reputation rests on ISD’s persistent failure to go sub-exponential.
“A quantum computer decodes these codes the way Shor’s factors RSA.” It doesn’t. Quantum ISD gets a Grover-style square-root speedup, which larger parameters absorb, with no Shor-style exponential collapse. The decoding problem has no known structure a quantum computer can exploit that way.
“The big keys are the vulnerability.” The large key is a consequence of the security proof, not a weakness. Keys are sized so that ISD’s exponential cost clears the target strength; the size is the cost of that safety margin.
“BJMM broke McEliece.” BJMM improved the ISD exponent to about 2^(0.0494n), a meaningful cryptanalytic advance that still leaves the attack exponential and Classic McEliece’s parameters comfortably out of reach. Designers accounted for it by parameter choice, and the scheme has never been practically broken.
Questions people ask
What is information-set decoding in one sentence? It’s the best known algorithm for recovering the secret low-weight error in a random-looking linear code, which is the problem an attacker faces against every code-based scheme, and it runs in exponential time.
Who invented it and when? Ed Prange introduced the information-set idea in 1962, and the modern high-performance variants (Stern 1988, MMT 2011, BJMM 2012) are refinements of that same core loop (IACR ePrint 2012/026).
Does information-set decoding threaten HQC? No more than it threatens any code-based scheme. HQC’s parameters are set so the best ISD attack, classical or quantum, exceeds its target security level, which is exactly why NIST could select it as a backup KEM in 2025.
Could a smaller code shrink the keys? Only by weakening the scheme, because shrinking the code cheapens the ISD attack. The key size and the security level are two ends of the same lever, so a smaller key means a smaller security margin.
Information-set decoding is the reason code-based cryptography can point to a longer unbroken record than anything else in the field, and the reason its keys are the largest. Everything here is the map, given freely. When your team needs to decide where a code-based backup actually fits in your protocols and estate, that’s what an alignment briefing is for.
Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.