On the Efficiency of One-time Digital Signatures

. 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 fl ß 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, O..