Figure 1.
The incomplete $\alpha$ 'th Winternitz hash chain in ${\mathcal{A}}_{{\rm KOW}}$ 's experiment
-
Previous Article
Some two-weight and three-weight linear codes
- AMC Home
- This Issue
-
Next Article
Double circulant self-dual and LCD codes over Galois rings
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 |
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.
Mathematics Subject Classification:
Primary: 94A60.
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. 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 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. 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 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. |
| [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] |
Meenakshi Kansal, Ratna Dutta, Sourav Mukhopadhyay. Group signature from lattices preserving forward security in dynamic setting. Advances in Mathematics of Communications, 2020, 14 (4) : 535-553. doi: 10.3934/amc.2020027 |
| [3] |
Xuemei Li, Rafael de la Llave. Convergence of differentiable functions on closed sets and remarks on the proofs of the "Converse Approximation Lemmas''. Discrete and Continuous Dynamical Systems - S, 2010, 3 (4) : 623-641. doi: 10.3934/dcdss.2010.3.623 |
| [4] |
Marcela Mejía, J. Urías. An asymptotically perfect pseudorandom generator. Discrete and Continuous Dynamical Systems, 2001, 7 (1) : 115-126. doi: 10.3934/dcds.2001.7.115 |
| [5] |
Shan Liu, Hui Zhao, Ximin Rong. Time-consistent investment-reinsurance strategy with a defaultable security under ambiguous environment. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1185-1222. doi: 10.3934/jimo.2021015 |
| [6] |
Qi Feng, Man Luo, Zhaoyu Zhang. Deep signature FBSDE algorithm. Numerical Algebra, Control and Optimization, 2022 doi: 10.3934/naco.2022028 |
| [7] |
Małgorzata Wyrwas, Dorota Mozyrska, Ewa Girejko. Subdifferentials of convex functions on time scales. Discrete and Continuous Dynamical Systems, 2011, 29 (2) : 671-691. doi: 10.3934/dcds.2011.29.671 |
| [8] |
Carlos Lizama, Marina Murillo-Arcila. Discrete maximal regularity for volterra equations and nonlocal time-stepping schemes. Discrete and Continuous Dynamical Systems, 2020, 40 (1) : 509-528. doi: 10.3934/dcds.2020020 |
| [9] |
Hélène Hivert. Numerical schemes for kinetic equation with diffusion limit and anomalous time scale. Kinetic and Related Models, 2018, 11 (2) : 409-439. doi: 10.3934/krm.2018019 |
| [10] |
Nicolas Crouseilles, Giacomo Dimarco, Mohammed Lemou. Asymptotic preserving and time diminishing schemes for rarefied gas dynamic. Kinetic and Related Models, 2017, 10 (3) : 643-668. doi: 10.3934/krm.2017026 |
| [11] |
Laurent Gosse. Well-balanced schemes using elementary solutions for linear models of the Boltzmann equation in one space dimension. Kinetic and Related Models, 2012, 5 (2) : 283-323. doi: 10.3934/krm.2012.5.283 |
| [12] |
Adam M. Oberman. Wide stencil finite difference schemes for the elliptic Monge-Ampère equation and functions of the eigenvalues of the Hessian. Discrete and Continuous Dynamical Systems - B, 2008, 10 (1) : 221-238. doi: 10.3934/dcdsb.2008.10.221 |
| [13] |
Françoise Demengel, Thomas Dumas. Extremal functions for an embedding from some anisotropic space, involving the "one Laplacian". Discrete and Continuous Dynamical Systems, 2019, 39 (2) : 1135-1155. doi: 10.3934/dcds.2019048 |
| [14] |
Carlos Lizama, Marina Murillo-Arcila. Maximal regularity for time-stepping schemes arising from convolution quadrature of non-local in time equations. Discrete and Continuous Dynamical Systems, 2022, 42 (8) : 3787-3807. doi: 10.3934/dcds.2022032 |
| [15] |
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 |
| [16] |
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 |
| [17] |
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 and Applied Analysis, 2017, 16 (5) : 1915-1938. doi: 10.3934/cpaa.2017093 |
| [18] |
Daniele Boffi, Lucia Gastaldi, Sebastian Wolf. Higher-order time-stepping schemes for fluid-structure interaction problems. Discrete and Continuous Dynamical Systems - B, 2020, 25 (10) : 3807-3830. doi: 10.3934/dcdsb.2020229 |
| [19] |
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 and Continuous Dynamical Systems, 2012, 32 (12) : 4229-4246. doi: 10.3934/dcds.2012.32.4229 |
| [20] |
Xingjie Helen Li, Fei Lu, Felix X.-F. Ye. ISALT: Inference-based schemes adaptive to large time-stepping for locally Lipschitz ergodic systems. Discrete and Continuous Dynamical Systems - S, 2022, 15 (4) : 747-771. doi: 10.3934/dcdss.2021103 |
2021 Impact Factor: 1.015
Tools
Metrics
Other articles
by authors
[Back to Top]