# Optimal Tree-based One-time Digital Signature Schemes

## Daniel Bleichenbacher and Ueli Maurer

```
```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\leq 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.

Keywords: Cryptography, digital signature schemes, trees,
partially ordered sets.