Alice seeks an information-theoretically secure source of private random data. Unfortunately, she lacks a personal source and must use remote sources controlled by other parties. Alice wants to simulate a coin flip of specified bias $\alpha$ , as a function of data she receives from $p$ sources; she seeks privacy from any coalition of $r$ of them. We show: If $p/2 \leq r < p$ , the bias can be any rational number and nothing else; if $0 < r < p/2$ , the bias can be any algebraic number and nothing else. The proof uses projective varieties, convex geometry, and the probabilistic method. Our results improve on those laid out by Yao, who asserts one direction of the $r=1$ case in his seminal paper [Yao82]. We also provide an application to secure multiparty computation.Alice seeks an information-theoretically secure source of private random data. Unfortunately, she lacks a personal source and must use remote sources controlled by other parties. Alice wants to simulate a coin flip of specified bias $\alpha$, as a function of data she receives from $p$ sources; she seeks privacy from any coalition of $r$ of them. We show: If $p/2 \leq r < p$, the bias can be any rational number and nothing else; if $0 < r < p/2$, the bias can be any algebraic number and nothing else. The proof uses projective varieties, convex geometry, and the probabilistic method. Our results improve on those laid out by Yao, who asserts one direction of the $r=1$ case in his seminal paper [Yao82]. We also provide an application to secure multiparty computation.

Sep 21, 20100 citations

On Statistical Security in Two-Party Computation

Dakshita Khurana, Muhammad Haris Mughees

Lecture notes in computer scienceJan 1, 20206 citations

An Almost-Optimally Fair Three-Party Coin-Flipping Protocol

Iftach Haitner, Eliad Tsfadia

In a multiparty fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. Cleve [in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1986, pp. 364--369] has shown that in the case of dishonest majority (i.e., at least half of the parties can be corrupted), in any $m$ -round coin-flipping protocol the corrupted parties can bias the honest parties' common output bit by $\Omega(\frac 1{m})$ . For more than two decades the best known coin-flipping protocols against dishonest majority had bias $\Theta(\frac {\ell}{\sqrt{m}})$ , where $\ell$ is the number of corrupted parties. This was changed by a recent breakthrough result of Moran, Naor, and Segev [in Theory of Cryptography, Lecture Notes in Comput. Sci. 5444, Springer, Berlin, 2009, pp. 1--18], who constructed an $m$ -round, two-party coin-flipping protocol with optimal bias $\Theta(\frac 1 m)$ . In a subsequent work, Beimel, Omri, and Orlov [in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1990, pp. 503--513] extended this result to the multiparty case in which less than $\frac23$ of the parties can be corrupted. Still, for the case of $\frac23$ (or more) corrupted parties, the best known protocol had bias $\Theta(\frac {\ell}{\sqrt{m}})$ . In particular, this was the state of affairs for the natural three-party case. We take a step toward eliminating the above gap, presenting an $m$ -round, three-party coin-flipping protocol, with bias $\frac{O(\log^3 m)}m$ . Our approach (which we also apply to the two-party case) does not follow the “threshold round" paradigm used in the work of Moran, Naor, and Segev and Beimel, Omri, and Orlov but rather is a variation of the majority protocol of Cleve used to obtain the aforementioned $\Theta(\frac {\ell}{\sqrt{m}})$ -bias protocol.In a multiparty fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. Cleve [in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1986, pp. 364--369] has shown that in the case of dishonest majority (i.e., at least half of the parties can be corrupted), in any $m$-round coin-flipping protocol the corrupted parties can bias the honest parties' common output bit by $\Omega(\frac 1{m})$. For more than two decades the best known coin-flipping protocols against dishonest majority had bias $\Theta(\frac {\ell}{\sqrt{m}})$, where $\ell$ is the number of corrupted parties. This was changed by a recent breakthrough result of Moran, Naor, and Segev [in Theory of Cryptography, Lecture Notes in Comput. Sci. 5444, Springer, Berlin, 2009, pp. 1--18], who constructed an $m$-round, two-party coin-flipping protocol with optimal bias $\Theta(\frac 1 m)$. In a subsequent work, Beimel, Omri, and Orlov [in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1990, pp. 503--513] extended this result to the multiparty case in which less than $\frac23$ of the parties can be corrupted. Still, for the case of $\frac23$ (or more) corrupted parties, the best known protocol had bias $\Theta(\frac {\ell}{\sqrt{m}})$. In particular, this was the state of affairs for the natural three-party case. We take a step toward eliminating the above gap, presenting an $m$-round, three-party coin-flipping protocol, with bias $\frac{O(\log^3 m)}m$. Our approach (which we also apply to the two-party case) does not follow the “threshold round" paradigm used in the work of Moran, Naor, and Segev and Beimel, Omri, and Orlov but rather is a variation of the majority protocol of Cleve used to obtain the aforementioned $\Theta(\frac {\ell}{\sqrt{m}})$-bias protocol.

SIAM Journal on ComputingJan 1, 201717 citations

Scalable and Unconditionally Secure Multiparty Computation

Ivan Damgård, Jesper Buus Nielsen

Springer eBooksAug 9, 2007274 citations

Cheat-Penalised Quantum Weak Coin-Flipping

Atul Singh Arora, Carl A. Miller, Mauro E. S. Morales +1 more

