You are looking at a specific version 20200515:095956 of this paper. See the latest version.

Paper 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 oine 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Africacrypt 2020
Keywords
Digital signaturesHash-based signature schemesPost- Quantum CryptographyAdaptive chosen message attacks.
Contact author(s)
mahmoudyehia @ uvic ca
History
2020-07-10: revised
2020-05-15: received
See all versions
Short URL
https://ia.cr/2020/564
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.