Welcome to the resource topic for 2019/1313
Title:
On Oblivious Amplification of Coin-Tossing Protocols
Authors: Nir Bitansky, Nathan Geier
Abstract:We consider the problem of amplifying two-party coin-tossing protocols: given a protocol where it is possible to bias the common output by at most \rho, we aim to obtain a new protocol where the output can be biased by at most \rho^\star<\rho. We rule out the existence of a natural type of amplifiers called oblivious amplifiers for every \rho^\star<\rho. Such amplifiers ignore the way that the underlying \rho-bias protocol works and can only invoke an oracle that provides \rho-bias bits. We provide two proofs of this impossibility. The first is by a reduction to the impossibility of deterministic randomness extraction from Santha-Vazirani sources. The second is a direct proof that is more general and also rules outs certain types of asymmetric amplification. In addition, it gives yet another proof for the Santha-Vazirani impossibility.
ePrint: https://eprint.iacr.org/2019/1313
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 .