Lamport One-Time Signatures

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.

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">{{lbl_message}}</div>
    <div class="ls-row">
      <input id="msg" type="text" maxlength="8" value="hello" autocomplete="off" spellcheck="false"/>
      <button id="genBtn" type="button">{{btn_generate}}</button>
    </div>
  </div>
  <div id="keyDisplay" class="ls-section hidden">
    <div class="ls-label">{{lbl_public_key}}</div>
    <div id="pkGrid" class="ls-grid"></div>
  </div>
  <div id="signSection" class="ls-section hidden">
    <button id="signBtn" type="button">{{btn_sign}}</button>
  </div>
  <div id="sigDisplay" class="ls-section hidden">
    <div class="ls-label">{{lbl_msg_hash}}</div>
    <div id="hashBits" class="ls-bits"></div>
    <div class="ls-label" style="margin-top:.7rem">{{lbl_signature}}</div>
    <div id="sigGrid" class="ls-grid"></div>
  </div>
  <div id="verifySection" class="ls-section hidden">
    <button id="verifyBtn" type="button">{{btn_verify}}</button>
  </div>
  <div id="result" class="ls-result hidden"></div>
  <div id="warn" class="ls-warn hidden">{{warn_spent}}</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; }

// Code not found

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.

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)$ — 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(2^{n}/2)$ with Grover's algorithm for collision attacks, but pre-image attacks remain $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.

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.

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.