# Information Security and Cryptography Research Group

## Optimal Tree-based One-time Digital Signature Schemes

### Daniel Bleichenbacher and Ueli Maurer

Proc. 13th Symposium on Theoretical Aspects of Computer Science — STACS '96, Lecture Notes in Computer Science, Springer-Verlag, vol. 1046, pp. 363–374, Feb 1996.

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.

## BibTeX Citation

@inproceedings{BleMau96a,
author       = {Daniel Bleichenbacher and Ueli Maurer},
title        = {Optimal Tree-based One-time Digital Signature Schemes},
editor       = {C. Puech and R. Reischuk},
booktitle    = {Proc.~13th Symposium on Theoretical Aspects of Computer Science --- STACS~'96},
pages        = 363--374,
series       = {Lecture Notes in Computer Science},
volume       = 1046,
year         = 1996,
month        = 2,
publisher    = {Springer-Verlag},
}