Kai-Min Chung
Cornell University

On the (Im)Possibility of Tamper-Resilient Cryptography: Using
Fourier Analysis in Computer Viruses

We study the resilience of cryptographic primitives in the presence of
efficient tampering of the secret random bits of the parties. We
consider, so-called, \emph{$p$-tampering attackers} that may tamper
with each bit of the random tape with probability $p$ while they have
to decide about the value of tampered bits in an \emph{online} way. We
present positive and negative results:

- Any CPA secure encryption scheme, bit commitment scheme, or
efficient-prover zero-knowledge protocol can be ``broken'' with
advantage $\Omega(p)$ by a $p$-tampering attacker. The core of this
result is a new Fourier analytic technique for biasing the output of
bounded value functions, which may be of independent interest (and
provides an alternative, and in our eyes simpler, proof of the classic
Santha-Vazirani theorem).

- Assuming the existence of  one-way  functions,  cryptographic
primitives with a ``threshold~0''-falsifiable security game (\eg
signatures, identification protocols, witness hiding protocols, etc)
can be made resilient to $p$-tampering attacks for arbitrary large $p
= 1/\poly(n)$ where $n$ is the security parameter.

(Joint work with Per Austrin, Mohammad Mahmoody, Rafael Pass, and Karn Seth)