That's Not My Signature! Fail-Stop Signatures for a Post-quantum World

In this work we present Fail-Stop Signatures (FSS), which are digital signatures enhanced with a forgery detection mechanism. Such mechanism allows to extract from a forgery a proof that the hardness assumption underlying the signature scheme has been broken, without the need for extensive cryptanalysis. This capability allows for the rapid deprecation of insecure signature schemes and their consequent replacement with more secure alternatives. We argue that a standardization process should prefer signatures that allow for a fail-stop mechanism whenever reasonable, as FSS make large, undiscriminating exploits of an undisclosed vulnerability a high stakes game for an agency. To prove that fail-stop mechanisms are practical we present FSS.SPHINCS, that is, SPHINCS + (now standardized as SLH-DSA) augmented with a fail-stop mechanism. We show that the fail-stop mechanism does not have a big impact on the efficiency of SPHINCS + . Using Lamport's signature as running example, we illustrate how to go from SPHINCS + to FSS.SPHINCS and give an intuition behind our proposed security model.