Lamport and Diffie first invented a one-time digital signature scheme based on one-way function. However, the Lamport-Diffie scheme requires a large amount of storage for storage of authentic information if a large number of messages are to be signed. Later, in CRYPTO'87, Merkle improved the Lamport-Diffie scheme by applying an infinite tree structure, namely the authentication tree, to minimize the size of the authentic information. By means of Merkel's scheme, the receiver (or verifier) only needs to remember the public information associated with the root of the tree while the sender (or signer) needs to regenerate historical authentic information with respect to each traveled node in the tree. In this paper, we propose an improvement of Merkle's scheme. By means of the proposed scheme, the sender does not need to regenerate historical authentic in-formation for each traveled node in the tree; only current authentic information for the travelling node is required. Hence, the performance complexity of the proposed scheme is superior to that of Merkle's scheme.