W-OTS+ - shorter signatures for hash-based signature schemes

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

97 Citations (Scopus)


We present W-OTS+, a Winternitz type one-time signature scheme (W-OTS). We prove that W-OTS+ is strongly unforgeable under chosen message attacks in the standard model. Our proof is exact and tight. The first property allows us to compute the security of the scheme for given parameters. The second property allows for shorter signatures than previous proposals without lowering the security. This improvement in signature size directly carries over to all recent hash-based signature schemes. I.e. we can reduce the signature size by more than 50% for XMSS+ at a security level of 80 bits. As the main drawback of hash-based signature schemes is assumed to be the signature size, this is a further step in making hash-based signatures practical.

Original languageEnglish
Title of host publicationProgress in Cryptology–AFRICACRYPT 2013
Subtitle of host publication6th International Conference on Cryptology in Africa, Cairo, Egypt, June 22-24, 2013. Proceedings
EditorsA. Youssef, A. Nitaj, A.E. Hassanien
Place of PublicationBerlin
Number of pages16
ISBN (Electronic)978-3-642-38553-7
ISBN (Print)978-3-642-38552-0
Publication statusPublished - 2013
Externally publishedYes
Event6th International Conference on the Theory and Application of Cryptographic Techniques in Africa (Africacrypt 2013) - Cairo, Egypt
Duration: 22 Jun 201324 Jun 2013
Conference number: 6

Publication series

NameLecture Notes in Computer Science (LNCS)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference6th International Conference on the Theory and Application of Cryptographic Techniques in Africa (Africacrypt 2013)
Abbreviated titleAfricacrypt 2011


  • digital signatures
  • hash functions
  • hash-based signatures
  • one-time signature schemes
  • provable security


Dive into the research topics of 'W-OTS+ - shorter signatures for hash-based signature schemes'. Together they form a unique fingerprint.

Cite this