Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

SIAM Journal on Computing

The Round Complexity of Two-Party Random Selection

Saurabh Sanghvi, Salil Vadhan

Published Jan 1, 2008• 7 citations
Publisher

Abstract

We study the round complexity of two-party protocols for generating a random n-bit string such that the output is guaranteed to have bounded “bias,” even if one of the two parties deviates from the protocol (possibly using unlimited computational resources). Specifically, we require that the output's statistical difference from the uniform distribution on $\{0,1\}^n$ is bounded by a constant less than 1. We present a protocol for the above problem that has $2 \log^* n + O(1)$ rounds, improving a previous $2n$-round protocol of Goldreich, Goldwasser, and Linial (FOCS '91). Like the GGL Protocol, our protocol actually provides a stronger guarantee, ensuring that the output lands in any set $T \subseteq \{0,1\}^n$ of density $\mu$ with probability at most $O(\sqrt{\mu + \delta})$, where $\delta$ may be an arbitrarily small constant. We then prove a nearly matching lower bound, showing that any protocol guaranteeing bounded statistical difference requires at least $\log^* n - \log^* \log^* n - O(1)$ rounds. We also prove several results for the case when the output's bias is measured by the maximum multiplicative factor by which a party can increase the probability of a set $T \subseteq \{0,1\}^n$.

DOI
10.1137/050641715

Related papers

The round complexity of two-party random selection

Saurabh Sanghvi, Salil Vadhan

We study the round complexity of two-party protocols for generating a random n-bit string such that the output is guaranteed to have bounded “bias ” even if one of the two parties deviates from the protocol (possibly using unlimited computational resources). Specifically, we require that the output’s statistical difference from the uniform distribution on {0, 1} n is bounded by a constant less than 1. We present a protocol for the above problem that has 2 log ∗ n + O(1) rounds, improving a previous 2n-round protocol of Goldreich, Goldwasser, and Linial (FOCS ’91). Like the GGL Protocol, our protocol actually provides a stronger guarantee, ensuring that the output lands in any set T ⊆ {0, 1} n of density µ with probability at most O ( √ µ + δ), where δ may be an arbitrarily small constant. We then prove a nearly matching lower bound, showing that any protocol guaranteeing bounded statistical difference requires at least log ∗ n − log ∗ log ∗ n − O(1) rounds. We also prove several results for the case when the output’s bias is measured by the maximum multiplicative factor by which a party can increase the probability of a set T ⊆ {0, 1} n.

•Jan 1, 2005•0 citations

The round complexity of two-party random selection

Saurabh Sanghvi, Salil Vadhan

We study the round complexity of two-party protocols for generating a random n-bit string such that the output is guaranteed to have bounded bias (according to some measure) even if one of the two parties deviates from the protocol (even using unlimited computational resources). Specifically, we require that the output's statistical difference from the uniform distribution on zon is bounded by a constant less than 1.We present a protocol for the above problem that has 2 log*n+O(1) rounds, improving a 2n-round protocol that follows from the work of Goldreich, Goldwasser, and Linial (FOCS'91). Like the GGL protocol, our protocol actually provides a stronger guarantee, ensuring that the output lands in any set T⊆zon of density μ with probability at most O(√μ+δ), where δ is an arbitarily small constant.We then prove a matching lower bound, showing that any protocol guaranteeing bounded statistical difference requires at least log*n - log* log*n-O(1) rounds. As far as we know, this is the first nontrivial lower bound on the round complexity of random selection protocols (of any type) that does not impose additional constraints (e.g. on communication or "simulatability").We also state several results for the case when the output's bias is measured by the maximum multiplicative factor by which a party can increase the probability of a set T ⊆ zon.

ACM Symposium on Theory of Computing (STOC)•May 22, 2005•13 citations

High Entropy Random Selection Protocols (Extended Abstract)

Harry Buhrman, Matthias Christandl, Michal Kouck +3 more

