On the security of the Winternitz one-time signature scheme

Johannes Buchmann, Erik Dahmen, Sarah Ereth, Andreas Hülsing, Markus Rückert

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

44 Citations (Scopus)

Abstract

We show that the Winternitz one-time signature scheme is existentially unforgeable under adaptive chosen message attacks when instantiated with a family of pseudo random functions. Compared to previous results, which require a collision resistant hash function, our result provides significantly smaller signatures at the same security level. We also consider security in the strong sense and show that the Winternitz one-time signature scheme is strongly unforgeable assuming additional properties of the pseudo random function. In this context we formally define several key-based security notions for function families and investigate their relation to pseudorandomness. All our reductions are exact and in the standard model and can directly be used to estimate the output length of the hash function required to meet a certain security level.

Original languageEnglish
Title of host publicationProgress in Cryptology – AFRICACRYPT 2011
Subtitle of host publication4th International Conference on Cryptology in Africa, Dakar, Senegal, July 5-7, 2011 Proceedings
EditorsA. Nitaj, D. Pointcheval
Place of PublicationBerlin
PublisherSpringer
Pages363-378
Number of pages16
ISBN (Print)9783642219689
DOIs
Publication statusPublished - 2011
Event4th International Conference on the Theory and Application of Cryptographic Techniques in Africa (Africacrypt 2011) - Dakar, Senegal
Duration: 5 Jul 20117 Jul 2011
Conference number: 4

Publication series

NameLecture Notes in Computer Science
Volume6737
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference4th International Conference on the Theory and Application of Cryptographic Techniques in Africa (Africacrypt 2011)
Abbreviated titleAfricacrypt 2011
Country/TerritorySenegal
CityDakar
Period5/07/117/07/11

Keywords

  • Hash-based signatures
  • post-quantum signatures
  • pseudorandom functions
  • security reductions

Fingerprint

Dive into the research topics of 'On the security of the Winternitz one-time signature scheme'. Together they form a unique fingerprint.

Cite this