Cryptology ePrint Archive: Report 2020/564

Hash-based Signatures Revisited: A Dynamic FORS with Adaptive Chosen Message Security

Mahmoud Yehia and Riham AlTawy and T. Aaron Gulliver

Abstract: FORS is the underlying hash-based few-time signing scheme in SPHINCS+, one of the nine signature schemes which advanced to round 2 of the NIST Post-Quantum Cryptography standardization competition. In this paper, we analyze the security of FORS with respect to adaptive chosen message attacks. We show that in such a setting, the security of FORS decreases significantly with each signed message when compared to its security against non-adaptive chosen message attacks. We propose a chaining mechanism that with slightly more computation, dynamically binds the Obtain Random Subset (ORS) generation with signing, hence, eliminating the offline advantage of adaptive chosen message adversaries. We apply our chaining mechanism to FORS and present DFORS whose security against adaptive chosen message attacks is equal to the non-adaptive security of FORS. In a nutshell, using SPHINCS+-128s parameters, FORS provides 75-bit security and DFORS achieves 150-bit security with respect to adaptive chosen message attacks after signing one message. We note that our analysis does not affect the claimed security of SPHINCS+. Nevertheless, this work provides a better understanding of FORS and other HORS variants and furnishes a solution if new adaptive cryptanalytic techniques on SPHINCS+ emerge.

Category / Keywords: foundations / Digital signatures, Hash-based signature schemes, Post- Quantum Cryptography, Adaptive chosen message attacks.

Original Publication (in the same form): Africacrypt 2020

Date: received 15 May 2020, last revised 10 Jul 2020

Contact author: mahmoudyehia at uvic ca

Available format(s): PDF | BibTeX Citation

Version: 20200710:234204 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]