Abstract. We study the two party problem of randomly selecting a string among all the strings of length n. We want the protocol to have the property that the output distribution has high entropy, even when one of the two parties is dishonest and deviates from the protocol. We develop protocols that achieve high, close to n, entropy. In the literature the randomness guarantee is usually expressed as being close to the uniform distribution or in terms of resiliency. The notion of entropy is not directly comparable to that of resiliency, but we establish a connection between the two that allows us to compare our protocols with the existing ones. We construct an explicit protocol that yields entropy n − O(1) and has 4log ∗ n rounds, improving over the protocol of Goldreich et al. [3] that also achieves this entropy but needs O(n) rounds. Both these protocols need O(n 2) bits of communication. Next we reduce the communication in our protocols. We show the existence, nonexplicitly, of a protocol that has 6 rounds, 2n + 8log n bits of communication

•Jan 1, 2008•0 citations

High Entropy Random Selection Protocols

Nikolay Vereshchagin, Harry Buhrman, Cristandl, Matthias +3 more

We study the two party problem of randomly selecting a string among all the strings of length n. We want the protocol to have the property that the output distribution has high entropy, even when one of the two parties is dishonest and deviates from the protocol. We develop protocols that achieve high, close to n, entropy. In the literature the randomness guarantee is usually expressed as being close to the uniform distribution or in terms of resiliency. The notion of entropy is not directly comparable to that of resiliency, but we establish a connection between the two that allows us to compare our protocols with the existing ones. We construct an explicit protocol that yields entropy n - O(1) and has 4log^* n rounds, improving over the protocol of Goldwasser et al. that also achieves this entropy but needs O(n) rounds. Both these protocols need O(n^2) bits of communication. Next we reduce the communication in our protocols. We show the existence, non-explicitly, of a protocol that has 6-rounds, 2n + 8log n bits of communication and yields entropy n- O(log n) and min-entropy n/2 - O(log n). Our protocol achieves the same entropy bound as the recent, also non-explicit, protocol of Gradwohl et al., however achieves much higher min-entropy: n/2 - O(log n) versus O(log n). Finally we exhibit very simple explicit protocols. We connect the security parameter of these geometric protocols with the well studied Kakeya problem motivated by harmonic analysis and analytical number theory. We are only able to prove that these protocols have entropy 3n/4 but still n/2 - O(log n) min-entropy. Therefore they do not perform as well with respect to the explicit constructions of Gradwohl et al. entropy-wise, but still have much better min-entropy. We conjecture that these simple protocols achieve n -o(n) entropy. Our geometric construction and its relation to the Kakeya problem follows a new and different approach to the random selection problem than any of the previously known protocols.

Dagstuhl Seminar Proceedings•Jan 1, 2008•0 citations

A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip

Iftach Haitner, Yonatan Karidi-Heller

In a distributed coin-flipping protocol, Blum [ACM Transactions on Computer Systems ’83], the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip, Ben-Or and Linial [FOCS ’85], the parties communicate over a broadcast channel, and a computationally unbounded adversary can choose which parties to corrupt along the protocol execution. Ben-Or and Linial proved that the n -party majority protocol is resilient to \(O(\sqrt {n})\) corruptions, and conjectured this is a tight upper bound for any n -party protocol (of any round complexity). Their conjecture was proved to be correct, up to polylogarithmic factors, for single-turn (each party sends a single message) single-bit (a message is one bit) protocols Lichtenstein et al. [Combinatorica ’89], symmetric protocols Goldwasser et al. [ICALP ’15], and recently for (arbitrary message length) single-turn protocols Tauman Kalai et al. [DISC ’18]. Yet, the question of many-turn protocols was left entirely open. In this work, we close the above gap, proving that no n -party protocol (of any round complexity) is resilient to \(\Omega (\sqrt {n} \cdot \log ^3 n)\) adaptive corruptions. Namely, majority is the optimal coin-flipping protocol against adaptive adversaries (up to polylogarithmic factors).

arXiv:2005.01565•Annual Symposium on Foundations of Computer Science•Nov 1, 2020•13 citations

Tighter Bounds on Multi-Party Coin Flipping via Augmented Weak Martingales and Differentially Private Sampling

Amos Beimel, Iftach Haitner, Nikolaos Makriyannis +1 more

