Paper 2011/191

On the Security of the Winternitz One-Time Signature Scheme

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

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.

Note: Eprint report 2017/938 reports a flaw in the security reduction of the proposed construction as well as an issue with the estimation of the exact security which we can confirm. As stated in the report, this flaw does not concern any other variants of WOTS. As we do not see any straight forward way to fix this we suggest to not use the scheme proposed in this work anymore but to use WOTS+.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Full version. An extended abstract of this paper appears in Proceedings of Africacrypt 2011
Keywords
Hash-based signaturespost-quantum signaturespseudorandom functionssecurity reductions.
Contact author(s)
andreas @ huelsing net
History
2017-09-28: last of 2 revisions
2011-04-16: received
See all versions
Short URL
https://ia.cr/2011/191
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/191,
      author = {Johannes Buchmann and Erik Dahmen and Sarah Ereth and Andreas Hülsing and Markus Rückert},
      title = {On the Security of the Winternitz One-Time Signature Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2011/191},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/191}},
      url = {https://eprint.iacr.org/2011/191}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.