Robust Coin Flipping
Gene S. Kopp and John D. Wiltshire-Gordon
University of Michigan

Abstract. 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 simulatea coin ﬂip of speciﬁed bias α, as a function of data she receives from psources; she seeks privacy from any coalition of r of them. We show: If
p/2 ≤ 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.
Keywords: multiparty computation, outsourcing randomness, biased
coin ﬂip, algebraic number, projective duality, hyperdeterminant.

1

Introduction

Alice has a perfectly fair penny—one that lands heads exactly 50% of the time.
Unfortunately, the penny is mixed in with a jar of ordinary, imperfect pennies.
The truly fair penny can never be distinguished from the other pennies, sinceno amount of experimentation can identify it with certainty. Still, Alice has
discovered a workable solution. Whenever she needs a fair coin ﬂip, she ﬂips all
the pennies and counts the Lincolns; an even number means heads, and an odd
number means tails.
Alice’s technique is an example of “robust coin ﬂipping.” She samples many
random sources, some speciﬁed number of which are unreliable, and still manages to simulate a desired coin ﬂip. Indeed, Alice’s technique works even if theunreliable coin ﬂips somehow fail to be independent.
Bob faces a sort of converse problem. He’s marooned on an island, and thenearest coin is over three hundred miles away. Whenever he needs a fair coin ﬂip,
he calls up two trustworthy friends who don’t know each other, asking for random equivalence classes modulo two. Since the sum of the classes is completelyIt is our pleasure to thank Tom Church, for helping simplify our original proof ofalgebraicity of mystery-values; László Babai, for providing guidance with respect topublication; László Csirmaz, for discussing secret-sharing with us; Victor Protsak,
for pointing us to Lind’s article [Lin84]; and Matthew Woolf, Nic Ford, Vipul Naik,and Steven J. Miller for reading drafts and providing helpful comments. We are also
grateful to several anonymous referees for their suggestions.

D. Pointcheval and T. Johansson (Eds.): EUROCRYPT 2012, LNCS 7237, pp. 172–194, 2012.
c International Association for Cryptologic Research 2012


Robust Coin Flipping

173

mysterious to either of the friends, Bob may safely use the sum to make private
decisions.
Bob’s technique seems similar to Alice’s, and indeed we shall see that the two
predicaments are essentially the same. We shall also see that the story for biased
coin ﬂips is much more complex.
1.1

Preliminaries and Definitions

Informally, we think of a random source as a (possibly remote) machine capableof sampling from certain probability spaces. Formally, a random source is acollection C of probability spaces that is closed under quotients. That is, if X ∈ C
and there is a measure-preserving map1 X → Y , then Y ∈ C. Random sources
are partially ordered by inclusion: We say that C is stronger than D iﬀ C ⊃ D.
The quotients of a probability space X are precisely the spaces a person canmodel with X. For example, one can model a fair coin with a fair die: Label threeof the die’s faces “heads” and the other three “tails.” Similarly, one can model
the uniform rectangle [0, 1]2 with the uniform interval [0, 1]: Take a decimal
expansion of each point in [0, 1], and build two new decimals, one from the oddnumbered digits and one from the even-numbered digits.2 Thus, forcing C to beclosed under quotients is not a real restriction; it allows us to capture the notionthat “a fair die is more powerful that a fair coin.”3
We deﬁne an infinite random source to be one that contains an inﬁnite
space.4 A finite random source, on the other hand, contains only ﬁnite probability spaces. Further, for any set of numbers S, we deﬁne an S-random source
to be one which is forced to take probabilities in S. That is, all the measurable
sets in its probability spaces have measures in S.
Sometimes we will ﬁnd it useful to talk about the strongest random source insome collection of sources. We call such a random source full-strength for thatcollection. For instance, a full-strength ﬁnite random source can model any ﬁnite
probability space, and a full-strength S-random source can model any S-random
source.
In practice, when p people simulate a private random source for someone else,they may want to make sure that privacy is preserved even if a few people blababout the data from their random sources or try to game the system. Deﬁne an rrobust function of p independent random variables to be one whose distribution
1

A measure-preserving map (morphism in the category of probability spaces) is afunction for which the inverse image of every measurable set is measurable and has
the same measure. Any measure-preserving map may be thought of as a quotient“up to measure zero.”2
In fact, this deﬁnes an isomorphism of probability spaces between the rectangle andthe interval.
3
It would also be natural (albeit unnecessary) to require that C is closed under ﬁnite
products.
4
An inﬁnite space is one that is not isomorphic to any ﬁnite space. A space withexactly 2012 measurable sets will always be isomorphic to a ﬁnite space, no matter
how large it is as a set.

174

G.S. Kopp and J.D. Wiltshire-Gordon

does not change when the joint distribution of any r of the random variables isaltered. Saying that p people simulate a random source r-robustly is equivalent
to asserting that the privacy of that source is preserved unless someone learns thedata of more than r participants. Similarly, to simulate a random source using psources, at least q of which are working properly, Alice must run a (p − q)-robust
simulation.
By a robust function or simulation, we mean a 1-robust one.
We use J to denote the all-ones tensor of appropriate dimensions. When weapply J to a vector or hypermatrix, we always mean “add up the entries.”
1.2

Results

This paper answers the question “When can a function sampling from p independent random sources be protected against miscalibration or dependency amongp − q of them?” (Alice’s predicament), or equivalently, “When can p people withrandom sources simulate a private random source for someone else5 in a waythat protects against gossip among any p − q of them?” (Bob’s predicament). In
the ﬁrst question, we assume that at least q of the sources are still functioning
correctly, but we don’t know which. In the second question, we assume that atleast q of the people keep their mouths shut, but we don’t know who. In theterminology just introduced, we seek a (p − q)-robust simulation.
Consider the case of p full-strength ﬁnite random sources. We prove: If
1 ≤ q ≤ p/2, the people may simulate any ﬁnite Q-random source and nothing
better; if p/2 < q < p, they may simulate any ﬁnite Q-random source and nothing
better. The proof uses projective varieties, convex geometry, and the probabilistic method. We also deal brieﬂy with the case of inﬁnite random sources, inwhich full-strength simulation is possible, indeed easy (see Appendix C).
1.3

Yao’s Robust Coin Flipping

Our work ﬁts in the context of secure multiparty computation, a ﬁeld with rootsin A. C. Yao’s inﬂuential paper [Yao82]. In the last section of his paper, entitled“What cannot be done?”, Yao presents (a claim equivalent to) the following
theorem:
Theorem 1 (A. C. Yao). Alice has several ﬁnite random sources, and shewants to generate a random bit with bias α. Unfortunately, she knows that oneof them may be miscalibrated, and she doesn’t know which one. This annoyanceactually makes her task impossible if α is a transcendental number.
It does not not suﬃce for Alice to just program the distribution (α 1 − α) into
one of the random sources and record the result; this fails because she might
use the miscalibrated one! We require—as in our jar of pennies example—that
5

