Cryptology ePrint Archive: Report 2006/320

CMSS -- An Improved Merkle Signature Scheme

Johannes Buchmann and Luis Carlos Coronado Garcia and Erik Dahmen and Martin Doering and Elena Klintsevich

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.

Category / Keywords: public-key cryptography / Merkle Signatures, One-Time-Signatures, Post-Quantum Signatures, Tree Authentication

Date: received 20 Sep 2006, last revised 20 Sep 2006

Contact author: dahmen at cdc informatik tu-darmstadt de

Available formats: PDF | BibTeX Citation

Version: 20060921:100215 (All versions of this report)

Discussion forum: Show discussion | Start new discussion