International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: CMSS -- An Improved Merkle Signature Scheme

Johannes Buchmann
Luis Carlos Coronado Garcia
Erik Dahmen
Martin Doering
Elena Klintsevich
Search ePrint
Search Google
Abstract: The Merkle signature scheme (MSS) is an interesting alternative for well established signature schemes such as RSA, DSA, and ECDSA. The security of MSS only relies on the existence of cryptographically secure hash functions. MSS has a good chance of being quantum computer resistant. In this paper, we propose CMSS, a variant of MSS, with reduced private key size, key pair generation time, and signature generation time. We demonstrate that CMSS is competitive in practice by presenting a highly efficient implementation within the Java Cryptographic Service Provider FlexiProvider. We present extensive experimental results and show that our implementation can for example be used to sign messages in Microsoft Outlook.
  title={CMSS -- An Improved Merkle Signature Scheme},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Merkle Signatures, One-Time-Signatures, Post-Quantum Signatures, Tree Authentication},
  note={ 13411 received 20 Sep 2006, last revised 20 Sep 2006},
  author={Johannes Buchmann and Luis Carlos Coronado Garcia and Erik Dahmen and Martin Doering and Elena Klintsevich},