SPEAKER: Kai-Min Chung Cornell University TITLE: On the (Im)Possibility of Tamper-Resilient Cryptography: Using Fourier Analysis in Computer Viruses ABSTRACT: 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)