Later, we give an application to secure multiparty computation in which the outputof the simulated random source has no single recipient, but is utilized by the group
without any individual gaining access; see Section 3.

Robust Coin Flipping

175

Alice’s algorithm be robust enough to handle unpredictable results from any
single source.
Unfortunately, Yao provides no proof of the theorem, and we are not aware of
any in the literature. Yao’s theorem is a special case of the results we describedin the previous section.

2

Simulating Finite Random Sources

The following result is classical.
Proposition 2. If p players are equipped with private d-sided dice, they may(p − 1)-robustly simulate a d-sided die.
Proof. We provide a direct construction. Fix a group G of order d (such as thecyclic group Z/dZ). The ith player uses the uniform measure to pick gi ∈ G at
random. The roll of the simulated die will be the product g1 g2 · · · gp .
It follows from the G-invariance of the uniform measure that any p-subset of{g1 , g2 , . . . , gp , g1 g2 · · · gp }(1)

is independent! Thus, this is a (p − 1)-robust simulation.
For an example of this construction, consider how Alice and Bob may robustly
ﬂip a coin with bias 2/5. Alice picks an element a ∈ Z/5Z, and Bob picks anelement b ∈ Z/5Z; both do so using the uniform distribution. Then, a, b, and a+b
are pairwise independent! We say that the coin came up heads if a + b ∈ {0, 1}
and tails if a + b ∈ {2, 3, 4}.
This construction exploits the fact that several random variables may be pairwise (or (p − 1)-setwise) independent but still dependent overall. In cryptology,
this approach goes back to the one-time pad. Shamir [Sha79] uses it to develop
secret-sharing protocols, and these are exploited in multiparty computation tosuch ends as playing poker without cards [GM82, GMW87].
Corollary 3. If p players are equipped with private, full-strength ﬁnite Q-random
sources, they may (p− 1)-robustly simulate a private, full-strength ﬁnite Q-random
source for some other player.
Proof. Follows from Proposition 2 because any ﬁnite rational probability space
is a quotient of some ﬁnite uniform distribution.
2.1

Cooperative Numbers

We deﬁne a useful class of numbers.
Definition 4. If p people with private full-strength ﬁnite random sources canrobustly simulate a coin ﬂip with bias α, we say α is p-cooperative. We denotethe set of p-cooperative numbers by C(p).

176

G.S. Kopp and J.D. Wiltshire-Gordon

The ability to robustly simulate coin ﬂips of certain bias is enough to robustly
simulate any ﬁnite spaces with points having those biases, assuming some hypotheses about C(p) which we will later see to be true.
Lemma 5. Suppose that, if α, α ∈ C(p) and α < α , then α/α ∈ C(p). If p people have full-strength ﬁnite random sources, they can robustly simulate precisely
ﬁnite C(p)-random sources.
Proof. Clearly, any random source they simulate must take p-cooperative probabilities, because any space with a subset of mass α has the space (α 1 − α) asa quotient.
In the other direction, consider a ﬁnite probability space with point masses( α1 α2 · · · αn )(2)in C(p). Robustly ﬂip a coin of bias α1 . In the heads case, we pick the ﬁrst point.
In the tails case, we apply induction to robustly simulate( α2 /(1 − α1 ) · · · αn /(1 − α1 ) ).

(3)

This is possible because 1 − α1 ∈ C(p) by symmetry, and so the ratios
αi /(1 − α1 ) ∈ C(p) by assumption.
2.2

Restatement Using Multilinear Algebra

Consider a {heads, tails}-valued function of several independent ﬁnite probability spaces that produces an α-biased coin ﬂip when random sources sample
the spaces. If we model each probability space as a stochastic vector—that is,a nonnegative vector whose coordinates sum to one—we may view the productprobability space as the Kronecker product of these vectors. Each entry in the
resulting tensor represents the probability of a certain combination of outputs
from the random sources. Since the sources together determine the ﬂip, some ofthese entries should be marked “heads,” and the rest “tails.”
For instance, if we have a fair die and a fair coin at our disposal, we may cook
up some rule to assign “heads” or “tails” to each combination of results:
⎛1⎞
6
⎜1⎟
⎜6⎟
⎜1⎟
⎜6⎟ 1 1
⎜ ⎟⊗
2 2
⎜1⎟
⎜6⎟
⎜1⎟
⎝6⎠
1
6

⎛ 1
12
⎜ 1
⎜ 12
⎜ 1
⎜ 12
=⎜
⎜ 1
⎜ 12
⎜ 1
⎝ 12
1
12

⎞
⎛
1 ⎞
H T
12
1 ⎟
⎜H T ⎟
⎟
⎜
12 ⎟
⎟
⎜
⎟
1 ⎟
⎟
⎜
T
H
12 ⎟
⎟
⎜
⎟
1 ⎟ −→ ⎜
H
T
⎟
⎜
⎟
12
⎟
⎜
⎟
1 ⎠
⎝
T H⎠
12
1
T H
12

(4)

If we want to calculate the probability of heads, we can substitute 1 for H and
0 for T in the last matrix and evaluate

Robust Coin Flipping

⎞
10
⎜1 0⎟
⎟
⎜
⎜0 1⎟
⎟
⎜
⎜1 0⎟
⎟
⎜
⎝0 1⎠
01

177

⎛
1 1 1 1 1 1
6 6 6 6 6 6

1
2
1
2

=

1
.
2

(5)

This framework gives an easy way to check if the algorithm is robust in the senseof Yao. If one of the random sources is miscalibrated (maybe the die is a little
uneven), we may see what happens to the probability of heads:
⎞
⎛
10
⎜1 0⎟
⎟
⎜
 1 1 1 1 1 1 ⎜ 0 1 ⎟ 12
1
⎟
⎜
(6)
= .
12 10 6 4 15 3 ⎜ 1 0 ⎟
1
2
⎟ 2
⎜
⎝0 1⎠
01
It’s unaﬀected! In fact, deﬁning
⎞
10
⎜1 0⎟
⎟
⎜
⎜ 0 1 ⎟ (2) ⎟A x(1) , x(2) = x(1) ⎜,⎜1 0⎟x
⎟
⎜
⎝0 1⎠
01


we see that letting β (1) = 16 16 16 16 16 16 and β (2) = 12 12
⎛

1
2
1
=
2

(7)

gives usA x(1) , β (2) =A β (1) , x(2)(8)

