Cryptology ePrint Archive: Report 2005/192

On the security and the efficiency of the Merkle signature scheme

Carlos Coronado

Abstract: This paper builds on the multi-time signature scheme proposed by Merkle. We prove that the original scheme is existentially unforgeable under adaptive chosen message attack. Moreover, we present an improved version which has three advantages: It is provably forward secure. The number of signatures that can be made with one private key is --- in a practical sense --- unlimited. Finally, the cost for key generation is kept low.

The theoretical exposition is complemented by experimental data about the efficiency of the improved Merkle signature scheme.

Category / Keywords: public-key cryptography / Merkle Signature Scheme, Forward Security, Provable Security, Lamport-Diffie one-time Signature Scheme.

Date: received 23 Jun 2005

Contact author: coronado at cdc informatik tu-darmstadt de

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20050623:094202 (All versions of this report)

Short URL: ia.cr/2005/192