On Oblivious Amplification of Coin-Tossing Protocols

Nir Bitansky; Nathan Geier

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 $ρ$ , we aim to obtain a new protocol where the output can be biased by at most $ρ^{⋆} < ρ$ . We rule out the existence of a natural type of amplifiers called oblivious amplifiers for every $ρ^{⋆} < ρ$ . Such amplifiers ignore the way that the underlying $ρ$ -bias protocol works and can only invoke an oracle that provides $ρ$ -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 Tossing Amplification Lower Bound Santha 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},
      url = {https://eprint.iacr.org/2019/1313}
}