Tamper-evident digital signatures: Protecting certification Authorities against malware

We introduce the notion of tamper-evidence for digital signature generation in order to defend against attacks aimed at covertly leaking secret information held by corrupted signing nodes. This is achieved by letting observers (which need not be trusted) verify the absence of covert channels by means of techniques we introduce herein. We call our signature schemes tamper-evident since any deviation from the protocol is immediately detectable. We demonstrate our technique for the RSA-PSS (known as RSA's Probabilistic Signature Scheme) and DSA signature schemes and show how the same technique can be applied to the Schnorr and Feige-Fiat-Shamir (FFS) signature schemes. Our technique does not modify the distribution of the generated signature transcripts, and has only a minimal overhead in terms of computation, communication, and storage.