How to construct optimal one-time signatures

One-time signature (OTS) offer a viable alternative to public key-based digital signatures. OTS security is typically based only on the strength of the underlying one-way function and does not depend on the conjectured difficulty of some mathematical problem. Although many OTS methods have been proposed in the past, no solid foundation exists for judging their efficiency or optimality. This paper develops a methodology for evaluating OTS methods and presents optimal OTS techniques for a single OTS or a tree with many OTS's. These techniques can be used in a seesaw mode to obtain the desired tradeoff between various parameters such as the cost of signature generation and its subsequent verification. (C) 2003 Elsevier B.V. All rights reserved.