Introduction

Every time you visit a website over HTTPS, check a software update, or send a signed email, a digital signature is in play. A signature lets you prove you created a message without letting anyone else forge your name. Today almost all signatures — RSA, ECDSA, EdDSA — rest on the hardness of factoring large integers or computing discrete logarithms. Shor's algorithm, run on a large enough quantum computer, breaks both in polynomial time.

Lamport signatures, invented by Leslie Lamport in 1979, take a completely different road. They need no number theory at all. The only mathematical primitive is a one-way hash function — a function easy to compute forward but hard to invert. The security proof is simple: forging a signature requires inverting a hash, and no known classical or quantum algorithm does that efficiently.

The catch? Each key pair can sign exactly one message and must never be reused. That single-use constraint sounds severe, but it is precisely what makes the scheme so elegant and easy to understand — and it is the seed from which modern hash-based signature trees like XMSS grow.

Sign a Message

The demo below lets you generate a fresh Lamport key pair, type a short message, sign it, and verify the signature. Each step is shown in full so you can see exactly which secrets are revealed.

<div class="ls-wrap">
  <div class="ls-section">
    <div class="ls-label">Message to sign (max 8 chars)</div>
    <div class="ls-row">
      <input id="msg" type="text" maxlength="8" value="hello" autocomplete="off" spellcheck="false"/>
      <button id="genBtn" type="button">Generate key pair</button>
    </div>
  </div>
  <div id="keyDisplay" class="ls-section hidden">
    <div class="ls-label">Public key (hashes — these are public)</div>
    <div id="pkGrid" class="ls-grid"></div>
  </div>
  <div id="signSection" class="ls-section hidden">
    <button id="signBtn" type="button">Sign message</button>
  </div>
  <div id="sigDisplay" class="ls-section hidden">
    <div class="ls-label">Message hash (first 8 bits shown)</div>
    <div id="hashBits" class="ls-bits"></div>
    <div class="ls-label" style="margin-top:.7rem">Signature (revealed pre-images — one per bit)</div>
    <div id="sigGrid" class="ls-grid"></div>
  </div>
  <div id="verifySection" class="ls-section hidden">
    <button id="verifyBtn" type="button">Verify signature</button>
  </div>
  <div id="result" class="ls-result hidden"></div>
  <div id="warn" class="ls-warn hidden">Key pair spent — generate a new one to sign again.</div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.ls-wrap { padding: .25rem 0; }
