**On Oblivious Amplification of Coin-Tossing Protocols**

*Nir Bitansky and 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.

**Category / Keywords: **cryptographic protocols / Coin Tossing, Amplification, Lower Bound, Santha Vazirani

**Original Publication**** (in the same form): **ITCS 2020
**DOI: **10.4230/LIPIcs.ITCS.2020.30

**Date: **received 13 Nov 2019

**Contact author: **nathangeier at mail tau ac il

**Available format(s): **PDF | BibTeX Citation

**Version: **20191117:181246 (All versions of this report)

**Short URL: **ia.cr/2019/1313

[ Cryptology ePrint archive ]