文章基本信息

标题：On Oblivious Amplification of Coin-Tossing Protocols
本地全文：下载
作者：Nir Bitansky ; Nathan Geier
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：151
页码：1-13
DOI：10.4230/LIPIcs.ITCS.2020.30
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Coin Tossing; Amplification; Lower Bound; Santha Vazirani