On the Complexity of Fair Coin Flipping
On the Complexity of Fair Coin Flipping
复制标题
论公平抛硬币的复杂性
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Eran Omri
中科院分区：
文献类型：
--
作者：
Iftach Haitner;Nikolaos Makriyannis;Eran Omri
一个两方硬币翻转协议是（vareps）-公平的，如果没有有效的对手可以使诚实的一方的输出（即使另一方放弃，也总是输出一位）偏向超过（vareps）。Cleve [STOC '86]表明r轮o（1 / r）-公平硬币翻转协议不存在。Awerbuch等人[Mandarpt '85]构建了一个（varTheta（1/sqrt{r}））-公平的硬币翻转协议，假设存在单向函数。Moran等人[Journal of Cryptology '16]构建了一个r轮硬币翻转协议，该协议是（varTheta（1/r））公平的（因此匹配上述Cleve的下限[STOC '86]），假设存在不经意的转移。
A two-party coin-flipping protocol is (varepsilon )-fair if no efficient adversary can bias the output of the honest party (who always outputs a bit, even if the other party aborts) by more than (varepsilon ). Cleve [STOC ’86] showed that r-round o(1 / r)-fair coin-flipping protocols do not exist. Awerbuch et al. [Manuscript ’85] constructed a (varTheta (1/sqrt{r}))-fair coin-flipping protocol, assuming the existence of one-way functions. Moran et al. [Journal of Cryptology ’16] constructed an r-round coin-flipping protocol that is (varTheta (1/r))-fair (thus matching the aforementioned lower bound of Cleve [STOC ’86]), assuming the existence of oblivious transfer.