Title: On the security of the Winternitz one-time signature scheme

Authors: Johannes Buchmann; Erik Dahmen; Sarah Ereth; Andreas Hülsing; Markus Rückert

Addresses: Technische Universität Darmstadt, Fachbereich Informatik, Hochschulstrasse 10, 64289 Darmstadt, Germany ' Technische Universität Darmstadt, Fachbereich Informatik, Hochschulstrasse 10, 64289 Darmstadt, Germany ' Technische Universität Darmstadt, Fachbereich Informatik, Hochschulstrasse 10, 64289 Darmstadt, Germany ' Technische Universität Darmstadt, Fachbereich Informatik, Hochschulstrasse 10, 64289 Darmstadt, Germany ' Technische Universität Darmstadt, Fachbereich Informatik, Hochschulstrasse 10, 64289 Darmstadt, Germany

Abstract: We show that the Winternitz one-time signature scheme is existentially unforgeable under adaptive chosen message attacks when instantiated with a family of pseudorandom functions. Our result halves the signature size at the same security level, compared to previous results, which require a collision resistant hash function. 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 pseudorandom function family. 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.

Keywords: hash-based signatures; post-quantum signatures; pseudorandom functions; PRFs; security reductions; applied cryptography; one-time signature schemes; Winternitz; EU-CMA; SU-CMA; security notions; adaptive chosen message attacks; security levels.

DOI: 10.1504/IJACT.2013.053435

International Journal of Applied Cryptography, 2013 Vol.3 No.1, pp.84 - 96

Published online: 04 Sep 2014 *