# Information Security and Cryptography Research Group

## On the Efficiency of One-time Digital Signatures

### Daniel Bleichenbacher and Ueli Maurer

Advances in Cryptology — ASIACRYPT '96, Lecture Notes in Computer Science, Springer-Verlag, vol. 1163, pp. 196–209, Nov 1996.

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.

## BibTeX Citation

@inproceedings{BleMau96b,
author       = {Daniel Bleichenbacher and Ueli Maurer},
title        = {On the Efficiency of One-time Digital Signatures},
editor       = {K. Kim and T. Matsumoto},
booktitle    = {Advances in Cryptology --- ASIACRYPT~'96},
pages        = {196--209},
series       = {Lecture Notes in Computer Science},
volume       = {1163},
year         = {1996},
month        = {11},
publisher    = {Springer-Verlag},
}