Improving Lamport one-time signature scheme

Abstract

One-time signature scheme, a kind of digital signature schemes, is used to sign at most one message; otherwise the signature can be forged. One of the advantages is that the one-time signature generation and verification are very efficient and it is useful for chip cards, where low computation complexity is required. Lamport first invented a one-time digital signature scheme based on one-way functions. However, the Lamport one-time scheme requires a large amount of space for storage of authentic information if a large number of messages are signed. In this paper, we improve the Lamport one-time signature on the amount of storage space for public keys and signed message saving storage space and propose an efficient scheme to sign a long message. Thus, we make the Lamport one-time signature useful in practice. (c) 2004 Elsevier Inc. All rights reserved.