Paper 2019/1313
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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. ITCS 2020
- DOI
- 10.4230/LIPIcs.ITCS.2020.30
- Keywords
- Coin TossingAmplificationLower BoundSantha Vazirani
- Contact author(s)
- nathangeier @ mail tau ac il
- History
- 2019-11-17: received
- Short URL
- https://ia.cr/2019/1313
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/1313,
author = {Nir Bitansky and Nathan Geier},
title = {On Oblivious Amplification of Coin-Tossing Protocols},
howpublished = {Cryptology ePrint Archive, Paper 2019/1313},
year = {2019},
doi = {10.4230/LIPIcs.ITCS.2020.30},
note = {\url{https://eprint.iacr.org/2019/1313}},
url = {https://eprint.iacr.org/2019/1313}
}
