February 2019, 13(1): 185-193. doi: 10.3934/amc.2019012

On the security of the WOTS-PRF signature scheme

1. 

ISARA Corporation, Waterloo, Canada

2. 

Department of Combinatorics & Optimization, University of Waterloo, Canada

Received  July 2018 Published  December 2018

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.

Citation: Philip Lafrance, Alfred Menezes. On the security of the WOTS-PRF signature scheme. Advances in Mathematics of Communications, 2019, 13 (1) : 185-193. doi: 10.3934/amc.2019012
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. BuchmannE. DahmenS. ErethA. 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. EvenO. Goldreich and S. Micali, On-line/off-line digital signatures, Journal of Cryptology, 9 (1996), 35-67. doi: 10.1007/BF02254791.

[9]

O. GoldreichS. 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åstadR. ImpagliazzoL. 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 XMSSMT, 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.

show all references

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. BuchmannE. DahmenS. ErethA. 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. EvenO. Goldreich and S. Micali, On-line/off-line digital signatures, Journal of Cryptology, 9 (1996), 35-67. doi: 10.1007/BF02254791.

[9]

O. GoldreichS. 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åstadR. ImpagliazzoL. 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 XMSSMT, 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.

Figure 1.  The incomplete $\alpha$'th Winternitz hash chain in ${\mathcal{A}}_{{\rm KOW}}$'s experiment
Figure 2.  The tree of $w$-keychains to $pk_{\alpha}$
[1]

Gregory M. Zaverucha, Douglas R. Stinson. Short one-time signatures. Advances in Mathematics of Communications, 2011, 5 (3) : 473-488. doi: 10.3934/amc.2011.5.473

[2]

Xuemei Li, Rafael de la Llave. Convergence of differentiable functions on closed sets and remarks on the proofs of the "Converse Approximation Lemmas''. Discrete & Continuous Dynamical Systems - S, 2010, 3 (4) : 623-641. doi: 10.3934/dcdss.2010.3.623

[3]

Marcela Mejía, J. Urías. An asymptotically perfect pseudorandom generator. Discrete & Continuous Dynamical Systems - A, 2001, 7 (1) : 115-126. doi: 10.3934/dcds.2001.7.115

[4]

Małgorzata Wyrwas, Dorota Mozyrska, Ewa Girejko. Subdifferentials of convex functions on time scales. Discrete & Continuous Dynamical Systems - A, 2011, 29 (2) : 671-691. doi: 10.3934/dcds.2011.29.671

[5]

Hélène Hivert. Numerical schemes for kinetic equation with diffusion limit and anomalous time scale. Kinetic & Related Models, 2018, 11 (2) : 409-439. doi: 10.3934/krm.2018019

[6]

Nicolas Crouseilles, Giacomo Dimarco, Mohammed Lemou. Asymptotic preserving and time diminishing schemes for rarefied gas dynamic. Kinetic & Related Models, 2017, 10 (3) : 643-668. doi: 10.3934/krm.2017026

[7]

Adam M. Oberman. Wide stencil finite difference schemes for the elliptic Monge-Ampère equation and functions of the eigenvalues of the Hessian. Discrete & Continuous Dynamical Systems - B, 2008, 10 (1) : 221-238. doi: 10.3934/dcdsb.2008.10.221

[8]

Laurent Gosse. Well-balanced schemes using elementary solutions for linear models of the Boltzmann equation in one space dimension. Kinetic & Related Models, 2012, 5 (2) : 283-323. doi: 10.3934/krm.2012.5.283

[9]

Neal Koblitz, Alfred Menezes. Another look at security definitions. Advances in Mathematics of Communications, 2013, 7 (1) : 1-38. doi: 10.3934/amc.2013.7.1

[10]

Isabelle Déchène. On the security of generalized Jacobian cryptosystems. Advances in Mathematics of Communications, 2007, 1 (4) : 413-426. doi: 10.3934/amc.2007.1.413

[11]

Françoise Demengel, Thomas Dumas. Extremal functions for an embedding from some anisotropic space, involving the "one Laplacian". Discrete & Continuous Dynamical Systems - A, 2019, 39 (2) : 1135-1155. doi: 10.3934/dcds.2019048

[12]

Takeshi Fukao, Shuji Yoshikawa, Saori Wada. Structure-preserving finite difference schemes for the Cahn-Hilliard equation with dynamic boundary conditions in the one-dimensional case. Communications on Pure & Applied Analysis, 2017, 16 (5) : 1915-1938. doi: 10.3934/cpaa.2017093

[13]

Francisco Guillén-González, Mouhamadou Samsidy Goudiaby. Stability and convergence at infinite time of several fully discrete schemes for a Ginzburg-Landau model for nematic liquid crystal flows. Discrete & Continuous Dynamical Systems - A, 2012, 32 (12) : 4229-4246. doi: 10.3934/dcds.2012.32.4229

[14]

Robert Glassey, Stephen Pankavich, Jack Schaeffer. On long-time behavior of monocharged and neutral plasma in one and one-half dimensions. Kinetic & Related Models, 2009, 2 (3) : 465-488. doi: 10.3934/krm.2009.2.465

[15]

Peter E. Kloeden, Björn Schmalfuss. Lyapunov functions and attractors under variable time-step discretization. Discrete & Continuous Dynamical Systems - A, 1996, 2 (2) : 163-172. doi: 10.3934/dcds.1996.2.163

[16]

Jan L. Cieśliński. Some implications of a new approach to exponential functions on time scales. Conference Publications, 2011, 2011 (Special) : 302-311. doi: 10.3934/proc.2011.2011.302

[17]

Wenxian Shen, Xiaoxia Xie. Spectraltheory for nonlocal dispersal operators with time periodic indefinite weight functions and applications. Discrete & Continuous Dynamical Systems - B, 2017, 22 (3) : 1023-1047. doi: 10.3934/dcdsb.2017051

[18]

Nataliia V. Gorban, Olha V. Khomenko, Liliia S. Paliichuk, Alla M. Tkachuk. Long-time behavior of state functions for climate energy balance model. Discrete & Continuous Dynamical Systems - B, 2017, 22 (5) : 1887-1897. doi: 10.3934/dcdsb.2017112

[19]

Yang Lu, Quanling Zhang, Jiguo Li. An improved certificateless strong key-insulated signature scheme in the standard model. Advances in Mathematics of Communications, 2015, 9 (3) : 353-373. doi: 10.3934/amc.2015.9.353

[20]

Alina Ostafe, Igor E. Shparlinski, Arne Winterhof. On the generalized joint linear complexity profile of a class of nonlinear pseudorandom multisequences. Advances in Mathematics of Communications, 2010, 4 (3) : 369-379. doi: 10.3934/amc.2010.4.369

2017 Impact Factor: 0.564

Article outline

Figures and Tables

[Back to Top]