Welcome to the resource topic for 2013/194
Title:
On the Impossibility of Cryptography with Tamperable Randomness
Authors: Per Austrin, Kai-Min Chung, Mohammad Mahmoody, Rafael Pass, 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.
ePrint: https://eprint.iacr.org/2013/194
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .