I present a simple algorithm that lets one use an undetermined number of OTS's for the same public key at the expense of a larger signature. My scheme would allow at least 4.2 billion one-time signatures to be used with a single public key using today's technology.
The Merkle signature scheme (MSS) is a well-known way to use a one-time signature (OTS) like the Lamport-Diffie OTS to create a public key cryptosystem. Briefly, one creates a hash tree of height h
from 2^h
OTS public keys leading to a root public key. To sign a message, one then simply creates a signature from one of the leaf OTS's as usual and provides evidence of its presence in the tree by giving the sequence of hashes that lead from it to the root public key of the MSS.