Directed Acyclic Graphs, One-way Functions and Digital Signatures

The goals of this paper are to formalize and investigate the general concept of a digital signature scheme based on a general one-way function without trapdoor for signing a predetermined number of messages. It generalizes and unifies previous work of Lamport, Winternitz, Merkle, Even et al. and Vaudenay. The structure of the computation yielding a public key from a secret key corresponds to a directed acyclic graph $$ \mathcal{G} $$. A signature scheme for $$ \mathcal{G} $$ can be defined as an antichain in the poset of minimal verifyable sets of vertices of $$ \mathcal{G} $$ with the naturally defined computability relation as the order relation and where a set is verifyable if and only if the public key can be computed from the set.