# On the Efficiency of One-time Digital Signatures

## Daniel Bleichenbacher and Ueli Maurer

```
```Digital signature schemes based on a general one-way function without
trapdoor offer two potential advantages over digital signature schemes
based on trapdoor one-way functions such as the RSA system: higher
efficiency and much more freedom in choosing a cryptographic function
to base the security on. Such a scheme is characterized by a directed
acyclic computation graph and an antichain in a certain partially
ordered set defined by the graph. Several results on the achievable
efficiency of such schemes are proved, where the efficiency of a scheme
is defined as the ratio of the size of messages that can be signed and
the number of one-way function evaluations needed for setting up the
system. For instance, the maximal achievable efficiency for trees is
shown to be equal to a constant $\gamma\approx 0.4161426$ and a family
of general graphs with substantially greater efficiency $0.476$ is
demonstrated. This construction appears to be close to optimal.

Key words: Cryptography, Digital signature, One-way function,
Directed acyclic graph, Partially ordered set.