Abstract
In 2020, Kudinov, Kiktenko, and Fedorov pointed out a flaw in the tight security proof of the SPHINCS\(^+\) construction. This work gives a new tight security proof for SPHINCS\(^+\). The flaw can be traced back to the security proof for the Winternitz one-time signature scheme (WOTS) used within SPHINCS\(^+\). In this work, we give a stand-alone description of the WOTS variant used in SPHINCS\(^+\) that we call WOTS-TW. We provide a security proof for WOTS-TW and multi-instance WOTS-TW against non-adaptive chosen message attacks where the adversary only learns the public key after it made its signature query. Afterwards, we show that this is sufficient to give a tight security proof for SPHINCS\(^+\). We recover almost the same bound for the security of SPHINCS\(^+\), with only a factor w loss compared to the previously claimed bound, where w is the Winternitz parameter that is commonly set to 16. On a more technical level, we introduce new lower bounds on the quantum query complexity for generic attacks against properties of cryptographic hash functions and analyse the constructions of tweakable hash functions used in SPHINCS\(^+\) with regard to further security properties.
This work was funded by an NWO VIDI grant (Project No. VI.Vidi.193.066). Part of this work was done while M.K. was still affiliated with the Russian Quantum Center, QApp. Date: November 19, 2022.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
To be precise, we are considering multi-target versions of these notions which we omit in the introduction for the sake of clarity.
References
Aumasson, J.-P., et al.: SPHINCS\(^{+}\). Submission to NIST’s post-quantum crypto standardization project, v. 3 (2020). http://sphincs.org/data/sphincs+-round3-specification.pdf
Bernstein, D.J., Hülsing, A.: Decisional second-preimage resistance: when does SPR imply PRE? In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019, Part III. LNCS, vol. 11923, pp. 33–62. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34618-8_2
Bernstein, D.J., Hülsing, A., Kölbl, S., Niederhagen, R., Rijneveld, J., Schwabe, P.: The SPHINCS\(^+\) signature framework. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J. (eds.) ACM CCS 2019, pp. 2129–2146. ACM Press (2019)
Dods, C., Smart, N.P., Stam, M.: Hash based digital signature schemes. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 96–115. Springer, Heidelberg (2005). https://doi.org/10.1007/11586821_8
Hülsing, A., Kudinov, M.: Recovering the tight security proof of SPHINCS\(^{+}\). Cryptology ePrint Archive, Paper 2022/346 (2022). http://eprint.iacr.org/2022/346
Hülsing, A., Rijneveld, J., Song, F.: Mitigating multi-target attacks in hash-based signatures. In: Cheng, C.-M., Chung, K.-M., Persiano, G., Yang, B.-Y. (eds.) PKC 2016, Part I. LNCS, vol. 9614, pp. 387–416. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49384-7_15
Hülsing, A.: W-OTS+ – shorter signatures for hash-based signature schemes. In: Youssef, A., Nitaj, A., Hassanien, A.E. (eds.) AFRICACRYPT 2013. LNCS, vol. 7918, pp. 173–188. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38553-7_10
Kudinov, M., Kiktenko, E., Fedorov, A.: [PQC-forum] Round 3 Official Comment: SPHINCS+ (2020). http://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/official-comments/Sphincs-Plus-round3-official-comment.pdf. Accessed 1 Feb 2022
Kaye, P., Laflamme, R., Mosca, M.: An Introduction to Quantum Computing. Oxford University Press, Oxford (2006)
Xagawa, K., Yamakawa, T.: (Tightly) QCCA-secure key-encapsulation mechanism in the quantum random oracle model. In: Ding, J., Steinwandt, R. (eds.) PQCrypto 2019. LNCS, vol. 11505, pp. 249–268. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-25510-7_14
Zhandry, M.: Secure identity-based encryption in the quantum random oracle model. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 758–775. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_44
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 International Association for Cryptologic Research
About this paper
Cite this paper
Hülsing, A., Kudinov, M. (2022). Recovering the Tight Security Proof of SPHINCS\(^+\). In: Agrawal, S., Lin, D. (eds) Advances in Cryptology – ASIACRYPT 2022. ASIACRYPT 2022. Lecture Notes in Computer Science, vol 13794. Springer, Cham. https://doi.org/10.1007/978-3-031-22972-5_1
Download citation
DOI: https://doi.org/10.1007/978-3-031-22972-5_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-22971-8
Online ISBN: 978-3-031-22972-5
eBook Packages: Computer ScienceComputer Science (R0)