The McEliece Cryptosystem

Error-correcting codes exist to undo damage: scratch a CD, fade a deep-space signal, flip a bit in memory, and clever extra symbols let the receiver reconstruct the original. The whole point is that a little noise is easy to remove — if you know how the code is built.

In 1978, Robert McEliece asked a mischievous question: what if we hide the construction, scramble the code so it looks random, and then add the noise on purpose? Now the noise is no longer a nuisance — it's the lock. Anyone holding the secret recipe peels the noise off in an instant. Everyone else faces a code with no visible structure and a message buried under errors.

That single inversion — damage as encryption — gives one of the oldest public-key systems we have, and one of the very few still standing in the age of quantum computers.

Here is McEliece shrunk to seven bits. Pick a 4-bit message; we multiply it into a 7-bit codeword using a tiny error-correcting code, then flip exactly one bit on purpose. That noisy word is what gets sent.

<p class="hint">{{hint}}</p>

<div class="row">
  <span class="lbl">{{msg_label}}</span>
  <div id="msg" class="bits"></div>
  <button id="rnd" type="button" class="ghost">{{randomize}}</button>
</div>

<div class="pipe">
  <div class="stage"><div class="cap">{{cap_codeword}}</div><div id="code" class="bits big"></div></div>
  <div class="arrow">{{arrow_error}}</div>
  <div class="stage"><div class="cap">{{cap_sent}}</div><div id="sent" class="bits big"></div></div>
</div>

<div class="btns">
  <button id="enc" type="button">{{btn_encrypt}}</button>
  <button id="dec" type="button">{{btn_decode}}</button>
  <button id="atk" type="button" class="ghost">{{btn_attack}}</button>
</div>
<div class="status" id="status">{{status_initial}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.row { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin: .5rem 0; }
.lbl { font-size: .9rem; font-weight: 600; color: #1d3557; }
.bits { display: flex; gap: 4px; }
.bit { width: 30px; height: 34px; display: flex; align-items: center; justify-content: center;
       font: 700 16px ui-monospace, monospace; border-radius: 7px; background: #e8eef3;
       color: #1d3557; border: 1px solid #cdd9e3; user-select: none; }
.bits.big .bit { width: 34px; height: 38px; font-size: 17px; }
.bit.click { cursor: pointer; }
.bit.click:hover { background: #d6e1ea; }
.bit.one { background: #1d3557; color: #fff; border-color: #14243d; }
.bit.err { background: #e63946; color: #fff; border-color: #c92f3c; }
.bit.fixed { background: #0a7d33; color: #fff; border-color: #086627; }
.pipe { display: flex; align-items: center; gap: .8rem; flex-wrap: wrap; margin: .8rem 0; }
.stage { display: flex; flex-direction: column; gap: .25rem; }
.cap { font-size: .72rem; text-transform: uppercase; letter-spacing: .04em; color: #667; font-weight: 700; }
.arrow { font-size: .85rem; font-weight: 700; color: #c92f3c; }
.status { font-size: .95rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; line-height: 1.4; }
.status.ok { color: #0a7d33; } .status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .4rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Press Decode with trapdoor: knowing the code's parity structure, one calculation (the syndrome) names the flipped bit immediately and the message pops out. Then press Attack without trapdoor: with no structure to exploit, the only honest move is to try error patterns one by one. Our toy has just $2^{7}$ of them; real McEliece has astronomically more — which is exactly where the hardness lives.

What exactly is the attacker up against?

• With the trapdoor, decoding is easy. The secret is a code (originally a binary Goppa code) you actually know how to correct, plus two scrambling matrices that disguise it. The owner unscrambles, runs the code's fast decoder, then unscrambles back.
• Without it, the attacker sees a generator matrix that looks random and a word with errors. Finding the nearest codeword is the general decoding problem — and decoding a general linear code is NP-complete, proved by Berlekamp, McEliece and van Tilborg in 1978, the same year the cipher appeared.
• The status today. McEliece is not proven unbreakable — no public-key system is. But after more than four decades of attacks the best methods (information-set decoding) still cost exponential time, and the original Goppa-code parameters have never been broken.
• Quantum resistance. Shor's algorithm demolishes factoring and discrete logs — the foundations of RSA and elliptic-curve crypto. But it gives no useful speedup for decoding random codes; quantum search only halves the exponent. That is why McEliece is a NIST post-quantum finalist (standardized as Classic McEliece).

So the precise status is: believed hard, unbroken since 1978, and conjectured to stay hard even for quantum machines — resting on an NP-complete problem rather than on factoring like RSA.

McEliece sat as a curiosity for years — its keys are large — but the quantum threat moved it to center stage:

• Post-quantum security: as agencies plan for a future quantum computer, Classic McEliece is one of the most conservative key-encapsulation schemes on the table, prized precisely because it has survived so long unbroken.
• "Harvest now, decrypt later": data stolen today could be decrypted once quantum machines arrive. Code-based crypto protects long-lived secrets against that exact attack.
• The same hard core, everywhere: the decoding problem behind McEliece is the mirror image of the codes that fix errors on deep-space links, storage and mobile networks — one problem, used to repair in one direction and to protect in the other.
• A family of schemes: the trick of hiding hardness in noise also powers lattice-based systems like Learning With Errors, another pillar of the post-quantum standards.

Understand McEliece and you understand why "easy one way, hard the other" — the heartbeat of P vs NP — is the foundation of all public-key cryptography.

McEliece is a beautiful piece of judo: it takes noise, the thing error-correcting codes were invented to defeat, and turns it into the very wall protecting a secret. With the trapdoor the wall is paper-thin — one syndrome and the message falls out. Without it, you are decoding a structureless code, an NP-complete problem with no known shortcut.

Almost half a century after Robert McEliece proposed it in 1978, no one has broken the original system, and quantum computers — which shred RSA and factoring — offer no real foothold. The deepest secrets, it turns out, may be safest when they are hidden inside something deliberately broken.