.ls-section { margin-bottom: .9rem; }
.ls-label { font-size: .78rem; font-weight: 700; text-transform: uppercase;
            letter-spacing: .04em; color: #5a7088; margin-bottom: .35rem; }
.ls-row { display: flex; gap: .5rem; align-items: center; flex-wrap: wrap; }
input[type=text] { font: 15px ui-monospace, monospace; padding: .4rem .6rem;
                   border: 1px solid #cdd9e3; border-radius: 6px; width: 140px; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 6px; cursor: pointer; white-space: nowrap; }
button:disabled { opacity: .4; cursor: default; }
.ls-grid { display: flex; flex-wrap: wrap; gap: 3px; }
.ls-cell { font: 11px ui-monospace, monospace; padding: 3px 5px; border-radius: 4px;
           border: 1px solid #d0dae3; background: #edf2f7; color: #1d3557; max-width: 80px;
           overflow: hidden; text-overflow: ellipsis; white-space: nowrap; }
.ls-cell.revealed { background: #d4edda; border-color: #82c89a; color: #1a4731; }
.ls-cell.hidden-key { background: #f8d7da; border-color: #e89ba3; color: #721c24; }
.ls-bits { display: flex; gap: 4px; flex-wrap: wrap; }
.ls-bit { width: 28px; height: 28px; display: flex; align-items: center; justify-content: center;
          font: 700 13px ui-monospace; border-radius: 5px; border: 1px solid; }
.ls-bit.b0 { background: #edf2f7; border-color: #cdd9e3; color: #1d3557; }
.ls-bit.b1 { background: #1d3557; border-color: #1d3557; color: #fff; }
.ls-result { font-weight: 700; font-size: 1rem; padding: .5rem .8rem; border-radius: 6px; margin-top: .3rem; }
.ls-result.ok { background: #d4edda; color: #155724; }
.ls-result.bad { background: #f8d7da; color: #721c24; }
.ls-warn { background: #fff3cd; color: #856404; border: 1px solid #ffc107;
           padding: .4rem .7rem; border-radius: 6px; font-size: .85rem; }
.hidden { display: none !important; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Lamport one-time signature demo (educational, uses a simple in-browser hash).
// Security note: this uses a toy XOR+rotate hash for visual clarity.
// Real implementations use SHA-256 or stronger.

const BITS = 8; // sign the first 8 bits of a simple hash of the message

// --- Toy one-way hash (for demo only) ---
// Produces BITS bits from an arbitrary byte sequence.
function toyHash(bytes) {
  // Mix bytes with a simple polynomial: accumulate into a 32-bit state.
  let h = 0x5f3759df;
  for (let i = 0; i < bytes.length; i++) {
    h = Math.imul(h ^ bytes[i], 0x9e3779b9);
    h ^= (h >>> 17);
    h = Math.imul(h, 0x85ebca6b);
    h ^= (h >>> 13);
  }
  // Extract BITS bits
  const bits = [];
  for (let i = 0; i < BITS; i++) bits.push((h >>> i) & 1);
  return bits;
}

// Hash a single 32-bit integer (used to hash private key entries).
function hashInt(n) {
  let h = Math.imul(n ^ 0xdeadbeef, 0x9e3779b9);
  h ^= (h >>> 17);
  h = Math.imul(h, 0x85ebca6b);
  h ^= (h >>> 13);
  h = Math.imul(h, 0xc2b2ae35);
  h ^= (h >>> 16);
  return h >>> 0; // unsigned 32-bit
}

function hex8(n) { return (n >>> 0).toString(16).padStart(8, '0'); }

// --- Key generation ---
// Private key: sk[i][b] = random 32-bit integer for bit i, value b∈{0,1}
// Public key:  pk[i][b] = hashInt(sk[i][b])
let sk = null, pk = null, msgBits = null, signature = null, spent = false;

function generateKeyPair() {
  sk = [];
  pk = [];
  for (let i = 0; i < BITS; i++) {
    const s0 = (Math.random() * 0xffffffff) >>> 0;
    const s1 = (Math.random() * 0xffffffff) >>> 0;
    sk.push([s0, s1]);
    pk.push([hashInt(s0), hashInt(s1)]);
  }
  msgBits = null; signature = null; spent = false;
}

// --- Signing ---
function sign(message) {
  // Compute hash of message bytes
  const bytes = [...message].map(c => c.charCodeAt(0));
  msgBits = toyHash(bytes);
  signature = msgBits.map((b, i) => sk[i][b]);
}

// --- Verification ---
function verify() {
  if (!signature || !msgBits || !pk) return false;
  return signature.every((s, i) => hashInt(s) === pk[i][msgBits[i]]);
}

// --- UI ---
const genBtn = document.getElementById('genBtn');
const signBtn = document.getElementById('signBtn');
const verifyBtn = document.getElementById('verifyBtn');
const msgInput = document.getElementById('msg');

function show(id) { document.getElementById(id).classList.remove('hidden'); }
function hide(id) { document.getElementById(id).classList.add('hidden'); }

function renderPK() {
  const grid = document.getElementById('pkGrid');
  grid.innerHTML = '';
  for (let i = 0; i < BITS; i++) {
    for (let b = 0; b < 2; b++) {
      const cell = document.createElement('div');
      cell.className = 'ls-cell';
      cell.title = `pk[${i}][${b}] = hash(sk[${i}][${b}])`;
      cell.textContent = hex8(pk[i][b]);
      grid.appendChild(cell);
    }
  }
}

function renderSig() {
  const bitsDiv = document.getElementById('hashBits');
  bitsDiv.innerHTML = '';
  msgBits.forEach((b, i) => {
    const d = document.createElement('div');
    d.className = `ls-bit b${b}`;
    d.title = fmt('bit %i% = %b%', { i: i, b: b });
    d.textContent = b;
    bitsDiv.appendChild(d);
  });

  const grid = document.getElementById('sigGrid');
  grid.innerHTML = '';
  for (let i = 0; i < BITS; i++) {
    // Show revealed pre-image
    const revCell = document.createElement('div');
    revCell.className = 'ls-cell revealed';
    revCell.title = fmt('revealed: sk[%i%][%v%]', { i: i, v: msgBits[i] });
    revCell.textContent = hex8(signature[i]);
    grid.appendChild(revCell);

    // Show that the opposite pre-image stays hidden
    const hidCell = document.createElement('div');
    hidCell.className = 'ls-cell hidden-key';
    hidCell.title = fmt('hidden: sk[%i%][%v%] (never revealed)', { i: i, v: 1 - msgBits[i] });
    hidCell.textContent = '????????';
    grid.appendChild(hidCell);
  }
}

genBtn.addEventListener('click', () => {
  generateKeyPair();
  renderPK();
  hide('warn');
  hide('sigDisplay');
  hide('verifySection');
  hide('result');
  show('keyDisplay');
  show('signSection');
  signBtn.disabled = false;
});

signBtn.addEventListener('click', () => {
  if (spent) { show('warn'); return; }
  const msg = msgInput.value || 'hello';
  sign(msg);
  spent = true;
  signBtn.disabled = true;
  renderSig();
  show('sigDisplay');
  show('verifySection');
  hide('result');
  hide('warn');
});

verifyBtn.addEventListener('click', () => {
  const ok = verify();
  const res = document.getElementById('result');
  res.className = 'ls-result ' + (ok ? 'ok' : 'bad');
  res.textContent = ok
    ? '✓ Signature valid — every hash(revealed) matches the public key.'
    : '✗ Signature invalid — hash mismatch detected.';
  show('result');
  if (spent) show('warn');
});

// Auto-generate on load
generateKeyPair();
renderPK();
show('keyDisplay');
show('signSection');
Result
Console

Notice the one-time constraint: after signing, the key pair is spent. The demo shows which pre-images were revealed; an attacker who intercepts the signature can see those values — but to forge a different message they would need pre-images for the opposite bit values, which remain hidden and can only be found by inverting the hash.

The Real Security

How secure is a Lamport signature, and what does it cost?

  • Key generation: pick 2n random secrets (two per message bit). Hash each one to get the public key. With a 256-bit hash and 256-bit messages, that is 512 secrets and 512 public values.
  • Signing: for each bit i of the message hash, reveal secret[i][bit_i]. Half the secrets stay hidden.
  • Verification: hash the revealed secrets and compare to the corresponding public values. Checking is O(n)O(n) — trivially fast.
  • Security reduction: forging a signature on any different message requires revealing a pre-image the signer never exposed. That is exactly inverting the hash function. No classical or quantum algorithm inverts a good hash faster than brute force (O(2n/2)O(2^{n}/2) with Grover's algorithm for collision attacks, but pre-image attacks remain O(2n)O(2^{n})).
  • Quantum safety: Shor's algorithm breaks factoring and discrete log — it has no leverage on hash inversion. Lamport signatures with a 256-bit hash remain secure against known quantum attacks, unlike RSA or ECDSA.
  • One-time limit: once a key is used, the attacker learns half the secrets. Reusing the key to sign a second message could expose enough secrets to forge a third. This is the fundamental trade-off: simplicity and quantum safety in exchange for a strict single-use rule.

Compared to RSA-2048 (~256-byte signature) or Ed25519 (64 bytes), a Lamport signature is large — about 8 KB for 256-bit security. The key sizes are even larger. Practical post-quantum schemes like XMSS and SPHINCS+ build Merkle trees of Lamport keys to allow many signatures from one root key, at the cost of complexity.

Where It Matters

Lamport signatures are not just a curiosity — they are the conceptual root of an entire family of real-world post-quantum tools:

  • Post-quantum standards: NIST's post-quantum cryptography process selected SPHINCS+ (now SLH-DSA) as one of its signature standards. SPHINCS+ is built on hash-based one-time signatures directly descended from Lamport's idea.
  • XMSS and LMS: RFC 8391 (XMSS) and RFC 8554 (LMS/HSS) are stateful hash-based signatures standardized by IETF. They chain Lamport-style OTS keys in a Merkle tree to allow thousands of signatures from one root key.
  • Blockchain and timestamping: early Bitcoin proposals and some blockchain designs use hash-based signatures to achieve quantum resistance without modifying the hash-chain structure.
  • Firmware and software signing: devices with long lifetimes (industrial controllers, satellites) may still be operating when quantum computers mature. Hash-based signatures are a drop-in upgrade path for firmware signing.
  • Teaching cryptography: Lamport signatures are one of the clearest illustrations of how security can be built from minimal assumptions — a single one-way function is all you need, connecting to the theory of factoring and discrete logarithms.

Conclusion

Lamport signatures distil digital signing to its logical core: hide two secrets per bit, reveal one when you sign, and let the hash function do all the heavy lifting. There is no modular arithmetic, no elliptic curve, no structure that a quantum computer can exploit.

The one-time constraint is the price of that simplicity. But every serious post-quantum signature scheme — XMSS, LMS, SPHINCS+ — pays it too, just with bookkeeping that hides the cost. Understanding Lamport means understanding why hash functions are the bedrock of post-quantum cryptography, and why the coming quantum era does not spell the end of digital trust.

Want to dig deeper into the asymmetry between easy and hard problems in cryptography? Explore factoring or learning with errors — the hard problems that underpin everything else we rely on.

Share this article

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

Comments

Loading comments...

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