Coin-flipping is a fundamental task in two-party cryptography where two remote mistrustful parties wish to generate a shared uniformly random bit. While quantum protocols promising near-perfect security exist for weak coin-flipping -- when the parties want opposing outcomes -- it has been shown that they must be inefficient in terms of their round complexity, and it is an open question of how space efficient they can be. In this work, we consider a variant called cheat-penalised weak coin-flipping in which if a party gets caught cheating, they lose $Λ$ points (compared to $0$ in the standard definition). We find that already for a small cheating penalty, the landscape of coin-flipping changes dramatically. For example, with $Λ=0.01$ , we exhibit a protocol where neither Alice nor Bob can bias the result in their favour beyond $1/2 + 10^{-8}$ , which uses $24$ qubits and $10^{16}$ rounds of communication (provably $10^{7}$ times better than any weak coin-flipping protocol with matching security). For the same space requirements, we demonstrate how one can choose between lowering how much a malicious party can bias the result (down to $1/2 + 10^{-10}$ ) and reducing the rounds of communication (down to $25,180$ ), depending on what is preferred. To find these protocols, we make two technical contributions. First, we extend the point game-protocol correspondence introduced by Kitaev and Mochon, to incorporate: (i) approximate point games, (ii) the cheat-penalised setting, and (iii) round and space complexity. Second, we give the first (to the best of our knowledge) numerical algorithm for constructing (approximate) point games that correspond to high security and low complexity. Our results open up the possibility of having secure and practical quantum protocols for multiparty computation.Coin-flipping is a fundamental task in two-party cryptography where two remote mistrustful parties wish to generate a shared uniformly random bit. While quantum protocols promising near-perfect security exist for weak coin-flipping -- when the parties want opposing outcomes -- it has been shown that they must be inefficient in terms of their round complexity, and it is an open question of how space efficient they can be. In this work, we consider a variant called cheat-penalised weak coin-flipping in which if a party gets caught cheating, they lose $Λ$ points (compared to $0$ in the standard definition). We find that already for a small cheating penalty, the landscape of coin-flipping changes dramatically. For example, with $Λ=0.01$, we exhibit a protocol where neither Alice nor Bob can bias the result in their favour beyond $1/2 + 10^{-8}$, which uses $24$ qubits and $10^{16}$ rounds of communication (provably $10^{7}$ times better than any weak coin-flipping protocol with matching security). For the same space requirements, we demonstrate how one can choose between lowering how much a malicious party can bias the result (down to $1/2 + 10^{-10}$) and reducing the rounds of communication (down to $25,180$), depending on what is preferred. To find these protocols, we make two technical contributions. First, we extend the point game-protocol correspondence introduced by Kitaev and Mochon, to incorporate: (i) approximate point games, (ii) the cheat-penalised setting, and (iii) round and space complexity. Second, we give the first (to the best of our knowledge) numerical algorithm for constructing (approximate) point games that correspond to high security and low complexity. Our results open up the possibility of having secure and practical quantum protocols for multiparty computation.

arXiv:2510.03218Oct 3, 20250 citations

\alpha

, as a function of data she receives from

p

sources; she seeks privacy from any coalition of

r

of them. We show: If

p/2 \leq r < p

, the bias can be any rational number and nothing else; if

0 < r < p/2

, the bias can be any algebraic number and nothing else. The proof uses projective varieties, convex geometry, and the probabilistic method. Our results improve on those laid out by Yao, who asserts one direction of the

r=1

case in his seminal paper [Yao82]. We also provide an application to secure multiparty computation.

m

-round coin-flipping protocol the corrupted parties can bias the honest parties' common output bit by

\Omega(\frac 1{m})

. For more than two decades the best known coin-flipping protocols against dishonest majority had bias

\Theta(\frac {\ell}{\sqrt{m}})

, where

\ell

is the number of corrupted parties. This was changed by a recent breakthrough result of Moran, Naor, and Segev [in Theory of Cryptography, Lecture Notes in Comput. Sci. 5444, Springer, Berlin, 2009, pp. 1--18], who constructed an

m

-round, two-party coin-flipping protocol with optimal bias

\Theta(\frac 1 m)

. In a subsequent work, Beimel, Omri, and Orlov [in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1990, pp. 503--513] extended this result to the multiparty case in which less than

\frac23

of the parties can be corrupted. Still, for the case of

\frac23

(or more) corrupted parties, the best known protocol had bias

\Theta(\frac {\ell}{\sqrt{m}})

. In particular, this was the state of affairs for the natural three-party case. We take a step toward eliminating the above gap, presenting an

m

-round, three-party coin-flipping protocol, with bias

\frac{O(\log^3 m)}m

. Our approach (which we also apply to the two-party case) does not follow the “threshold round" paradigm used in the work of Moran, Naor, and Segev and Beimel, Omri, and Orlov but rather is a variation of the majority protocol of Cleve used to obtain the aforementioned

\Theta(\frac {\ell}{\sqrt{m}})

-bias protocol.

Λ

points (compared to

0

in the standard definition). We find that already for a small cheating penalty, the landscape of coin-flipping changes dramatically. For example, with

Λ=0.01

, we exhibit a protocol where neither Alice nor Bob can bias the result in their favour beyond

1/2 + 10^{-8}

, which uses

24

qubits and

10^{16}

rounds of communication (provably

10^{7}

times better than any weak coin-flipping protocol with matching security). For the same space requirements, we demonstrate how one can choose between lowering how much a malicious party can bias the result (down to

1/2 + 10^{-10}

) and reducing the rounds of communication (down to

25,180

), depending on what is preferred. To find these protocols, we make two technical contributions. First, we extend the point game-protocol correspondence introduced by Kitaev and Mochon, to incorporate: (i) approximate point games, (ii) the cheat-penalised setting, and (iii) round and space complexity. Second, we give the first (to the best of our knowledge) numerical algorithm for constructing (approximate) point games that correspond to high security and low complexity. Our results open up the possibility of having secure and practical quantum protocols for multiparty computation.