Paper 2020/564

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

Mahmoud Yehia, Riham AlTawy, and T. Aaron Gulliver


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.

Available format(s)
Publication info
Published elsewhere. Africacrypt 2020
Digital signaturesHash-based signature schemesPost- Quantum CryptographyAdaptive chosen message attacks.
Contact author(s)
mahmoudyehia @ uvic ca
2020-07-10: revised
2020-05-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mahmoud Yehia and Riham AlTawy and T.  Aaron Gulliver},
      title = {Hash-based Signatures Revisited: A Dynamic FORS with Adaptive Chosen Message Security},
      howpublished = {Cryptology ePrint Archive, Paper 2020/564},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.