Introduction

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.

Try It: Encrypt by Breaking

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">McEliece in miniature. Your <b>4-bit message</b> is multiplied into a 7-bit <b>codeword</b>, then we deliberately flip <b>one bit</b> (the secret error). With the trapdoor — knowing the code's parity structure — decoding is a single table lookup. Without it, an attacker must search.</p>

<div class="row">
  <span class="lbl">Message (4 bits):</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">Codeword (G&middot;m)</div><div id="code" class="bits big"></div></div>
  <div class="arrow">+ error &rarr;</div>
  <div class="stage"><div class="cap">Sent (with 1 flip)</div><div id="sent" class="bits big"></div></div>
</div>

<div class="btns">
  <button id="enc" type="button">Encrypt &amp; corrupt</button>
  <button id="dec" type="button">Decode with trapdoor</button>
  <button id="atk" type="button" class="ghost">Attack without trapdoor</button>
</div>
<div class="status" id="status">Pick a message, then press Encrypt &amp; corrupt.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// ── A toy McEliece, built on the Hamming(7,4) code ───────────────────────────
// Real McEliece hides a Goppa code that can correct t errors. We use the tiny
// Hamming(7,4) code (corrects 1 error) so the idea is visible:
//   * Public side: encode message m (4 bits) into codeword c = G·m (7 bits), then add ONE bit of noise. That noisy word is what travels.
//   * Trapdoor (secret): the parity-check matrix H. Compute the SYNDROME H·r; a nonzero syndrome equals the column of the flipped position — one lookup pinpoints and repairs the error. Decoding is instant.
//   * Attacker: sees only the noisy word and a scrambled-looking code. With no structure to exploit, the honest move is to TRY every error pattern — "syndrome decoding" of a general linear code, proven NP-complete (Berlekamp, McEliece & van Tilborg, 1978).

// p1=d1^d2^d3, p2=d1^d2^d4, p3=d1^d3^d4 (systematic Hamming(7,4))
function encode(m){ const [a,b,c,d]=m; return [a,b,c,d, a^b^c, a^b^d, a^c^d]; }
const H = [[1,1,1,0,1,0,0],[1,1,0,1,0,1,0],[1,0,1,1,0,0,1]];
const syndrome = r => H.map(row => row.reduce((s,h,i)=>s^(h&r[i]),0));

let msg=[1,0,1,1], code=null, sent=null, errPos=-1, corrupted=false;

const $ = id => document.getElementById(id);
function setStatus(t,cls){ const s=$('status'); s.innerHTML=t; s.className='status '+(cls||''); }
function render(){
  // message (clickable)
  const mb=$('msg'); mb.innerHTML='';
  msg.forEach((v,i)=>{ const d=document.createElement('div');
    d.className='bit click'+(v?' one':''); d.textContent=v;
    d.addEventListener('click',()=>{ msg[i]^=1; corrupted=false; reset(); render(); });
    mb.appendChild(d); });
  // codeword
  const cb=$('code'); cb.innerHTML='';
  (code||Array(7).fill('·')).forEach((v)=>{ const d=document.createElement('div');
    d.className='bit'+(v===1?' one':''); d.textContent=v; cb.appendChild(d); });
  // sent
  const sb=$('sent'); sb.innerHTML='';
  (sent||Array(7).fill('·')).forEach((v,i)=>{ const d=document.createElement('div');
    let cls='bit'+(v===1?' one':''); if(i===errPos) cls='bit err';
    d.className=cls; d.textContent=v; sb.appendChild(d); });
}
function reset(){ code=null; sent=null; errPos=-1; }

function doEncrypt(){
  code = encode(msg);
  errPos = Math.floor(Math.random()*7);
  sent = code.slice(); sent[errPos]^=1;
  corrupted=true; render();
  setStatus(fmt('Codeword sent with a hidden flip at position %errPos%%v%. To anyone without the trapdoor it is just a noisy 7-bit string.', { errPos: errPos, v: 1 }),'');
}
function doDecode(){
  if(!corrupted){ setStatus('Encrypt first.','bad'); return; }
  const s = syndrome(sent);
  let found=-1;
  for(let i=0;i<7;i++){ const col=H.map(row=>row[i]);
    if(col.every((b,k)=>b===s[k]) && s.some(x=>x)) { found=i; break; } }
  const fixed = sent.slice(); if(found>=0) fixed[found]^=1;
  const rec = fixed.slice(0,4);
  // show repair
  const sb=$('sent'); sb.innerHTML='';
  fixed.forEach((v,i)=>{ const d=document.createElement('div');
    d.className='bit'+(i===found?' fixed':(v===1?' one':'')); d.textContent=v; sb.appendChild(d); });
  const okMsg = rec.join('')===msg.join('');
  setStatus(fmt('Syndrome H&middot;r = [%s%] &rarr; error at position %found%%v%. Repaired in <b>1 lookup</b>. Recovered message <b>%rec%</b> %v2%', { s: s.join(' '), found: found, v: 1, rec: rec.join(''), v2: okMsg?'&mdash; correct.':'&mdash; mismatch?!' }), okMsg?'ok':'bad');
  console.log('syndrome', s, 'error pos', found+1, 'recovered', rec.join(''));
}
function doAttack(){
  if(!corrupted){ setStatus('Encrypt first.','bad'); return; }
  // Attacker with no trapdoor: try every error pattern until the word becomes a valid codeword (zero syndrome). Here, weight-≤1 patterns = 8 tries; real
  // parameters make this 2^hundreds. We count the tries to show the blow-up.
  let tries=0, hit=-1;
  for(let pattern=0; pattern<(1<<7); pattern++){ tries++;
    const cand = sent.map((b,i)=> b ^ ((pattern>>i)&1));
    if(syndrome(cand).every(x=>x===0) &&
       ((pattern & (pattern-1))===0)) { hit=pattern; break; } // smallest-weight guess
  }
  setStatus('No trapdoor: the attacker brute-forces error patterns. Toy code &rarr; up to 2<sup>7</sup>=128 patterns. Real McEliece uses ~2<sup>800</sup>+ &mdash; <b>general decoding is NP-complete</b>, so this search never finishes.','bad');
  console.log('attacker scanned', tries, 'patterns before a valid codeword');
}

$('rnd').addEventListener('click',()=>{ msg=msg.map(()=>Math.random()<.5?1:0); corrupted=false; reset(); render(); setStatus('New message. Press Encrypt & corrupt.',''); });
$('enc').addEventListener('click',doEncrypt);
$('dec').addEventListener('click',doDecode);
$('atk').addEventListener('click',doAttack);
render();
Result
Console

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 272^{7} of them; real McEliece has astronomically more — which is exactly where the hardness lives.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/mceliece/Content licensed under CC BY-NC 4.0.