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.
The main disadvantage to the MSS is its speed (or rather, lack of it). The cost of initially computing the public key requires creating at least O(2^h) leaf public keys, so the initial computation of the root public key can be very expensive for a significant h. Every OTS public key that will ever be used in the tree must be known at the time of creation.
Merkle presented a way to do this computation quickly as part of his 1979 paper A Certified Digital Signature, later improved by Michael Szydlo in Merkle Tree Traversal in Log Space and Time. Even with a proven best-case time efficiency for computing N sucessive leaves of O(2*log2(N)) = O(2*h) per leaf, time O(2*h*2^h) is required compute the public key.
Create a Merkle tree M for the MSS as usual. Instead of signing messages with the OTS leaves, sign the root of another MSS tree M'. Then, to sign messages, use the OTS on a leaf of M' to sign the message and provide the auth path to the root of M'. Then, append proof that the leaf of M signs the root of M', and provide the auth path on M to the public key root.
This doubles the size of the signature but provides numerous advantages:
- It can be extended indefinitely. Subtrees can sign further subtrees to allow the same public key to be reused as long as the signature size remains acceptable.
- There is no requirement that all subtrees are the same height, or that they all even exist when the primary public key is created. Subtrees can be "signed into" the main tree whenever it is necessary.
- As computational speed continues to improve, larger trees can be created and integrated. This would also allow several subtrees to be computed simultaneously.
- Several signing subtrees can be used at the same time, since there is no requirement that leaves of the MSS be used in sequence.
- Different types of MSS subtrees can be used. This could allow advances in OTS schemes or other new hash-based cryptographic techniques to be integrated into and used by older public keys.