Understanding LMS (Leighton-Micali Signatures)

By /

As we move toward a post-quantum world, hash-based signature schemes like XMSS and LMS are gaining attention. Both are designed to resist attacks from quantum computers by relying only on hash functions instead of fragile number-theoretic problems.

In this post, we’ll explain LMS (Leighton-Micali Signatures) in simple terms with an easy-to-follow example.

🔑 What is LMS?

LMS is a stateful hash-based signature scheme defined in RFC 8554 and standardized by NIST SP 800-208.

It works a lot like XMSS:

  • It combines many one-time signature keys using a Merkle tree.
  • Each one-time key signs one message only.
  • The Merkle tree compresses all the keys into a single public root.

The main difference is that LMS was designed for simplicity and efficiency in practice, with less overhead than XMSS.

🧩 Building Blocks of LMS

  1. LM-OTS (Leighton-Micali One-Time Signatures)
    • Each LM-OTS key pair can only be used once.
    • Based entirely on hash functions.
  2. Merkle Tree
    • Combines many LM-OTS keys into a single root (public key).
    • Each leaf corresponds to an LM-OTS public key.

🌱 A Toy Example (LMS with 4 Signatures)

Imagine we want an LMS key pair that can sign 4 messages.

Step 1: Generate One-Time Keys

We create 4 LM-OTS key pairs:

  • SK₁ / PK₁
  • SK₂ / PK₂
  • SK₃ / PK₃
  • SK₄ / PK₄

Step 2: Build the Merkle Tree

We hash these public keys together to build a tree:

vbnetCopyEdit       Root (Public Key)
         /          \
    Hash1             Hash2
   /     \           /     \
 PK1     PK2     PK3     PK4
  • The root hash is our LMS public key.
  • The private key contains all LM-OTS secret keys.

Step 3: Signing a Message

Suppose we want to sign Message B.

  1. Use the next unused LM-OTS key (SK₂).
  2. Create an LM-OTS signature for Message B.
  3. Include the authentication path (PK₁ and Hash2) so the verifier can rebuild the root.

So the signature includes:

  • The LM-OTS signature using SK₂
  • The authentication path (Hash values to reach the root)

Step 4: Verification

The verifier:

  1. Checks the LM-OTS signature with PK₂.
  2. Uses the authentication path to recompute the Merkle root.
  3. Compares the result with the known public key root.

If they match → ✅ signature is valid.

🚦 Why LMS Matters

  • Quantum resistant: Relies only on secure hash functions.
  • Efficient: Simpler and faster than XMSS for many use cases.
  • Standardized: Approved by NIST in SP 800-208.
  • Widely implemented: Easier to integrate into embedded systems and constrained devices.

📌 Limitations

  • Stateful: Like XMSS, you must track the number of signatures. If you reuse an LM-OTS key → security breaks.
  • Limited signatures: Each LMS key pair supports only as many signatures as tree leaves (decided when created).

🎯 Conclusion

LMS is a practical, hash-based post-quantum signature scheme that uses LM-OTS + Merkle trees to create a secure, quantum-resistant digital signature system.

It’s conceptually similar to XMSS but designed to be simpler and efficient in real-world deployments.

If you’re building quantum-safe systems today, LMS is one of the top candidates due to its NIST standardization and ease of implementation.

Scroll to Top