Abstract
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) [49]. FSS are digital signatures enhanced with a forgery-detection mechanism that can protect a computationally bounded signer from more powerful attackers. Despite the fascinating concept, research in this area stalled after the ’90 s. 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.
| Original language | English |
|---|---|
| Title of host publication | Advances in Cryptology – CRYPTO 2024 - 44th Annual International Cryptology Conference, Proceedings |
| Editors | Leonid Reyzin, Douglas Stebila |
| Publisher | Springer Science and Business Media B.V. |
| Pages | 107-140 |
| Number of pages | 34 |
| ISBN (Print) | 9783031683756 |
| DOIs | |
| Publication status | Published Online - 16 Aug 2024 |
| Event | 44th Annual International Cryptology Conference, CRYPTO 2024 - Santa Barbara, United States Duration: 18 Aug 2024 → 22 Aug 2024 |
Publication series
| Series | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 14920 LNCS |
Conference
| Conference | 44th Annual International Cryptology Conference, CRYPTO 2024 |
|---|---|
| Country/Territory | United States |
| City | Santa Barbara |
| Period | 18/8/24 → 22/8/24 |
Funding
We thank Oded Golderich, Yehuda Lindell, and Guy Rothblum for valuable discussions and insights. We also thank Noga Amit, Gal Arnon, and Matan Hamilis for reading a preliminary version of this document. Cecilia Boschini has been supported by the Università della Svizzera Italiana under the SNSF project no. 182452, and by the Postdoc.Mobility grant no. P500PT_203075. Hila Dahari is a fellow of the Ariane de Rothschild Women Doctoral Program and supported in part by grants from the Israel Science Foundation (no. 950/15 and 2686/20) and by the Simons Foundation Collaboration on the Theory of Algorithmic Fairness. Work done in part while a visitor at the FACT Research Center at Reichman University, supported in part by AFOSR Award FA9550-21-1-0046. Moni Naor is supported in part by grants from the Israel Science Foundation (no. 2686/20), by the Simons Foundation Collaboration on the Theory of Algorithmic Fairness and by the Israeli Council for Higher Education (CHE) via the Weizmann Data Science Research Center. Eyal Ronen is partly supported by ISF grant no. 1807/23 and the Len Blavatnik and the Blavatnik Family Foundation. Publisher Copyright: © International Association for Cryptologic Research 2024.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- General Computer Science