ECCC-Report TR17-168https://eccc.weizmann.ac.il/report/2017/168Comments and Revisions published for TR17-168en-usMon, 23 Apr 2018 19:28:36 +0300
Revision 6
| Tighter Bounds on Multi-Party Coin Flipping, via Augmented Weak Martingales and Dierentially Private Sampling |
Amos Beimel,
Iftach Haitner,
Nikolaos Makriyannis,
Eran Omri
https://eccc.weizmann.ac.il/report/2017/168#revision6In his seminal work, Cleve [STOC 1986] has proved that any r-round coin-flipping protocol can be efficiently biassed by ?(1/r). The above lower bound was met for the two-party case by Moran, Naor, and Segev [Journal of Cryptology '16], and the three-party case (up to a polylog factor) by Haitner and Tsfadia [SICOMP '17], and was approached for n-party protocols when n loglog r, however, the best bias for n-party coin-flipping protocols remains ?(n/?r) achieved by the majority protocol of Awerbuch, Blum, Chor, Goldwasser, and Micali [Manuscript '85].
Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant ? > 0, an r?-party r-round coin-flipping protocol can be efficiently biased by ?(1/?r). As far as we know, this is the rst improvement of Cleve's bound that holds in the standard model, and is only r? (multiplicative) far from the aforementioned upper bound of Awerbuch et al.
We prove the above bound using two new results that we believe are of independent interest. The first result is that a sequence of (``augmented'') weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes over the result of Cleve and Impagliazzo [Manuscript '93], who showed that the above holds for strong martingales, and allows in some setting to exploit this gap by efficient algorithms. We prove the above using a novel argument that does not follow the more complicated approach of Cleve and Impagliazzo}. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence.
Mon, 23 Apr 2018 19:28:36 +0300https://eccc.weizmann.ac.il/report/2017/168#revision6
Revision 5
| Tighter Bounds on Multi-Party Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling |
Amos Beimel,
Iftach Haitner,
Nikolaos Makriyannis,
Eran Omri
https://eccc.weizmann.ac.il/report/2017/168#revision5In his seminal work, Cleve [STOC '86] has proved that any $r$-round coin-flipping protocol can be efficiently biased by $\Theta(1/r)$. The above lower bound was met for the two-party case by Moran, Naor and Segev [Journal of Cryptology '16], and the three-party case (up to a polylog factor) by Haitner and Tsfadia [SICOMP '17], and was approached for $n$-party protocols when $n loglog r$, however, the best bias for $n$-party coin-flipping protocols remains $O(n/\sqrt{r})$ achieved by the majority protocol of Awerbuch, Blum, Chor, Goldwasser, and Micali [Manuscript '85].
Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant $\epsilon >0$, an $r^{\epsilon}$-party $r$-round coin-flipping protocol can be efficiently biased by $\widetilde{\Omega}(1/\sqrt{r})$. As far as we know, this is the first improvement of Cleve's bound that holds in the standard model, and is only $n=r^{\epsilon}$ (multiplicative) far from the aforementioned upper bound of Awerbuch et al.
For proving the above lower bound we present two new results that we believe are of independent interest. The first result is that a sequence of (augmented) weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes the result of Cleve and Impagliazzo [Manuscript '93], who proved that the above holds for strong martingales. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence. Tue, 05 Dec 2017 10:13:46 +0200https://eccc.weizmann.ac.il/report/2017/168#revision5
Revision 4
| Tighter Bounds on Multi-Party Coin Flipping, via Augmented Weak Martingales and Differentially Private Sampling |
Amos Beimel,
Iftach Haitner,
Nikolaos Makriyannis,
Eran Omri
https://eccc.weizmann.ac.il/report/2017/168#revision4In his seminal work, Cleve [STOC '86] has proved that any $r$-round coin-flipping protocol can be efficiently biased by $\Theta(1/r)$. The above lower bound was met for the two-party case by Moran, Naor and Segev [Journal of Cryptology '16], and the three-party case (up to a polylog factor) by Haitner and Tsfadia [SICOMP '17], and was approached for $n$-party protocols when $n loglog r$, however, the best bias for $n$-party coin-flipping protocols remains $O(n/\sqrt{r})$ achieved by the majority protocol of Awerbuch, Blum, Chor, Goldwasser, and Micali [Manuscript '85].% and \citeauthor{Cleve86} [STOC '86].
Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant $\epsilon >0$, an $r^{\epsilon}$-party $r$-round coin-flipping protocol can be efficiently biased by $\widetilde{\Omega}(1/\sqrt{r})$. As far as we know, this is the first improvement of Cleve's bound that holds in the standard model, and is only $n=r^{\epsilon}$ (multiplicative) far from the aforementioned upper bound of Awerbuch et al. % and \citeauthor{Cleve86}.
For proving the above lower bound we present two new results that we believe are of independent interest. The first result is that a sequence of (augmented) weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes the result of Cleve and Impagliazzo [Manuscript '93], who proved that the above holds for strong martingales. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence. Tue, 05 Dec 2017 09:00:58 +0200https://eccc.weizmann.ac.il/report/2017/168#revision4
Revision 3
| Tighter Bounds on Multi-Party Coin Flipping via Augmented Weak Martingales and Dierentially Private Sampling |
Amos Beimel,
Iftach Haitner,
Nikolaos Makriyannis,
Eran Omri
https://eccc.weizmann.ac.il/report/2017/168#revision3In his seminal work, Cleve [STOC '86] has proved that any $r$-round coin-flipping protocol can be efficiently biased by $\Theta(1/r)$. The above lower bound was met for the two-party case by Moran, Naor and Segev [Journal of Cryptology '16], and the three-party case (up to a polylog factor) by Haitner and Tsfadia [SICOMP '17], and was approached for $n$-party protocols when $n loglog r$, however, the best bias for $n$-party coin-flipping protocols remains $O(n/\sqrt{r})$ achieved by the majority protocol of Awerbuch, Blum, Chor, Goldwasser, and Micali [Manuscript '85].% and \citeauthor{Cleve86} [STOC '86].
Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant $\epsilon >0$, an $r^{\epsilon}$-party $r$-round coin-flipping protocol can be efficiently biased by $\widetilde{\Omega}(1/\sqrt{r})$. As far as we know, this is the first improvement of Cleve's bound that holds in the standard model, and is only $n=r^{\epsilon}$ (multiplicative) far from the aforementioned upper bound of Awerbuch et al. % and \citeauthor{Cleve86}.
For proving the above lower bound we present two new results that we believe are of independent interest. The first result is that a sequence of (augmented) weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes the result of Cleve and Impagliazzo [Manuscript '93], who proved that the above holds for strong martingales. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence. Sun, 03 Dec 2017 11:36:41 +0200https://eccc.weizmann.ac.il/report/2017/168#revision3
Revision 2
| Tighter Bounds on Multi-Party Coin Flipping, via Augmented Weak Martingales and Differentially Private Sampling |
Amos Beimel,
Iftach Haitner,
Nikolaos Makriyannis,
Eran Omri
https://eccc.weizmann.ac.il/report/2017/168#revision2In his seminal work, Cleve [STOC 1986] has proved that any r-round coin-flipping protocol can be efficiently biassed by ?(1/r). The above lower bound was met for the two-party case by Moran, Naor, and Segev [Journal of Cryptology '16], and the three-party case (up to a polylog factor) by Haitner and Tsfadia [SICOMP '17], and was approached for n-party protocols when n loglog r, however, the best bias for n-party coin-flipping protocols remains ?(n/?r) achieved by the majority protocol of Awerbuch, Blum, Chor, Goldwasser, and Micali [Manuscript '85].
Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant ? > 0, an r?-party r-round coin-flipping protocol can be efficiently biased by ?(1/?r). As far as we know, this is the rst improvement of Cleve's bound that holds in the standard model, and is only r? (multiplicative) far from the aforementioned upper bound of Awerbuch et al.
For proving the above lower bound, we present two new results that we believe are of independent interest. The first result is that a sequence of (augmented) weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes the result of Cleve and Impagliazzo [Manuscript '93], who proved that the above holds for strong martingales. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence.Tue, 28 Nov 2017 09:46:08 +0200https://eccc.weizmann.ac.il/report/2017/168#revision2
Revision 1
| Tighter Bounds on Multi-Party Coin Flipping, via Augmented Weak Martingales and Dierentially Private Sampling |
Amos Beimel,
Iftach Haitner,
Nikolaos Makriyannis,
Eran Omri
https://eccc.weizmann.ac.il/report/2017/168#revision1In his seminal work, Cleve [STOC 1986] has proved that any $r$-round coin-flipping protocol can be efficiently biassed by $\Omega(1/r)$. The above lower bound was met for the two-party case by Moran, Naor, and Segev [Journal of Cryptology '16], and the three-party case (up to a polylog factor) by Haitner and Tsfadia [SICOMP '17], and was approached for $n$-party protocols when $n \loglog r$, the best bias for $n$-party coin-flipping protocols remains $\Theta(n/\sqrt{r})$ achieved by the majority protocol of Awerbuch, Blum, Chor, Goldwasser, and Micali [Manuscript '85].
Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant $\epsilon$ > 0, an $r^{\epsilon}$-party r-round coin-flipping protocol can be efficiently biased by $\Omega(1/\sqrt{r})$. As far as we know, this is the rst improvement of Cleve's bound that holds in the standard model, and is only $r^{\epsilon}$ (multiplicative) far from the aforementioned upper bound of Awerbuch et al.
For proving the above lower bound, we present two new results that we believe are of independent interest. The first result is that a sequence of (augmented) weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes the result of Cleve and Impagliazzo [Manuscript '93], who proved that the above holds for strong martingales. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence.Mon, 06 Nov 2017 17:47:13 +0200https://eccc.weizmann.ac.il/report/2017/168#revision1
Paper TR17-168
| Tighter Bounds on Multi-Party Coin Flipping, via Augmented Weak Martingales and Dierentially Private Sampling |
Amos Beimel,
Iftach Haitner,
Nikolaos Makriyannis,
Eran Omri
https://eccc.weizmann.ac.il/report/2017/168In his seminal work, Cleve [STOC 1986] has proved that any r-round coin-flipping protocol can be efficiently biassed by ?(1/r). The above lower bound was met for the two-party case by Moran, Naor, and Segev [Journal of Cryptology '16], and the three-party case (up to a polylog factor) by Haitner and Tsfadia [SICOMP '17], and was approached for n-party protocols when n loglog r, however, the best bias for n-party coin-flipping protocols remains ?(n/?r) achieved by the majority protocol of Awerbuch, Blum, Chor, Goldwasser, and Micali [Manuscript '85].
Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant ? > 0, an r?-party r-round coin-flipping protocol can be efficiently biased by ?(1/?r). As far as we know, this is the rst improvement of Cleve's bound that holds in the standard model, and is only r? (multiplicative) far from the aforementioned upper bound of Awerbuch et al.
For proving the above lower bound, we present two new results that we believe are of independent interest. The first result is that a sequence of (augmented) weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes the result of Cleve and Impagliazzo [Manuscript '93], who proved that the above holds for strong martingales. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence.Sun, 05 Nov 2017 17:31:42 +0200https://eccc.weizmann.ac.il/report/2017/168