A Coin-Flip Protocol Sample Clauses

A Coin-Flip Protocol. We describe here a protocol that allows parties to generate a sequence of random bits (coins) Coin1, . . . , CoinT for a pre-determined parameter T . We denote the sub-protocol to generate the ith coin by CoinFlip(i). Roughly speaking, the pro- tocol guarantees that (1) when all honest parties invoke CoinFlip(i), all honest parties output the same value Coini and (2) until the first honest party invokes CoinFlip(i), the value of Coini is uniform. Our coin-flip protocol assumes setup provided by a trusted dealer that takes the following form: For each iteration 1, . . . , T , the dealer chooses uniform Coini 0, 1 chooses a random subset Ei of the parties by including each party in Ei with probability κ/n; and then gives authenticated secret shares of Coini (using a perfectly secret κ/3 -out-of- Ei secret-sharing scheme) to the members of Ei. (Authentication is done by having the dealer sign the shares.) Since each share (including the signature) has size O(κ), the size of the setup is O(κ2T ). The coin-flip protocol itself simply involves having the parties in the relevant subset send their shares to everyone else. The communication complexity is thus O(κ2n) per iteration. Lemma 1. Let 0 < ϵ < 1/3 and f (1 2ϵ) n/3. Then as long as at most f parties are corrupted, CoinFlip(i) satisfies the following: 1. all honest parties obtain the same value Coini, 2. until the first honest party invokes CoinFlip(i), the value of Coini is uniform from the adversary’s perspective.

A Coin-Flip Protocol. We describe here a protocol that allows parties to generate a sequence of random bits (coins) Coin1, . . . , CoinT for a pre-determined parameter T . We denote the sub-protocol to generate the ith coin by CoinFlip(i). Roughly speaking, the protocol guarantees that (1) when all honest parties invoke CoinFlip(i), all honest parties output the same value Coini and (2) until the first honest party invokes CoinFlip(i), the value of Coini is uniform. Our coin-flip protocol assumes setup provided by a trusted dealer that takes the following form: For each iteration 1, . . . , T , the dealer chooses uniform Coini ∈ {0, 1}; chooses a random subset Ei of the parties by including each party in Ei with probability n/n; and then gives authenticated secret shares of Coini (using a perfectly secret [n/3|-out-of-|Ei| secret-sharing scheme) to the members of Ei. (Authentication is done by having the dealer sign the shares.) Since each share (including the signature) has size O(n), the size of the setup is O(n2T ). The coin-flip protocol itself simply involves having the parties in the relevant subset send their shares to everyone else. The communication complexity is thus O(n2n) per iteration. Lemma 8 Let 0 < ϵ < 1/3 and ƒ ≤ (1 − 2ϵ) · n/3. Then as long as at most ƒ parties are corrupted, CoinFlip(i) satisfies the following: 1. all honest parties obtain the same value Coini, 2. until the first honest party invokes CoinFlip(i), the value of Coini is uniform from the adversary’s perspective. Proof Lemma 24 implies that, except with negligible probability, Ei contains more than [n/3| honest parties and fewer than (1 − ϵ) · n/3 corrupted parties. The stated properties follow.