On oblivious amplification of coin-tossing protocols

Nir Bitansky, Nathan Geier

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publication11th Innovations in Theoretical Computer Science Conference, ITCS 2020
EditorsThomas Vidick
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771344
DOIs
StatePublished - Jan 2020
Event11th Innovations in Theoretical Computer Science Conference, ITCS 2020 - Seattle, United States
Duration: Jan 12 2020Jan 14 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume151
ISSN (Print)1868-8969

Conference

Conference11th Innovations in Theoretical Computer Science Conference, ITCS 2020
Country/TerritoryUnited States
CitySeattle
Period1/12/201/14/20

Keywords

  • Amplification
  • Coin tossing
  • Lower bound
  • Santha vazirani

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'On oblivious amplification of coin-tossing protocols'. Together they form a unique fingerprint.

Cite this