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

9:30 am on Wednesday, November 14, 2012
11:20 pm on Wednesday, November 14, 2012
We initiate a study of the security of cryptographic primitives in the presence of efficient tampering attacks to the randomness of honest parties. More precisely, we consider p-tampering attackers that may tamper with each bit of the honest parties' random tape with probability p, but have to do so in an "online" fashion. We present both positive and negative results: * Any secure encryption scheme, bit commitment scheme, or zero- knowledge protocol can be “broken” with probability 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 such as signatures, identification protocols can be made resilient to p-tampering attacks for any p = 1/n^{\alpha}, where \alpha > 0 and n is the security parameter. Joint work with Per Austrin, Kai-Min Chung, Rafael Pass, and Karn Seth