ECCC-Report TR15-106https://eccc.weizmann.ac.il/report/2015/106Comments and Revisions published for TR15-106en-usWed, 21 Mar 2018 17:08:37 +0200
Revision 1
| Coin Flipping of Any Constant Bias Implies One-Way Functions |
Itay Berman,
Iftach Haitner,
Aris Tentes
https://eccc.weizmann.ac.il/report/2015/106#revision1We show that the existence of a coin-flipping protocol safe against any non-trivial constant bias (e.g., $.499$) implies the existence of one-way functions. This improves upon a recent result of Haitner and Omri [FOCS '11], who proved this implication for protocols with bias $\frac{\sqrt2 -1}2 - o(1) \approx .207$. Unlike the result of Haitner and Omri, our result also holds for weak coin-flipping protocols.Wed, 21 Mar 2018 17:08:37 +0200https://eccc.weizmann.ac.il/report/2015/106#revision1
Paper TR15-106
| Coin Flipping of Any Constant Bias Implies One-Way Functions |
Itay Berman,
Iftach Haitner,
Aris Tentes
https://eccc.weizmann.ac.il/report/2015/106We show that the existence of a coin-flipping protocol safe against any non-trivial constant bias (e.g., $.499$) implies the existence of one-way functions. This improves upon a recent result of Haitner and Omri [FOCS '11], who proved this implication for protocols with bias $\frac{\sqrt2 -1}2 - o(1) \approx .207$. Unlike the result of Haitner and Omri, our result also holds for weak coin-flipping protocols.Tue, 23 Jun 2015 21:57:43 +0300https://eccc.weizmann.ac.il/report/2015/106