### On the Impossibility of Cryptography with Tamperable Randomness

Per Austrin, Kai-Min Chung, Mohammad Mahmoody, Rafael Pass, and Karn Seth

##### Abstract

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 \emph{efficiently} tamper with each bit of the honest parties' random tape with probability p, but have to do so in an online'' fashion. Our main result is a strong negative result: We show that 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. We also show that this result cannot be extended to primitives such as signature schemes and identification protocols: assuming the existence of one-way functions, such primitives can be made resilient to (\nicefrac{1}{\poly(n)})-tampering attacks where $n$ is the security~parameter.

Available format(s)
Publication info
Published elsewhere. Unknown status
Keywords
TamperingRandomnessEncryption.
Contact author(s)
austrin @ kth se
chung @ cs cornell edu
mahmoody @ gmail com
rafael @ cs cornell edu
karn @ cs cornell edu
History
2018-10-16: last of 5 revisions
See all versions
Short URL
https://ia.cr/2013/194

CC BY

BibTeX

@misc{cryptoeprint:2013/194,
author = {Per Austrin and Kai-Min Chung and Mohammad Mahmoody and Rafael Pass and Karn Seth},
title = {On the Impossibility of Cryptography with Tamperable Randomness},
howpublished = {Cryptology ePrint Archive, Paper 2013/194},
year = {2013},
note = {\url{https://eprint.iacr.org/2013/194}},
url = {https://eprint.iacr.org/2013/194}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.