for all x(1) and x(2) of mass one. These relations express Yao’s notion of robustness; indeed, changing at most one of the distributions to some other distribution
leaves the result unaltered. As long as no two of the sources are miscalibrated,the bit is generated with probability 1/2.
If α denotes the bias of the bit, we may write the robustness condition as
A x(1) , β (2) = αJ x(1) , β (2)A β (1) , x(2) = αJ β (1) , x(2)(9)

since the β (i) both have mass one. (Here as always, J stands for the all-ones
tensor of appropriate dimensions.) These new equations hold for all x(i) , bylinearity. Subtracting, we obtain

178

G.S. Kopp and J.D. Wiltshire-Gordon

0 = (αJ − A) x(1) , β (2)0 = (αJ − A) β (1) , x(2)(10)

which says exactly that the bilinear form (αJ − A) is degenerate, i.e., that
Det(αJ − A) = 0.6(11)These conditions seem familiar: Changing the all-ones matrix J to the identity
matrix I would make α an eigenvalue for the left and right eigenvectors β (i) .
By analogy, we call α a mystery-value of the matrix A and the vectors β (i)mystery-vectors. Here’s the full deﬁnition:
Definition 6. A p-linear form A is said to have mystery-value α and corresponding mystery-vectors β (i) when, for any 1 ≤ j ≤ p,
0 = (αJ − A) β (1) , . . . , β (j−1) , x(j) , β (j+1) , . . . , β (p)for all vectors x(j) . (12)We further require that J(β (i) ) = 0.
We will see later that these conditions on (αJ − A) extend the notion of degeneracy to multilinear forms in general. This extension is captured by a generalization of the determinant—the hyperdeterminant.7 Hyperdeterminants will givemeaning to the statement Det(αJ − A) = 0, even when A is not bilinear.
This organizational theorem summarizes our eﬀorts to restate the problem
using multilinear algebra.
Theorem 7. A function from the product of several ﬁnite probability spaces tothe set {H, T } generates an α-biased bit robustly iﬀ the corresponding multilinear form has mystery-value α with the probability spaces as the accompanying
mystery-vectors.
We may now show the equivalenceof robustness and privacy more formally. Privacy requires that (αJ − A) ⊗β (i) remains zero, even if one of the distributionsin the tensor product collapses to some point mass, that is, to some basis vector.8 This condition must hold for all basis vectors, so it extends by linearity to
Yao’s robustness.
6

If the matrix (αJ −A) is not square, this equality should assert that all determinantsof maximal square submatrices vanish.
7
Hyperdeterminants were ﬁrst introduced in the 2 × 2 × 2 case by Cayley [Cay45], andwere deﬁned in full generality and studied by Gelfand, Kapranov, and Zelevinsky[GKZ94, Chapter 14].
8
That is, the simulated bit remains a “mystery” to each player, even though she cansee the output of her own random source.

Robust Coin Flipping

2.3

179

Two Players

The case p = 2 leaves us in the familiar setting of bilinear forms.
Proposition 8 (Uniqueness). Every bilinear form has at most one mysteryvalue.
Proof. Suppose α and α are both mystery-values for the matrix A with mystery
vectors β (i) and β (i) , respectively. We have four equations at our disposal, but
we will only use two:
A x(1) , β (2) = αA β (1) , x(2) = α(13)

We observe that a compromise simpliﬁes both ways:

α = A β (1) , β (2) = α ,(14)

so any two mystery-values are equal.
Corollary 9. Two players may not simulate an irrationally-biased coin.
Proof. Say the {0, 1}-matrix A has mystery-value α. Any ﬁeld automorphismσ ∈ Gal(C/Q) respects all operations of linear algebra, so σ(α) is a mystery-valueof the matrix σ(A). But the entries of A are all rational, so σ(A) = A. Indeed,σ(α) must also be a mystery-value of A itself. By the uniqueness proposition,σ(α) = α. Thus, α is in the ﬁxed ﬁeld of every automorphism over Q and cannot
be irrational.
Theorem 10. C(2) = Q ∩ [0, 1]. Two people with ﬁnite random sources canrobustly simulate only Q-random sources; indeed, they can already simulate afull-strength ﬁnite Q-random source if they have full-strength ﬁnite Q-random
sources.
Proof. The previous corollary shows that no probability generated by the source
can be irrational, since it could be used to simulate an irrationally-biased coin.
The other direction has already been shown in Corollary 3.
Proposition 11. If p people have full-strength ﬁnite Q-random sources, theymay (p − 1)-robustly simulate any ﬁnite Q-random source.
Proof. Follows from Proposition 2 just as the constructive direction of Theorem
10 does.

180

2.4

G.S. Kopp and J.D. Wiltshire-Gordon

Three or More Players: What Can’t Be Done

Even if three or more players have private ﬁnite random sources, it remains impossible to robustly simulate a transcendentally-biased coin. The proof makes
use of algebraic geometry, especially the concept of the dual of a complex projective variety. We describe these ideas brieﬂy in Appendix A. For a more thoroughintroduction, see [Har92, Lec. 14, 15, 16] or [GKZ94, Ch. 1].
Let A be a rational multilinear functional of format n1 × · · · × np (see Section
A.2), and let X be the Segre variety of the same format. Set n := n1 · · · np − 1,
the dimension of the ambient projective space where X lives. In what follows, we
prove that A has algebraic mystery-values. This is trivial when A is a multipleof J, and for convenience we exclude that case.
Proposition 12. Let A have mystery-value α with corresponding mystery-vectors
β (i) . Deﬁne β = ⊗β (i) , and let B denote the hyperplane of elements of (Pn )∗ thatyield zero when applied to β. Now (B, (αJ − A)) is in the incidence variety WX ∨(see Section A.1).
Proof. By the biduality theorem 31, the result would follow from the statement,“The hyperplane { x : (αJ − A)(x) = 0} is tangent to X at β.”(15)

But this statement is true by the partial derivatives formulation (Deﬁnition 32)
of the degeneracy of (αJ − A).
It is a standard fact (see e.g. [Mum95, p. 6]) that any variety has a stratiﬁcation
into locally closed smooth sets. The ﬁrst stratum of X ∨ is the Zariski-open set ofsmooth points of the variety. This leaves a subvariety of strictly smaller dimension, and the procedure continues inductively. Equations for the next stratum
may be found by taking derivatives and determinants.
Since X ∨ itself is deﬁned over Q, it follows that each of its strata is as well.
We conclude that there must be some subvariety S ⊆ X ∨ , deﬁned over Q, that
contains (αJ − A) as a smooth point.
Theorem 13. Any mystery-value of A must be an algebraic number.
Proof. Let A = αJ −A, and let  be the unique projective line through A and J.
Let A be some open aﬃne in (Pn )∗ containing A and J. The hyperplane B∩A is
the zero locus of some degree one regular function f on A. On ∩A, this function
will be nonzero at J (since J(β) = 0), so f is linear and not identically zero. It
follows that f (A) = 0 is the unique zero of f on , occurring with multiplicity
one. Thus, the restriction of f to the local ring of  at A is in the maximal ideal
but not its square:f = 0 ∈ m /m2 = TA∗  ()where m denotes the maximal ideal in O,A . (16)On the other hand, Proposition 12 shows that (B, A ) ∈ WX ∨ . Consequently, B
must be tangent to S, that is, f restricted to S is in the square of the maximal
ideal of the local ring of S at A :

