Directed Acyclic Graphs, One-way Functions and Digital Signatures

Daniel Bleichenbacher and Ueli Maurer

Advances in Cryptology — CRYPTO '94, Lecture Notes in Computer Science, Springer-Verlag, vol. 963, pp. 75–82, Aug 1994.

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 $G$ . A signature scheme for $G$ can be defined as an antichain in the poset of minimal verifyable sets of vertices of $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. Several types of graphs are analyzed, results on the number of signatures of these schemes are presented (with and without restriction on the size of signatures), and several open research problems are proposed. In particular, a tree is shown which allows to sign $0.4162$ bits per one-way function evaluation and it is proved that this is also an upper bound for all trees. In contrast a general graph is exhibited which allows to sign 0.4327 bits per one-way function evaluation.

BibTeX Citation

@inproceedings{BleMau94,
    author       = {Daniel Bleichenbacher and Ueli Maurer},
    title        = {Directed Acyclic Graphs, One-way Functions and Digital Signatures},
    editor       = {Yvo Desmedt},
    booktitle    = {Advances in Cryptology --- CRYPTO~'94},
    pages        = {75--82},
    series       = {Lecture Notes in Computer Science},
    volume       = {963},
    year         = {1994},
    month        = {8},
    publisher    = {Springer-Verlag},
}