Cryptographic Tamper Evidence
Abstract
We propose a new notion of cryptographic tamper evidence A tamper-evident signature scheme provides an additional procedure which detects tampering: given two signatures, this can determine whether one of them was generated by the forger. In this case, it might be impossible to tell which signature is generated by the legitimate signer and which by the forger, but at least the fact of the tampering will be made evident. We define several variants of tamper-evidence, differing in their power to detect tampering. In all of these, we assume an equally powerful adversary: she adaptively controls all the inputs to the legitimate signer (i.e., all messages to be signed and their timing), and observes all his outputs; she can also adaptively expose all the secrets at arbitrary times. We provide tamper-evident schemes for all the variants.

Our mechanisms are purely cryptographic: the tamper- detection algorithm is stateless and takes no inputs except the two signatures, it uses no infrastructure (or other ways to conceal additional secrets),and relies on no hard-ware properties (except those implied by the standard cryptographic assumptions, such as random number generators).

Key exposure is a well-known threat for any cryptographic tool. For signatures, exposure of a secret key compromises the corresponding public key After the exposure is detected,
the compromised keys can be revoked. This detection of the exposure has previously been dealt with outside the scope of cryptography. Indeed, it may seem that if an adversary in-conspicuously learns all the secrets within the system, then the cryptographic tools are helpless.

Thus, while it still might not be possible to distinguish the forger-generated signatures from the legitimate ones, our mechanisms can at least make the tampering evident.