CoreSource checked

Lamport One-Time Signature

Signs one message by revealing selected one-time secret values for its digest bits.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Cryptography
Difficulty: Intermediate
Family: Digital Signatures
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 0
Relationships: 3
Code example: Ready
Visualization: Ready

Overview

A Lamport one-time signature publishes hashes of paired secret values. To sign a digest, the signer reveals one secret from each pair, and the verifier hashes the revealed values to match the public key.

Core Concepts

one-time signaturesdigital signaturesbit maskscryptography

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(k)

Average

O(k^2)

Worst

O(k^3)

Space

O(k)

When to Use

Use when one-time signing semantics are acceptable and easy to enforce.
Use as a simple hash-based signature construction in educational or constrained settings.

When Not to Use

Avoid signing more than one message with the same key pair.
Avoid when signature size or key management overhead is too large.

What It Does

Generates secret value pairs for each digest bit
Publishes hashes of those secret values
Reveals one value from each pair to sign one message digest

Use Cases

Teaching hash-based signature ideas
One-time authentication where key reuse can be prevented
Building intuition for larger hash-based signature schemes

Inputs

Message, key, modulus, seed, or public parameters
Security parameter or nonce when required

Outputs

Cryptographic value such as signature, random bits, proof, or modular result

Pseudocode

1.Generate two random secret values for each digest bit position
2.Publish the hash of every secret value
3.Hash the message to a fixed-length digest
4.For each digest bit, reveal the matching secret value
5.Verify by hashing revealed values and comparing them with public-key entries

Canonical Example

Input: 2-bit digest = 10 with two secret pairs
Output: signature reveals secret[0][1] and secret[1][0]
Explanation: The verifier hashes the revealed secrets and compares them with the corresponding public-key hashes.

Implementation Notes

Generate independent random secret values for every digest bit and bit value.
Hash public-key values with a fixed, documented hash function.
Track key usage so each signing key is consumed exactly once.

Common Pitfalls

Reusing a Lamport key can reveal enough secrets to forge other messages.
Signing the raw message instead of a fixed-length digest changes the construction.
Weak randomness for secret values undermines the signature.