Advertisement
Published in:
2014 | OriginalPaper | Chapter
On the Impossibility of Cryptography with Tamperable Randomness
Authors : Per Austrin, Kai-Min Chung, Mohammad Mahmoody, Rafael Pass, Karn Seth
Published in: Advances in Cryptology – CRYPTO 2014
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
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 (1/poly(
n
))-tampering attacks where
n
is the security parameter.