On the security of the WOTS-PRF signature scheme

Philip Lafrance; Alfred Menezes

doi:10.3934/amc.2019012

Article Contents

2019, Volume 13, Issue 1: 185-193. Doi: 10.3934/amc.2019012

This issue Previous Article Double circulant self-dual and LCD codes over Galois rings Next Article Some two-weight and three-weight linear codes

On the security of the WOTS-PRF signature scheme

Philip Lafrance^1, and
Alfred Menezes^2,

1.
ISARA Corporation, Waterloo, Canada
2.
Department of Combinatorics & Optimization, University of Waterloo, Canada

Received: July 1, 2018

Published online: December 15, 2018

Abstract / Introduction Full Text(HTML) Figure(2) Related Papers Cited by

Abstract

We identify a flaw in the security proof and a flaw in the concrete security analysis of the WOTS-PRF variant of the Winternitz one-time signature scheme, and discuss the implications to its concrete security.

Keywords:

Mathematics Subject Classification: Primary: 94A60.

Citation:

Full Text(HTML)

Figure 1. The incomplete $\alpha$'th Winternitz hash chain in ${\mathcal{A}}_{{\rm KOW}}$'s experiment

Download: Full-size image PowerPoint slide

Figure 2. The tree of $w$-keychains to $pk_{\alpha}$

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	M. Bellare, New proofs for NMAC and HMAC: Security without collision resistance, in: Advances in Cryptology - CRYPTO 2006, LNCS, 4117 (2006), 602-619. doi: 10.1007/11818175_36.
[2]	D. Bernstein and T. Lange, Non-uniform cracks in the concrete: The power of free computation, in: Advances in Cryptology - ASIACRYPT 2013, LNCS, 8270 (2013), 321-340. doi: 10.1007/978-3-642-42045-0_17.
[3]	J. Buchmann, E. Dahmen, S. Ereth, A. Hülsing and M. Rückert, On the security of the Winternitz one-time signature scheme, in: Progress in Cryptology - AFRICACRYPT 2011, LNCS, 6737 (2011), 363-378. doi: 10.1007/978-3-642-21969-6_23.
[4]	J. Buchmann, E. Dahmen, S. Ereth, A. Hülsing and M. Rückert, On the security of the Winternitz one-time signature scheme, International Journal of Applied Cryptography, 3 (2013), 84-96. doi: 10.1504/IJACT.2013.053435.
[5]	J. Buchmann, E. Dahmen and A. H¨ulsing, XMSS - a practical forward secure signature scheme based on minimal security assumptions, in: Post-Quantum Cryptography - PQCrypto 2011, LNCS, 7071 (2011), 117-129. doi: 10.1007/978-3-642-25405-5_8.
[6]	C. Dods, N. Smart and M. Stam, Hash based digital signature schemes, in: Cryptography and Coding, LNCS, 3796 (2005), 96-115. doi: 10.1007/11586821_8.
[7]	E. Eaton, Leighton-Micali hash-based signatures in the quantum random-oracle model, in: Selected Areas in Cryptography - SAC 2017, LNCS 10719 (2018), 263-280.
[8]	S. Even, O. Goldreich and S. Micali, On-line/off-line digital signatures, Journal of Cryptology, 9 (1996), 35-67. doi: 10.1007/BF02254791.
[9]	O. Goldreich, S. Goldwasser and S. Micali, How to construct random functions, Journal of the ACM, 33 (1986), 792-807. doi: 10.1145/6490.6503.
[10]	J. Håstad, R. Impagliazzo, L. Levin and M. Luby, A pseudorandom generator from any oneway function, SIAM Journal on Computing, 28 (1999), 1364-1396. doi: 10.1137/S0097539793244708.
[11]	A. Hülsing, Practical Forward Secure Signatures Using Minimal Security Assumptions, Ph. D. thesis, Technical University of Darmstadt, 2013.
[12]	A. Hülsing, W-OTS⁺ - Shorter signatures for hash-based signature schemes, in: Progress in Cryptology - AFRICACRYPT 2013, LNCS 7918 (2013), 173-188.
[13]	A. Hülsing, C. Busold and J. Buchmann, Forward secure signatures on smart cards, in: Selected Areas in Cryptography - SAC 2012, LNCS 7707 (2013), 66-80.
[14]	A. Hülsing, D. Butin, S. Gazdag, J. Rijneveld and A. Mohaisen, XMSS: eXtended Merkle Signature Scheme, RFC 8391, May 31, 2018; available at https://datatracker.ietf.org/doc/rfc8391/.
[15]	A. Hülsing, L. Rausch and J. Buchmann, Optimal parameters for XMSS^MT, in: Availability, Reliability, and Security in Information Systems and HCI - CD-ARES 2013, LNCS 8128 (2013), 194-208.
[16]	A. Hülsing, J. Rijneveld and F. Song, Mitigating multi-target attacks in hash-based signatures, in: Public-Key Cryptography - PKC 2016, LNCS 9614 (2016), 387-416. doi: 10.1007/978-3-662-49384-7_15.
[17]	J. Katz, Analysis of a proposed hash-based signature scheme, in: Security Standardisation Research - SSR 2016, LNCS 10074 (2016), 261-273.
[18]	N. Koblitz and A. Menezes, Another look at HMAC, Journal of Mathematical Cryptology, 7 (2013), 225-251. doi: 10.1515/jmc-2013-5004.
[19]	N. Koblitz and A. Menezes, Another look at non-uniformity, Groups Complexity Cryptology, 5 (2013), 117-139. doi: 10.1515/gcc-2013-0008.
[20]	L. Lamport, Constructing digital signatures from a one way function, Technical Report CSL-98, SRI International, 1979.
[21]	D. McGrew, M. Curcio and S. Fluhrer, Hash-based signatures, Internet Draft, April 5, 2018; available at https://datatracker.ietf.org/doc/draft-mcgrew-hash-sigs/.
[22]	R. Merkle, A digital signature based on a conventional encryption function, in: Advances in Cryptology - CRYPTO '87, LNCS 293 (1988), 369-378.
[23]	M. Raab and A. Steger, "Balls into bins" - = - a simple and tight analysis, in: Randomization and Approximation Techniques in Computer Science - RANDOM 1998, LNCS 1518 (1998), 159-170. doi: 10.1007/3-540-49543-6_13.