Optimal Tree-based One-time Digital Signature Schemes

. A minimal cutset of a tree directed from the leaves to the root is a minimal set of vertices such that every path from a leaf to the root meets at least one of these vertices. An order relation on the set of minmal cutsets can be defined: U V if and only if every vertex of U is on the path from some vertex in V to the root. Motivated by the design of efficient cryptographic digital signature schemes, the problem of constructing trees with a large number of pairwise incomparable minimal cutsets or, equivalently, with a large antichain in the poset of minimal cutsets, is considered. Such signature schemes can be computationally more efficient than previously proposed signature schemes based on number-theoretic problems, they allow to base the security on a much larger class of conjectured difficult problems (e.g. RSA), but on the other hand the number of messages that can be signed for a given public key is fixed in advance. Keywords. Cryptography, digital signature schemes, trees, p..