Cryptographic Tamper Evidence

Gene Itkis
Boston University

We propose a new notion of {\em 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 had inconspicuously learned some
---or even {\em 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 {\em 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
{\em all the secrets} at arbitrary times.

We provide tamper-evident schemes for all the variants and prove their
optimality.

We stress that our mechanisms are purely cryptographic: the
tamper-detection algorithm $Div$ is stateless and takes no inputs
except the two signatures (in particular, it keeps no logs), we use no
infrastructure (or other ways to conceal additional secrets), and we
use no hardware properties (except those implied by the standard
cryptographic assumptions, such as random number generators).

Our constructions are based on arbitrary ordinary signature schemes
and do not require random oracles.