We propose a new notion of cryptographic tamper evidence. A tamper-evident signature scheme provides an additional procedure Div which detects tampering: given two signatures, Div can determine whether one of them was generated by the forger. Surprisingly, this is possible even after the adversary has inconspicuously learned (exposedootnote We say that a secret is exposed when it becomes known to the adversary. Exposure does not imply that the secrets become publicly known. Moreover, nobody --- except the adversary --- is aware of the exposure taking place.) some --- or even all --- the secrets in the system. 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 controlsall 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. Some of our schemes use a combinatorial construction of a-separating sets, which might be of independent interest.The schemes are optimal: we prove tight lower-bounds. These lower bounds are perhaps the most surprising result of this paper. The lower bounds proofs are information-theoretic, and thus cannot be broken by introducing number-theoretic or algebraic complexity assumptions.Our mechanisms are purely cryptographic: the tamper-detection algorithm Div 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 hardware properties (except those implied by the standard cryptographic assumptions, such as random number generators).All constructions in thispaper are based on arbitrary ordinary signature schemes and do not require random oracles.
展开▼
