Paper 2023/1754

That’s not my Signature! Fail-Stop Signatures for a Post-Quantum World

Cecilia Boschini, ETH Zurich
Hila Dahari, Weizmann Institute of Science
Moni Naor, Weizmann Institute of Science
Eyal Ronen, Tel Aviv University

The Snowden's revelations kick-started a community-wide effort to develop cryptographic tools against mass surveillance. In this work, we propose to add another primitive to that toolbox: Fail-Stop Signatures (FSS) [EC'89]. FSS are digital signatures enhanced with a forgery-detection mechanism that can protect a PPT signer from more powerful attackers. Despite the fascinating concept, research in this area stalled after the '90s. However, the ongoing transition to post-quantum cryptography, with its hiccups due to the novelty of underlying assumptions, has become the perfect use case for FSS. This paper aims to reboot research on FSS with practical use in mind: Our framework for FSS includes ``fine-grained'' security definitions (that assume a powerful, but bounded adversary e.g: can break $128$-bit of security, but not $256$-bit). As an application, we show new FSS constructions for the post-quantum setting. We show that FSS are equivalent to standard, provably secure digital signatures that do not require rewinding or programming random oracles, and that this implies lattice-based FSS. Our main construction is an FSS version of SPHINCS, which required building FSS versions of all its building blocks: WOTS, XMSS, and FORS. In the process, we identify and provide generic solutions for two fundamental issues arising when deriving a large number of private keys from a single seed, and when building FSS for Hash-and-Sign-based signatures.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2024
Fail-stop signaturefoundationshash-based signatureSPHINCS+
Contact author(s)
cecilia boschini @ inf ethz ch
hila dahari @ weizmann ac il
moni naor @ weizmann ac il
eyal ronen @ cs tau ac il
2024-06-05: revised
2023-11-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Cecilia Boschini and Hila Dahari and Moni Naor and Eyal Ronen},
      title = {That’s not my Signature! Fail-Stop Signatures for a Post-Quantum World},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1754},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.