Robust Coin Flipping

181

f = 0 ∈ mS /m2S = TA∗  (S) where mS denotes the maximal ideal in OS,A . (17)The function f must be zero in the cotangent space of the intersection S ∩ since the inclusion S ∩  → S induces a surjectionTA∗  (S)  TA∗  (S ∩ ),(18)

so the corresponding surjectionTA∗  ()  TA∗  (S ∩ )

(19)must kill f . This ﬁrst space is the cotangent space of a line, hence one dimensional. But f is nonzero in the ﬁrst space, so the second space must be zero. It
follows that S ∩  is a zero dimensional variety.
Of course, [α : 1] lies in S ∩ , which is deﬁned over Q! The number α mustbe algebraic.
Therefore, the set of p-cooperative numbers is contained in Q ∩ [0, 1], and wehave established the following proposition:
Proposition 14. If several people with ﬁnite random sources simulate a private
random source for someone else, that source must take probabilities in Q.
2.5

Three Players: What Can Be Done

We prove that three players with private full-strength ﬁnite random sources
are enough to simulate any private ﬁnite Q-random source. First, we give a construction for a hypermatrix with stochastic mystery-vectors for a given algebraic
number α, but whose entries may be negative. Next, we use it to ﬁnd a nonnegative hypermatrix with mystery-value (α+r)/s for some suitable natural numbersr and s. Then, after a bit of convex geometry to “even out” this hypermatrix,
we scale and shift it back, completing the construction.
Remark 15. Our construction may easily be made algorithmic, but in practice
it gives hypermatrices that are far larger than optimal. An optimal algorithm
would need to be radically diﬀerent to take full advantage of the third person.
The heart of our construction (see Proposition 18) utilizes 2 × (n + 1) × (n + 1)
hypermatrices, but the degree of the hyperdeterminant polynomial grows much
more quickly for (near-)diagonal formats [GKZ94, Ch. 14]. We would be excited
to see a method of producing (say) small cubic hypermatrices with particular
mystery-values.
Hypermatrices with Cooperative Entries Recall that a {heads, tails}function of several ﬁnite probability spaces may be represented by a {1, 0}hypermatrix. The condition that the entries of the matrix are either 1 or 0
is inconvenient when we want to build simulations for a given algebraic bias.
Fortunately, constructing a matrix with cooperative entries will suﬃce.

182

G.S. Kopp and J.D. Wiltshire-Gordon

Lemma 16. Suppose that A is a p-dimensional hypermatrix with p-cooperative
entries in [0, 1] and stochastic mystery-vectors β (1) , . . . , β (p) for the mysteryvalue α. Then, α is p-cooperative.
Proof. Let the hypermatrix A have entries w1 , w2 , . . . , wn . Each entry wk is pcooperative, so it is the mystery-value of some p-dimensional {0, 1}-hypermatrix
(1)
(2)
(p)
Ak with associated stochastic mystery-vectors βk , βk , . . . , βk . We now build
a {0, 1}-hypermatrix A with α as a mystery-value. The hypermatrix A hasblocks corresponding to the entries of A. We replace each entry wi of A with aKronecker product:
wi becomes J1 ⊗ J2 ⊗ · · · ⊗ Ji−1 ⊗ Ai ⊗ Ji+1 ⊗ · · · ⊗ Jn .

(20)

It is easy to check that the resulting tensor A has α as a mystery-value with
(i)
(i)
(i)
corresponding mystery-vectors β (i) ⊗ β1 ⊗ β2 ⊗ · · · ⊗ βn .
Because rational numbers are 2-cooperative, this lemma applies in particular torational p-dimensional hypermatrices, for p ≥ 2. In this case and in others, theconstruction can be modiﬁed to give an A of smaller format.
Readers who have been following the analogy between mystery-values and eigenvalues will see that Lemma 16 corresponds to an analogous result for eigenvalues of matrices. Nonetheless, there are striking diﬀerences between the theories
of mystery-values and eigenvalues. For instance, we are in the midst of showingthat it is always possible to construct a nonnegative rational hypermatrix witha given nonnegative algebraic mystery-value and stochastic mystery-vectors. The
analogous statement for matrix eigenvalues is false, by the Perron-Frobenius theorem: any such algebraic number must be greater than or equal to all of its Galois
conjugates (which will also occur as eigenvalues). Encouragingly, the inverse problem for eigenvalues has been solved: Every “Perron number” may be realized asa “Perron eigenvalue” [Lin84]. Our solution to the corresponding inverse problem
for mystery-values uses diﬀerent techniques. It would be nice to see if either proof
sheds light on the other.
Constructing Hypermatrices from Matrices
Proposition 17. If λ is a real algebraic number of degree n, then there is someM ∈ Mn (Q) having λ as an eigenvalue with non-perpendicular positive left andright eigenvectors.
Proof. Let f ∈ Q[x] be the minimal polynomial for λ over Q, and let L be thecompanion matrix for f . That is, if
f (x) = xn +

n−1

k=0

ak xk for ak ∈ Q,

(21)

Robust Coin Flipping

183⎞
0 0 · · · 0 −a0⎜ 1 0 · · · 0 −a1 ⎟
⎟
⎜
⎟
⎜
(22)
L = ⎜ 0 1 · · · 0 −a2 ⎟ .
⎜ .. .. . . ..
.. ⎟⎠⎝. . . .
.
0 0 · · · 1 −an−1
The polynomial f is irreducible over Q, so it has no repeated roots in C. The
matrix L is therefore diagonalizable, with diagonal entries the roots of f . Fix abasis for which L is diagonal, with λ in the upper-left entry. In this basis, theright and left eigenvectors, v0 and w0 , corresponding to λ are zero except in theﬁrst coordinate. It follows that v0 (w0 ) = 0.
The right and left eigenvectors may now be visualized as two geometric objects:
a real hyperplane and a real vector not contained in it. It’s clear that GLn (R) acts
transitively on the space S := {(v, w) ∈ (Rn )∗ × Rn : v(w) = v0 (w0 )}. Moreover,GLn (Q) is dense in GLn (R), so the orbit of (v0 , w0 ) under the action of GLn (Q)is dense in S. The set of positive pairs in S is non-empty and open, so we may
rationally conjugate L to a basis which makes v0 and w0 positive.
⎛

then