In his seminal work, Cleve [STOC '86] has proved that any $r$-round coin-flipping protocol can be efficiently biased by $Θ(1/r)$. This 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 Tsfadi [SICOMP '17], and was approached for $n$-party protocols when $n< loglog r$ by Buchbinder, Haitner, Levi, and Tsfadia [SODA '17]. For $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 $ε>0$, an $r^ε$-party $r$-round coin-flipping protocol can be efficiently biased by $\widetildeΩ(1/\sqrt{r})$. As far as we know, this is the first improvement of Cleve's bound, and is only $n=r^ε$ (multiplicative) far from the aforementioned upper bound of Awerbuch et al.

arXiv:2105.00743•May 3, 2021•0 citations
We study the round complexity of two-party protocols for generating a random n-bit string such that the output is guaranteed to have bounded “bias,” even if one of the two parties deviates from the protocol (possibly using unlimited computational resources). Specifically, we require that the output's statistical difference from the uniform distribution on {0,1}n\{0,1\}^n{0,1}n is bounded by a constant less than 1. We present a protocol for the above problem that has 2log⁡∗n+O(1)2 \log^* n + O(1)2log∗n+O(1) rounds, improving a previous 2n2n2n-round protocol of Goldreich, Goldwasser, and Linial (FOCS '91). Like the GGL Protocol, our protocol actually provides a stronger guarantee, ensuring that the output lands in any set T⊆{0,1}nT \subseteq \{0,1\}^nT⊆{0,1}n of density μ\muμ with probability at most O(μ+δ)O(\sqrt{\mu + \delta})O(μ+δ​), where δ\deltaδ may be an arbitrarily small constant. We then prove a nearly matching lower bound, showing that any protocol guaranteeing bounded statistical difference requires at least log⁡∗n−log⁡∗log⁡∗n−O(1)\log^* n - \log^* \log^* n - O(1)log∗n−log∗log∗n−O(1) rounds. We also prove several results for the case when the output's bias is measured by the maximum multiplicative factor by which a party can increase the probability of a set T⊆{0,1}nT \subseteq \{0,1\}^nT⊆{0,1}n.
We study the round complexity of two-party protocols for generating a random n-bit string such that the output is guaranteed to have bounded “bias ” even if one of the two parties deviates from the protocol (possibly using unlimited computational resources). Specifically, we require that the output’s statistical difference from the uniform distribution on {0, 1} n is bounded by a constant less than 1. We present a protocol for the above problem that has 2 log ∗ n + O(1) rounds, improving a previous 2n-round protocol of Goldreich, Goldwasser, and Linial (FOCS ’91). Like the GGL Protocol, our protocol actually provides a stronger guarantee, ensuring that the output lands in any set T ⊆ {0, 1} n of density µ with probability at most O ( √ µ + δ), where δ may be an arbitrarily small constant. We then prove a nearly matching lower bound, showing that any protocol guaranteeing bounded statistical difference requires at least log ∗ n − log ∗ log ∗ n − O(1) rounds. We also prove several results for the case when the output’s bias is measured by the maximum multiplicative factor by which a party can increase the probability of a set T ⊆ {0, 1} n.
We study the round complexity of two-party protocols for generating a random n-bit string such that the output is guaranteed to have bounded bias (according to some measure) even if one of the two parties deviates from the protocol (even using unlimited computational resources). Specifically, we require that the output's statistical difference from the uniform distribution on zon is bounded by a constant less than 1.We present a protocol for the above problem that has 2 log*n+O(1) rounds, improving a 2n-round protocol that follows from the work of Goldreich, Goldwasser, and Linial (FOCS'91). Like the GGL protocol, our protocol actually provides a stronger guarantee, ensuring that the output lands in any set T⊆zon of density μ with probability at most O(√μ+δ), where δ is an arbitarily small constant.We then prove a matching lower bound, showing that any protocol guaranteeing bounded statistical difference requires at least log*n - log* log*n-O(1) rounds. As far as we know, this is the first nontrivial lower bound on the round complexity of random selection protocols (of any type) that does not impose additional constraints (e.g. on communication or "simulatability").We also state several results for the case when the output's bias is measured by the maximum multiplicative factor by which a party can increase the probability of a set T ⊆ zon.
Abstract. We study the two party problem of randomly selecting a string among all the strings of length n. We want the protocol to have the property that the output distribution has high entropy, even when one of the two parties is dishonest and deviates from the protocol. We develop protocols that achieve high, close to n, entropy. In the literature the randomness guarantee is usually expressed as being close to the uniform distribution or in terms of resiliency. The notion of entropy is not directly comparable to that of resiliency, but we establish a connection between the two that allows us to compare our protocols with the existing ones. We construct an explicit protocol that yields entropy n − O(1) and has 4log ∗ n rounds, improving over the protocol of Goldreich et al. [3] that also achieves this entropy but needs O(n) rounds. Both these protocols need O(n 2) bits of communication. Next we reduce the communication in our protocols. We show the existence, nonexplicitly, of a protocol that has 6 rounds, 2n + 8log n bits of communication
We study the two party problem of randomly selecting a string among all the strings of length n. We want the protocol to have the property that the output distribution has high entropy, even when one of the two parties is dishonest and deviates from the protocol. We develop protocols that achieve high, close to n, entropy. In the literature the randomness guarantee is usually expressed as being close to the uniform distribution or in terms of resiliency. The notion of entropy is not directly comparable to that of resiliency, but we establish a connection between the two that allows us to compare our protocols with the existing ones. We construct an explicit protocol that yields entropy n - O(1) and has 4log^* n rounds, improving over the protocol of Goldwasser et al. that also achieves this entropy but needs O(n) rounds. Both these protocols need O(n^2) bits of communication. Next we reduce the communication in our protocols. We show the existence, non-explicitly, of a protocol that has 6-rounds, 2n + 8log n bits of communication and yields entropy n- O(log n) and min-entropy n/2 - O(log n). Our protocol achieves the same entropy bound as the recent, also non-explicit, protocol of Gradwohl et al., however achieves much higher min-entropy: n/2 - O(log n) versus O(log n). Finally we exhibit very simple explicit protocols. We connect the security parameter of these geometric protocols with the well studied Kakeya problem motivated by harmonic analysis and analytical number theory. We are only able to prove that these protocols have entropy 3n/4 but still n/2 - O(log n) min-entropy. Therefore they do not perform as well with respect to the explicit constructions of Gradwohl et al. entropy-wise, but still have much better min-entropy. We conjecture that these simple protocols achieve n -o(n) entropy. Our geometric construction and its relation to the Kakeya problem follows a new and different approach to the random selection problem than any of the previously known protocols.
In a distributed coin-flipping protocol, Blum [ACM Transactions on Computer Systems ’83], the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip, Ben-Or and Linial [FOCS ’85], the parties communicate over a broadcast channel, and a computationally unbounded adversary can choose which parties to corrupt along the protocol execution. Ben-Or and Linial proved that the n -party majority protocol is resilient to O(n)O(\sqrt {n})O(n​) corruptions, and conjectured this is a tight upper bound for any n -party protocol (of any round complexity). Their conjecture was proved to be correct, up to polylogarithmic factors, for single-turn (each party sends a single message) single-bit (a message is one bit) protocols Lichtenstein et al. [Combinatorica ’89], symmetric protocols Goldwasser et al. [ICALP ’15], and recently for (arbitrary message length) single-turn protocols Tauman Kalai et al. [DISC ’18]. Yet, the question of many-turn protocols was left entirely open. In this work, we close the above gap, proving that no n -party protocol (of any round complexity) is resilient to Ω(n⋅log⁡3n)\Omega (\sqrt {n} \cdot \log ^3 n)Ω(n​⋅log3n) adaptive corruptions. Namely, majority is the optimal coin-flipping protocol against adaptive adversaries (up to polylogarithmic factors).
In his seminal work, Cleve [STOC '86] has proved that any rrr-round coin-flipping protocol can be efficiently biased by Θ(1/r)Θ(1/r)Θ(1/r). This 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 polylogpolylogpolylog factor) by Haitner and Tsfadi [SICOMP '17], and was approached for nnn-party protocols when n<loglogrn< loglog rn<loglogr by Buchbinder, Haitner, Levi, and Tsfadia [SODA '17]. For n>loglogrn> loglog rn>loglogr, however, the best bias for nnn-party coin-flipping protocols remains O(n/r)O(n/\sqrt{r})O(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ε>0ε>0, an rεr^εrε-party rrr-round coin-flipping protocol can be efficiently biased by Ω~(1/r)\widetildeΩ(1/\sqrt{r})Ω(1/r​). As far as we know, this is the first improvement of Cleve's bound, and is only n=rεn=r^εn=rε (multiplicative) far from the aforementioned upper bound of Awerbuch et al.