Geodesic
Security analysis of the W-OTS$^+$ signature scheme: Updating security bounds
Matematičeskie voprosy kriptografii, Tome 12 (2021) no. 2, pp. 129-145 
M. A. Kudinov; E. O. Kiktenko; A. K. Fedorov. Security analysis of the W-OTS$^+$ signature scheme: Updating security bounds. Matematičeskie voprosy kriptografii, Tome 12 (2021) no. 2, pp. 129-145. http://geodesic.mathdoc.fr/item/MVK_2021_12_2_a8/
@article{MVK_2021_12_2_a8,
     author = {M. A. Kudinov and E. O. Kiktenko and A. K. Fedorov},
     title = {Security analysis of the {W-OTS}$^+$ signature scheme: {Updating} security bounds},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {129--145},
     year = {2021},
     volume = {12},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2021_12_2_a8/}
}
TY  - JOUR
AU  - M. A. Kudinov
AU  - E. O. Kiktenko
AU  - A. K. Fedorov
TI  - Security analysis of the W-OTS$^+$ signature scheme: Updating security bounds
JO  - Matematičeskie voprosy kriptografii
PY  - 2021
SP  - 129
EP  - 145
VL  - 12
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2021_12_2_a8/
LA  - en
ID  - MVK_2021_12_2_a8
ER  - 
%0 Journal Article
%A M. A. Kudinov
%A E. O. Kiktenko
%A A. K. Fedorov
%T Security analysis of the W-OTS$^+$ signature scheme: Updating security bounds
%J Matematičeskie voprosy kriptografii
%D 2021
%P 129-145
%V 12
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2021_12_2_a8/
%G en
%F MVK_2021_12_2_a8

Voir la notice de l'article provenant de la source Math-Net.Ru

We discuss in detail a flaw in the original security proof of the W-OTS${^+}$ variant of the Winternitz one-time signature scheme, which is an important component for various stateless and stateful many-time hash-based digital signature schemes. We update the security proof for the W-OTS${^+}$ scheme and derive the corresponding security level. Our result is of importance for the security analysis of hash-based digital signature schemes.

[1] Shor P.W., “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM J. Comput., 26 (1997), 1484–1509

[2] Bernstein D.J., Lange T., “Post-quantum cryptography”, Nature, 549 (2017), 188-194

[3] Dods C., Smart N. P., Stam M., “Hash based digital signature schemes”, Cryptography and Coding, Lect. Notes Comput. Sci., 3796, 2005, 96–115

[4] Grover L.K., “A fast quantum mechanical algorithm for database search”, Proc. 28th Annu. ACM Symp. Theory of Computing, 1996, 212–219

[5] Cooper D.A., Apon D.C., Dang Q.H., Davidson M.S., Dworkin M.J., Miller C.A., Recommendation for stateful hash-based signature schemes, 2019 | DOI

[6] McGrew D., Curcio M., Fluhrer S., Hash-based signatures, 2018 https://datatracker.ietf.org/doc/draft-mcgrew-hash-sigs/

[7] Hülsing A., Butin D., Gazdag S., Rijneveld J., Mohaisen A., XMSS: eXtended Merkle Signature Scheme, 2018 https://datatracker.ietf.org/doc/rfc8391/

[8] Hülsing A., “W-OTS+ – shorter signatures for hash-based signature schemes”, AFRICACRYPT 2013, Lect. Notes Comput. Sci., 7918, 2013, 173–188

[9] Bernstein D.J., Hopwood D., Hülsing A., Lange T., Niederhagen R., Papachristodoulou L., Schneider M., Schwabe P., Wilcox-O'Hearn Z., “SPHINCS: practical stateless hash-based signatures”, EUROCRYPT 2015, Lect. Notes Comput. Sci., 9056, 368–397

[10] Hülsing A., Rijneveld J., Song F., “Mitigating multi-target attacks in hash-based signatures”, PKC 2016, Lect. Notes Comput. Sci., 9615, 2016, 387–416

[11] Bernstein D.J., C., Eichlseder M. et al., SPHINCS$^{+}$ Submission to the NIST post-quantum project, 2017 https://sphincs.org/resources.html

[12] Aumasson J.-P., Endignoux G., Gravity-SPHINCS, 2017 https://github.com/gravity-postquantum/gravity-sphincs

[13] Bernstein D.J., Hülsing A., Kölbl, Niederhagen R., Rijneveld J., “The SPHINCS$^{+}$ signature framework”, Proc. 2019 ACM SIGSAC Conf. Computer and Commun. Security, 2019, 2129–2146

[14] Bernstein D.J., Hülsing A., Decisional second-preimage resistance: when does SPR imply PRE?, ASIACRYPT 2019, Lect. Notes Comput. Sci., 11923, 2019, 33–62

[15] Merkle R. C., “A digital signature based on a conventional encryption function”, CRYPTO'87, Lect. Notes Comput. Sci., 293, 1988, 369–378

[16] Even S., Goldreich O., Micali S., “On-line/off-line digital signatures”, CRYPTO'89, Lect. Notes Comput. Sci., 435, 1990, 263–275

[17] Lamport L., Constructing digital signatures from a one way function, Tech. Rep. CSL-98 SRI Internat., 1979

[18] Buchmann J., Dahmen E., Ereth S., Hülsing A., Rückert M., “On the security of the Winternitz one-time signature scheme”, AFRICACRYPT 2011, Lect. Notes Comput. Sci., 6737, 2011, 363–378

[19] Peikert C.J., Official comments - SPHINCS$^{+}$, 2018 https://csrc.nist.gov/Projects/post-quantum-cryptography/Round-1-Submissions