liveBook · Manning

Hash-based signature scheme

As explained in Real-World Cryptography

A hash-based signature scheme is a digital signature scheme whose security is based on cryptographic hash-function properties rather than algebraic number-theoretic assumptions.

A hash-based signature scheme builds digital signatures from cryptographic hash functions rather than algebraic number-theoretic assumptions. Its security can rely on pre-image resistance, and modern hash functions make the approach naturally resistant to quantum computers. section 14.2

The basic construction grows from one-time signatures:

  • A Lamport one-time key pair uses two random secrets for each signable bit and publishes their individual hashes. section 14.2.1
  • Signing an n-bit message requires 2n secrets, so naive Lamport signatures are large and require strict one-time-key tracking. section 14.2.1
  • Modern designs extend the Lamport foundation to support many more signatures, more practical parameters, and sometimes stateless private keys. section 14.2.1

Why naive one-time signatures become bulky

Signing at most 1,000 messages of 256 bits with a 256-bit hash output would require roughly 16 megabytes for each private and public key. Reusing a one-time key pair must be avoided. section 14.2.1

How Real-World Cryptography covers it

How deep it goes
Explains Lamport construction, key-size costs, and state management, but stops short of full modern-scheme internals.
Examples
Uses one-bit and n-bit Lamport diagrams plus a 1,000-message, 256-bit example requiring roughly 16 megabytes.
What it assumes
Assumes familiarity with digital signatures and hash functions while building the one-time construction from random secrets and digests.
What you can do after
Evaluate/understand the tradeoffs among hash-only signatures, key size, signature count, and state tracking.
How it connects
Connects cryptographic hash functions, one-time signatures, Lamport signatures, post-quantum cryptography, XMSS, and SPHINCS+.
Cover of Real-World Cryptography
liveBookmanning.com
Read Real-World Cryptography on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Real-World Cryptography. The section links point to the parts of the book it draws on.