Paper 2026/1203

Signatures with Post-Compromise Accountability

Abstract

Cryptographic signatures play an integral part in ensuring authenticity and integrity in digital systems. Their security crucially relies on the secrecy of the signing key, since knowledge of this key enables an adversary to generate valid signatures on any message. Once a signing key is compromised, the standard countermeasure is to revoke the corresponding public key and to invalidate all signatures produced for this key. However, with this approach even legitimate signatures created by the honest signer would retroactively lose their validity. In this work, we initiate the formal study of a new approach - Signatures with Post-Compromise Accountability (SPCA) - which provides security guarantees even after the secret key was compromised. This notion effectively introduces a grace period for the legitimate key owner, during which the validity of honestly generated signatures is preserved despite the adversary’s knowledge of the secret key. We formally define SPCA and its security guarantees, and present two constructions achieving this notion. Our first construction generalizes the signature-in-signature approach of Błaśkiewicz et al. (ESORICS '21), where an inner signature is embedded into the randomness of an outer signature. This construction, however, requires revealing the signing secret key during revalidation. Our second construction overcomes this limitation by enabling revalidation without disclosing the secret key, yielding stronger security guarantees.