Hash-Based Signature Schemes

Corresponds to Chapter 14 (the basic idea of Lamport one-time signatures from collision-resistant hashing is already covered in digital-signatures-and-pki). Covers the practical engineering of hash-based signatures: shrinking a basic Lamport signature using an enhanced target-collision-resistant hash, the general Lamport framework and an explicit “containment-free” function it needs, Winternitz signatures (a size/computation tradeoff via a “domination-free” function, letting one hash chain sign several bits at once), and HORS (a differently-structured short signature). Shrinking the public key with a Merkle tree (rather than publishing every one-time public key directly) is the key idea letting these schemes scale, and online/offline signing plus authenticating streamed data are direct applications. The main technical payoff is converting a one-time signature scheme into a many-time one via indexed signatures and the complete (stateful) Merkle signature system, with nonce-based variants removing the need to track state — closing with the TESLA broadcast MAC, which repurposes this one-time-signature machinery for efficiently authenticating broadcast streams.

Outline (TODO — flesh out each)

• Shrinking a Lamport signature using an enhanced TCR
• A general Lamport framework; an explicit containment-free function
• Winternitz one-time signatures; a domination-free function
• HORS — short Lamport-style signatures
• Shrinking the public key using a Merkle tree
• Applications: online/offline signatures; authenticating streamed data
• From one-time to many-time signatures — indexed signatures
• The complete Merkle stateless signature system; nonce-based variants
• Fun application: the TESLA broadcast MAC