Proposition 18. If λ is real algebraic, then there exist integers r ≥ 0, s > 0
such that (λ + r)/s ∈ C(3).
Proof. By Proposition 17, there is a rational n × n matrix M with nonperpendicular positive right and left eigenvectors v, w for the eigenvalue λ.
Rescale w so that v(w) = 1, and choose an integer q ≥ max {J(v), J(w)}. Deﬁnethe block 2 × (n + 1) × (n + 1) hypermatrix
⎛
⎞
⎜0 0
⎜
⎜0
A := ⎜
⎜ ..
⎜.
⎝
0

···

0 1 1
···
1⎟
⎟
1
⎟
⎟,
.
.. q 2 (M − I) + J ⎟
⎟
q2 M
⎠
1

(23)

where I and J are the n×n identity and all-ones matrices, respectively. Consider
A as a trilinear form, where the metacolumns correspond to the coordinates of
the ﬁrst vector, the rows the second, and the columns the third. Deﬁne the block
vectorsβ (1) = ( 1 − λ λ ) ,(24)
β (2) = ( 1 − J(v)/q | v1 /q v2 /q · · · vn /q ) , andβ (3) = ( 1 − J(w)/q | w1 /q w2 /q · · · wn /q ) .
Clearly, these are all probability vectors. It’s easy to verify that
A x(1) , β (2) , β (3) = λJ x(1) ,A β (1) , x(2) , β (3) = λJ x(2) , andA β (1) , β (2) , x(3) = λJ x(3) .

(25)

184

G.S. Kopp and J.D. Wiltshire-Gordon

Choose a nonnegative integer r large enough so that all the entries of A + rJ are
positive, and then a positive integer s so that all the entries of A := (A + rJ)/s
are between 0 and 1.
λ+r
J x(1) ,s
λ+r=J x(2) , andsλ+r=J x(3) .
sA x(1) , β (2) , β (3) =A β (1) , x(2) , β (3)A β (1) , β (2) , x(3)(26)

By Lemma 16, it follows that (λ + r)/s is 3-cooperative.
Finishing the Proof The following lemma, which we we prove later, enables
us to complete the goal of this section: to classify which private random sources
three or more people can simulate.
Lemma 19 (Approximation lemma). Let α be a p-cooperative number. Now
for any ε > 0 there exists a p-dimensional rational hypermatrix whose entries are
all within ε of α, having α as a mystery-value with stochastic mystery-vectors.
Theorem 20. C(p) = Q ∩ [0, 1] for each p ≥ 3.
Proof. Certainly 0 and 1 are 3-cooperative. Let α be an algebraic number in(0, 1). By Proposition 18, there are integers r ≥ 0, s > 0 so that (α + r)/s is
3-cooperative. Let ε := (min{α, 1 − α}) /s.
By Proposition 19, there is some three-dimensional rational hypermatrix A
whose entries are all within ε of (α + r)/s, having (α + r)/s as a mystery-value
with stochastic mystery-vectors. Then, sA − rJ is a three-dimensional rational
hypermatrix with entries between 0 and 1, having α as a mystery-value withstochastic mystery-vectors. By Lemma 16, α is 3-cooperative.
We already showed that all cooperative numbers are algebraic. Thus, for p ≥ 3,
Q ∩ [0, 1] ⊆ C(3) ⊆ C(p) ⊆ Q ∩ [0, 1],(27)

so C(p) = Q ∩ [0, 1].
In conclusion, we have the following theorem.
Theorem 21. Three or more people with ﬁnite random sources can robustly simulate only Q-random sources. Indeed, if they have full-strength ﬁnite Q-random
sources, they can already robustly simulate a full-strength ﬁnite Q-random source.
Proof of the Approximation Lemma. The proof that follows is a somewhat
lengthy “delta-epsilon” argument broken down into several smaller steps. As webelieve our construction of a hypermatrix with mystery-value α to be far from
optimal, we strive for ease of exposition rather than focusing on achieving tightbounds at each step along the way.

Robust Coin Flipping

185

Recall that a ﬁnite probability space may be usefully modeled by a positive9
vector of mass one. Let β be such a vector. We denote by #β the number ofcoordinates of β . We say β  is a reﬁnement of β when β is the image of ameasure-preserving map from β  ; that is, when the coordinates of β  may beobtained by splitting up the coordinates of β.
The following easy lemma states that any positive vector of unit mass can bereﬁned in such a way that all the coordinates are about the same size.
Lemma 22 (Refinement lemma). Let β be a positive vector of total mass 1.
For any δ > 0 there exists a reﬁnement β  of β with the property thatmin βj ≥
j

1−δ
.
#β 

(28)

Proof. Without loss of generality, assume that β1 is the smallest coordinate ofβ. Let γ = β1 δ, and let k = #β. The vector β is in the standard open k-simplex
Δk = {positive vectors of mass 1 and dimension k}.

(29)

The rational points in Δk are dense (as in any rational polytope), andU := {x ∈ Δk : (∀i) |βi − xi | < γ and β1 < x1 }is an open subset of the
So U contain a rational point simplex.
with n = ni . Thus, βi − nni  < γ and β1 < nn1 , so


 βi

 − 1 < γ ≤ γ < γ = δ .
 ni n  ni
n1
βj n
n

(30)
 n1

nk
n ,..., n,(31)

Let β  be the reﬁnement of β obtained by splitting up βi into ni equal-sizedpieces. We have #β  = n, and the claim follows from this last inequality.
Remark 23. The best general bounds on the smallest possible #β  given β andδ are not generally known, but fairly good bounds may be obtained from the multidimensional version of Dirichlet’s theorem on rational approximation, which isclassical and elementary [Dav54]. Actually calculating good simultaneous rational
approximations is a diﬃcult problem, and one wishing to make an algorithmic
version of our construction should consult the literature on multidimensional
continued fractions and Farey partitions, for example, [Lag82, NS06].
The next proposition is rather geometrical. It concerns the n × n matrix Sδ :=(1 − δ)(J/n) + δI, which is a convex combination of two maps on the standard
simplex: the averaging map and the identity map. Each vertex gets mappedalmost to the center, so the action of Sδ can be visualized as shrinking thestandard simplex around its center point. The proposition picks up where thereﬁnement lemma left oﬀ:
9

We may leave out points of mass zero.

186

G.S. Kopp and J.D. Wiltshire-Gordon

Proposition 24. If a stochastic vector β satisﬁes
min βi ≥
i

1−δ
#β

(32)

