On the security and the efficiency of the Merkle signature scheme

Carlos Coronado

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 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.

Metadata

Available format(s): PDF PS
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: Merkle Signature Scheme Forward Security Provable Security Lamport-Diffie one-time Signature Scheme.
Contact author(s): coronado @ cdc informatik tu-darmstadt de
History: 2005-06-23: received
Short URL: https://ia.cr/2005/192
License: CC BY

BibTeX

@misc{cryptoeprint:2005/192,
      author = {Carlos Coronado},
      title = {On the security and the efficiency of the Merkle signature scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2005/192},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/192}},
      url = {https://eprint.iacr.org/2005/192}
}