then its image under the map Sδ−1 is still stochastic.
Proof. First note that [(1 − δ) (J/#β) + δI] [(1 − 1/δ) (J/#β) + (1/δ)I] = I, so
we have an explicit form for Sδ−1 . We know that mini βi ≥ (1 − δ)/#β, so thevector


 
1−δ
1
E=
β−
J
(33)
δ
#β
is still positive. Now β = (1 − δ) (J/#β) + δE, a convex combination of two
positive vectors. The vector β has mass 1, and (J/#β) as well, so E also has
mass 1.
Now compute:Sδ−1 β = (1 − 1/δ) (J/#β) + (1/δ)I (1 − δ) (J/#β) + δE
= (1 − 1/δ)(1 − δ) + (1/δ)(1 − δ) + (1 − 1/δ)δ (J/#β) + E
= E.

(34)

This completes the proof.
The following proposition shows that applying the matrix Sδ in all argumentsof some multilinear functional forces the outputs to be close to each other.
Proposition 25. Let A be a hypermatrix of format n1 × n2 × · · · × np withentries in [0, 1], and take δ := ε/(2p). Now the matrix A deﬁned byA ⊗x(i) := A ⊗Sδ x(i)(35)

satisﬁes |A (x) − A (x )| ≤ ε for any two stochastic tensors x and x .
Proof. Let m := A (⊗(J/ni )), the mean of the entries of A. We show that forany stochastic vectors x(i) ,



 
(36)
A ⊗x(i) − m ≤ ε/2.
Since any other stochastic tensor is a convex combination of stochastic puretensors, it will follow that |A (x) − m| ≤ ε/2. Then the triangle inequality will
yield the result.
It remains to show that A applied to a stochastic pure tensor gives a value
within ε/2 of m.
A ⊗x(i) = A ⊗Sδ x(i)= A ⊗ [(1 − δ)(J/ni ) + δI] x(i)
= A ⊗ (1 − δ)(J/ni ) + δx(i) .

(37)

Robust Coin Flipping

187

Each argument of A—that is, factor in the tensor product—is a convex combination of two stochastic vectors. Expanding out by multilinearity, we get convex
combination with 2p points. Each point—let’s call the k th one yk —is an element of [0, 1] since it is some weighted average of the entries of A. This convex
μk = 1 andcombination has positive μk such that
p



A

⊗x

(i)

=

2


μk y k .

(38)

k=1

Taking the ﬁrst vector in each argument of A in (37), we see that y1 = A (⊗(J/ni ))= m, the average entry of A. Thus, the ﬁrst term in the convex combination is
μ1 y1 = (1 − δ)p m.
The inequality (1−ε/2) ≤ (1−δ)p allows us to split up the ﬁrst term. Let μ0 :=1 − ε/2 and μ1 := μ1 − μ0 ≥ 0. We have μ1 y1 = (μ0 + μ1 )y1 = (1 − ε/2)m + μ1m.
After splitting this term, the original convex combination becomes
p



A

⊗x

(i)

= (1 − ε/2)m + μ1 m +2μk y k .

(39)

k=2

Let e denote the weighted average of the terms after the ﬁrst. We may rewrite
the convex combinationA ⊗x(i) = (1 − ε/2)m + (ε/2)e.

(40)

Since m, e ∈ [0, 1],m − ε/2 ≤ (1 − ε/2)m ≤ A ⊗x(i) ≤ (1 − ε/2)m + ε/2 ≤ m + ε/2,
and




 
A ⊗x(i) − m ≤ ε/2,

(41)

(42)

so we are done.
These results are now strong enough to prove the approximation lemma 19.
Proof. The number α is p-cooperative, so it comes with some p-dimensional
nonnegative rational hypermatrix A and positive vectors β (1) , β (2) , . . . , β (p) of
mass one, satisfying (in particular) A ⊗β (i) = α. The reﬁnement lemma allows
us to assume that each β (i) satisﬁes(i)

min βj ≥j1−δ.
#β (i)(43)

If one of the β (i) fails to satisfy this hypothesis, we may replace it with thereﬁnement given by the lemma, and duplicate the corresponding slices in A tomatch.
Now, by Proposition 24, each Sδ−1 β (i) is a stochastic vector.

188

G.S. Kopp and J.D. Wiltshire-Gordon

Let A be as in Proposition 25. It will still be a rational hypermatrix if wepick ε to be rational. We knowA ⊗Sδ−1 β (i) = α.

(44)

On the other hand, any entry of the matrix A is given by evaluation at a tensor
product of basis vectors. Both α and any entry of A can be found by evaluatingA at a stochastic tensor. Thus, by Proposition 25, each entry of A is within ε
of α.
2.6

Higher-Order Robustness

We complete the proof of our main theorem.
Proposition 26. If r ≥ p/2, then p people with ﬁnite random sources may
r-robustly simulate only ﬁnite Q-random sources.
Proof. Consider an r-robust simulation. Imagine that Alice has access to halfof the random sources (say, rounded up), and Bob has access to the remaining
sources. Because Alice and Bob have access to no more than r random sources,
neither knows anything about the source being simulated. But this is precisely
the two-player case of ordinary 1-robustness, so the source being simulated isrestricted to rational probabilities.
In the constructive direction, we show the following:
Proposition 27. If r < p/2, then p people with full-strength ﬁnite Q-random
sources may r-robustly simulate a full-strength ﬁnite Q-random source.
The proof is to simulate simulations (and simulate simulations of simulations,etc.). We treat the p = 3 case of our 1-robust simulation protocol as a black box.
If a majority of the random sources put into it are reliable, the one that comesout (the simulated random source) will also be reliable. This viewpoint leads us
into a discussion of majority gates.
Definition 28. A p-ary majority gate is a logic gate that computes a booleanfunction returning 1 if a majority of its inputs are 1 and 0 if a majority of its
inputs are 0. (The output doesn’t matter when there are ties.)
Lemma 29 (Bureaucracy). A p-ary majority gate may be built by wiring together ternary majority gates.
The proof of the bureaucracy lemma is a straightforward application of theprobabilistic method, and is covered in detail in Appendix B. Now, by iterating
simulations of simulations according to the wiring provided by the bureaucracylemma, we can overcome any minority of malfunctioning sources. So the bureaucracy lemma, together with the “black box” of our three-player construction,
implies Proposition 27.
Now we’re ﬁnally ready to prove our main result. The statement here is equivalent to the ones in the abstract and in Section 1.2 but uses the language ofrobustness.

Robust Coin Flipping

189

Theorem 30. Say p people have full-strength ﬁnite random sources. If
p/2 ≤ r < p, the people may r-robustly simulate any ﬁnite Q-random sourceand nothing better; if 1 ≤ r < p/2, they may r-robustly simulate any ﬁnite
Q-random source and nothing better.
Proof. The claim simply combines Proposition 11, Proposition 26, Theorem 30,
and Proposition 27.

3

Application to Secure Multiparty Computation and
Mental Poker

We begin with the classical case: Three gentlemen wish to play poker, but they
live far away from each other, so playing with actual cards is out of the question.
They could play online poker, in which another party (the remotely hosted poker
program) acts as a dealer and moderator, keeping track of the cards in eachplayer’s hand, in the deck, etc., and giving each player exactly the information
he would receive in a physical game. But this solution require our gentlemen totrust the moderator! If they fear the moderator may favor one of them, or if theywish to keep their game and its outcome private, they need another system.
A better solution is to use secure multiparty computation. Our gentlemen
work to simulate a moderator in a way that keeps the outcomes of the moderator’s computations completely hidden from each of them. An unconditionallysecure method of playing poker (and running other games/computations) “overthe phone” has been described in [GM82].
In the classical case, the players may perform ﬁnite computations, communicate along private channels, and query full-strength ﬁnitary private random
sources. The simulated moderator has the almost same abilities as the players,
except that its private random source is limited to rational probabilities. The
work of this paper expands this to all algebraic probabilities, and shows that
one can do no better.
To see how this may be useful, think back to our poker players. They may
be preparing for a poker tournament, and they may want to simulate opponents
who employ certain betting strategies. But poker is a complicated multiplayer
game (in the sense of economic game theory), and Nash equilibria will occur at
mixed strategies with algebraic coeﬃcients.10

A

Relevant Constructions in Algebraic Geometry

Comprehensive introductions to these constructions may be found in [Har92, Lec.
14, 15, 16] and [GKZ94, Ch. 1].
10

The appearance of algebraic (but not transcendental) coeﬃcients in mixed strategies
is explained by R. J. Lipton and E. Markakis in [LM04].

190

G.S. Kopp and J.D. Wiltshire-Gordon

A.1

Tangency and Projective Duality

Let k be an algebraically closed ﬁeld of characteristic zero. (For our purposes,
it would suﬃce to take k = C, but the methods are completely general.) Let
X ⊆ Pn be a projective variety over k. A hyperplane H ∈ (Pn )∗ is (algebraically)tangent to X at a point z if every regular function on an aﬃne neighborhood ofz vanishing on H lies in the square of the maximal ideal of the local ring OX,z .
This notion of tangency agrees with geometric intuition on the set of smooth
points X sm of X. To get a more complete geometric picture, we deﬁne an incidence variety:
WX := {(z, H) : z ∈ X sm , H is tangent to X at z} ⊆ Pn × (Pn )∗ .

(45)

The bar denotes Zariski closure. Membership in WX may be thought of as extending the notion of tangency at a smooth point to include singular points “bycontinuity.”
The image of a projective variety under a regular map is Zariski closed, so theprojection of WX onto the second coordinate is a variety, called the dual variety
and denoted X ∨ .
The following theorem explains why projective duality is called “duality.” Weomit the proof; see [Har92, p. 208–209] or [GKZ94, p. 27–30].
Theorem 31 (Biduality theorem). Let X be a variety in Pn . For z ∈ Pn ,let z ∗∗ be the image under the natural isomorphism to (Pn )∗∗ . Then, (z, H) →(H, z ∗∗ ) deﬁnes an isomorphism WX ∼= WX ∨ . (Specializing to the case when(z, H) and (H, z ∗∗ are smooth points X and X ∨ , respectively, this says that H
is tangent to X at z if and only if z is tangent to X ∨ at H.) Moreover, z → z ∗∗deﬁnes an isomorphism X ∼= (X ∨ )∨ .
A.2

Segre Embeddings and Their Duals

Consider the natural map k n1 × · · · × k np → k n1 ⊗ · · · ⊗ k np = k n1 ···np givenby the tensor product. Under this map, the ﬁber of a line through the origin
is a tuple of lines through the origin. Thus, this map induces an embedding
Pn1 −1 ×· · ·×Pnp −1 → Pn1 ···np −1 . The map is known as the Segre embedding, andthe image is known as the Segre variety X of format n1 × · · · × np . It is, in otherwords, the pure tensors considered as a subvariety of all tensors, up to constantmultiples. This variety is cut out by the determinants of the 2 × 2 subblocks.
Also, it is smooth because it is isomorphic as a variety to Pn1 −1 × · · · × Pnp −1 .
When a projective variety is deﬁned over the rational numbers,11 its dual isalso deﬁned over the rationals, by construction [GKZ94, p. 14]. In particular,
the dual X ∨ of the Segre embedding is deﬁned over Q.
When the dimensions ni satisfy the “p-gon inequality”
(nj − 1) ≤(ni − 1),
(46)
i=j
11

That is, it is the zero set of a system of homogeneous rational polynomials.

Robust Coin Flipping

191

Gelfand, Kapranov, and Zelevinsky [GKZ94, p. 446] show that the dual of theSegre variety is a hypersurface. The polynomial for this hypersurface is irreducible, has integer coeﬃcients, and is known as the hyperdeterminant of format
n1 × · · · × np . It is denoted by Det. When p = 2 and n1 = n2 , the hyperdeterminant is the same as the determinant of a square matrix [GKZ94, p. 36].
Gelfand, Kapranov, and Zelevinsky provide us with two equivalent deﬁnitionsof degeneracy.
Definition 32. A p-linear form T is said to be degenerate if either of thefollowing equivalent conditions holds:– there exist nonzero vectors β (i) so that, for any 0 ≤ j ≤ p,
T β (1) , . . . , β (j−1) , x(j) , β (j+1) , . . . , β (p) = 0 for all x(j) ;(47)– there exist nonzero vectors β (i) so that T vanishes at ⊗β (i) along with every
partial derivative with respect to an entry of some β (i) :
T and

∂T
(i)

∂βj

vanish at ⊗β (i) .

(48)

The dual of the Segre variety is useful to us because it can tell whether a multilinear form is degenerate.
Theorem 33 (Gelfand, Kapranov, and Zelevinsky). For any format, thedual X ∨ of the Segre embedding is deﬁned over Q and satisﬁes, for every multilinear form T of that format,
T ∈ X∨⇐⇒

T is degenerate.

(49)

When the format satisﬁes the “p-gon inequality,” X ∨ is deﬁned by a polynomialin the entries of T with coeﬃcients in Z, called the hyperdeterminant:Det(T ) = 0

B⇐⇒

T is degenerate.

(50)

Proof of the Bureaucracy Lemma

Here, we show that a p-ary majority gate may be built out of ternary majority
gates.
Proof. We prove the existence of the majority gate by showing that a random
gate built in a certain way has a positive probability of being a majority gate.
For simplicity, we assume p is odd. The even case follows from the odd case: A(2k − 1)-ary majority gate functions as a (2k)-ary majority gate if we simply
ignore one of the inputs.
Make a balanced ternary tree of depth n out of 30 + 31 + · · · + 3n−1 ternary
majority gates, where n is to be speciﬁed later. Let S be the set of possible

192

G.S. Kopp and J.D. Wiltshire-Gordon

assignments of p colors (one for each input slot) to the 3n leaves of the tree.
Each s ∈ S deﬁnes a p-ary gate; we prove that, for n large enough, a positive
fraction of these are majority gates. Let T be the set of p-tuples of input values
with exactly p+1
2 coordinates equal to 1. For (s, t) ∈ S × T , let χ(s, t) be the bit
returned by the gate deﬁned by s on input t.
If each input of a 3-ary majority gate is chosen to be 1 with probability x,
and 0 with probability 1 − x, we may compute the probability f (x) that theresulting bit is 1:
 
 
3 2
3 3
f (x) =x (1 − x) +x = x2 (3 − 2x).
(51)
2
3Fixing the choice of t ∈ T and letting s vary uniformly, it’s as if we’re assigningp−1
1 or 0 to each leaf with probabilities p+1
2 and 2 , respectively. We have


1 
p+1
χ(s, t) = f n
,
(52)
|S|
2
s∈S

where f n denotes iterated composition. Whenever 12 < ξ ≤ 1, it’s easy to see that
> 1 − |T1 | .
f n (ξ) approaches 1 as n becomes large.12 Choose n so that f n p+1
2
Now,
 1 
1 
χ(s, t) =χ(s, t)|S||S|s∈S t∈Tt∈Ts∈S p + 1
=
fn
2
t∈T


p+1
= |T |f n2
1> |T | 1 −= |T | − 1.
(53)
|T |
This is an average over S, and it follows that there must be some particulars0 ∈ S so that the inner sum t∈T χ(s0 , t) is greater than |T | − 1. But that sum
clearly takes an integer value between 0 and |T |, so it must take the value |T |,and we have χ(s0 , t) = 1 for every t ∈ T . That is, the gate speciﬁed by s0 returns
1 whenever exactly p+1
2 of the inputs are 1. By construction, setting more inputs
to 1 will not alter this outcome, so the gate returns 1 whenever a majority of
the inputs are 1. By the symmetry between 1 and 0 in each ternary component,
the gate returns 0 whenever a majority of the inputs are 0. Thus, s0 deﬁnes ap-ary majority gate.
We illustrate a 5-ary majority gate of the type obtained in the bureaucracylemma:
12

In fact, the convergence is very fast. While we’re ignoring computational complexity
questions in this paper, more careful bookkeeping shows that this proof gives apolynomial bound (in p) on the size of the tree.

Robust Coin Flipping193

3 2 5 2 3 4 2 2 4 3 5 1 3 5 3 5 2 4 1 1 1 5 1 2 4 4 5C

Simulating Infinite Random Sources

Say Alice and Bob are both equipped with private, full-strength random sources;
they wish to simulate a private, full-strength random source for some otherplayer.
For technical reasons, we will take “full-strength random source” to mean “arandom source capable of sampling from any Haar measure.” This restriction ismostly to avoid venturing into the wilds of set theory. After all, the pathologies
available to probability spaces closely reﬂect the chosen set-theoretic axioms. We
call these restricted spaces “Haar spaces.”
Definition 34. A probability space P is a Haar space if there exists some compact topological group G, equipped with its normalized Haar measure, admitting
a measure-preserving map to P .
Remark 35. The following probability spaces are all Haar spaces: any continuous distribution on the real line; any standard probability space in the sense of
Rokhlin [Rok49]; any Borel space or Borel measure on a Polish space; any ﬁnite
probability space; arbitrary products of the above.
The following construction is an easy generalization of the classical construction
given in Proposition 2.
Proposition 36. Let G be a compact group with normalized Haar measure.
Now, p players equipped with private sources that sample from G may (p − 1)robustly simulate an source that samples from G.
Proof. We provide a direct construction. The ith player uses the Haar measure
to pick gi ∈ G at random. The output of the simulated source will be the productg1 g2 · · · gp .
It follows from the invariance of the Haar measure that any p-subset of{g1 , g2 , ..., gp , g1 g2 · · · gp }is independent! Thus, this is a (p − 1)-robust simulation.

(54)

194

G.S. Kopp and J.D. Wiltshire-Gordon

Corollary 37. If p players are equipped with private, full-strength random
sources, they may (p − 1)-robustly simulate may simulate a private, full-strength
random source for some other player.
Proof. By Proposition 36, they may simulate a private random source capableof sampling from any compact group with Haar measure. But such a random
source may also sample from all quotients of such spaces.
Corollary 38. If p players are equipped with private random sources capable ofsampling from the unit interval, they may (p − 1)-robustly simulate a random
source capable of sampling from any standard probability space—in particular,
any ﬁnite probability space.
Proof. Immediate from Proposition 36.

References[Cay45] Cayley, A.: On the theory of linear transformations. Cambridge Math. J. 4
(1845)[Dav54] Davenport, H.: Simultaneous Diophantine approximation. In: Proc. of ICM,
vol. 3, pp. 9–12 (1954)[GKZ94] Gelfand, I.M., Kapranov, M.M., Zelevinsky, A.V.: Discriminants, Resultants
and Multidimensional Determinants. Birkhäuser (1994)[GM82] Goldwasser, S., Micali, S.: Probabilistic encryption & how to play mental
poker keeping secret all partial information. In: Proc. of ACM Symp. on TOC(1982)[GMW87] Goldreich, O., Micali, S., Wigderson, A.: How to play ANY mental game.
In: Proc. of ACM Symp. on TOC, pp. 218–229. ACM Press (1987)[Har92] Harris, J.: Algebraic Geomerty: A First Course. Springer (1992)[Lag82] Lagarias, J.C.: Best simultaneously Diophantine approximations. I. growth
rates of best approximation denominators. Trans. of AMS 272(2), 545–554(1982)[Lin84] Lind, D.A.: The entropies of topological Markov shifts and a related class ofalgebraic integers. Ergodic Theory Dynam. Systems 4(2), 283–300 (1984)[LM04] Lipton, R.J., Markakis, E.: Nash equilibria Via polynomial equations. In:
Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, pp. 413–422. Springer,
Heidelberg (2004)[Mum95] Mumford, D.: Algebraic Geometry I: Complex Projective Varieties. Springer(1995)[NS06] Nogueira, A., Sevennec, B.: Multidimensional farey partitions. Indag.
Mathem. 17(3), 437–456 (2006)[Rok49] Rokhlin, V.A.: On the fundamental ideas of measure theory. Mat. Sbornik
N.S. 25(67), 107–150 (1949)[Sha79] Shamir, A.: How to share a secret. CACM 22(11), 612–613 (1979)[Yao82] Yao, A.C.: Protocols for secure computations (extended abstract). In: Proc.
of FOCS, pp. 160–164 (November 1982)