2.1. Notation and Conventions for Probabilistic Algorithms

We emphasize the number of inputs received by an algorithm as follows. If algorithm \(A\) receives only one input we write "\(A(\cdot)\)", if it receives two inputs we write \(A(\cdot,\cdot)\) and so on.

RV will stand for "random variable"; in this paper we only consider RVs that assume values in \(\{0,1\}^*\). In fact, we deal almost exclusively with random variables arising from probabilistic algorithms. (We make the natural assumption that all parties may make use of probabilistic methods.)

If \(A(\cdot)\) is a probabilistic algorithm, then for any input \(x\) the notation \(A(x)\) refers to the RV which assigns to the string \(\sigma\) the probability that \(A\), on input \(x\) outputs \(\sigma\). If \(S\) is a RV that assigns positive probability only to a single element \(e\), we denote the value \(e\) by \(S\). (For instance, if \(A(\cdot)\) is an algorithm that, on input \(x\) outputs \(x^3\), then we may write \(A(2)=8\). This is in agreement with traditional notation.)

If \(f(\cdot)\) and \(g(\cdot,\cdots)\) are probabilistic algorithms then \(f(g(\cdot,\cdots))\) is the probabilistic algorithm obtained by composing \(f\) and \(g\) (i.e. running \(f\) on \(g\)'s output). For any inputs \(x,y,\cdots\) the associated RV is denoted \(f(g(x,y,\cdots))\).

Let PA denote the set of probabilistic polynomial-time algorithms. We assume that a natural representation of these algorithms as binary strings is used.

By \(1^k\) we denote the unary representation of integer \(k\).

2.2. Game Networks and Distributed Algorithms

Let us start by briefly describing the communication networks in which games will be played. This is the standard network supporting the execution of multiparty protocols.

Informally, a game network of size \(n\) is a collection of (interacting) probabilistic polynomial-time Turing machines. Each machine has a private read-only input tape, a private write-only output tape and a private read-write work tape. All machines share a common read-only input tape and a common write-only output tape. The \(n\) machines communicate by means of \(n\cdot(n-1)\) special tapes. Machine \(i\) publicly sends messages (strings) to machine \(j\) by means of a special tape \(i \rightarrow j\) on which only \(i\) can write and that all other machines can read. There is a common clock whose pulses define time intervals \(1,2,\dots\). Messages are sent at the beginning of a time interval and are received within the same time interval. We stress, though, that our result is largely independent from the specific communication mechanism, and also holds for "less equipped" communication networks.¹

That makes this network synchronous, authenticated, non-secret, and with no broadcast channel.

A probabilistic distributed algorithm \(S\) running in a game network of size \(n\) is a sequence of programs \(S=(S_1,\dots,S_n)\), where \(S_i\) is the program of the \(i\)th Turing machine in the network. We denote by PDA the class of all probabilistic polynomial-time distributed algorithms.

Let \(S\in\)PDA run in a game network of size \(n\) with common input \(CI\) and (respective) private inputs \(x_1,\dots,x_n\). Then \(HS(x_1,\dots,x_n,CI)\) denotes the RV consisting of the public history that is the sequence of all messages sent in an execution of \(S\); \(HS_i(x_1,\dots,x_n,CI)\) denotes the RV consisting of the internal configurations of machine \(i\), that is the sequence of the internal configurations of machine \(i\) in an execution of \(S\); for \(T\subset \{1,\dots,n\}\), \(HS_T(x_1,\dots,x_n)\) denotes the vector of the private histories of the members of \(T\) in an execution of \(S\); and \(OS_i(x_1,\dots,x_n,CI)\) denotes the RV consisting of the private output of machine \(i\) in an execution of \(S\).

2.3. Adversaries

We consider two interesting types of adversaries (faulty machines) in a game network: passive ones (a new notion) and malicious ones (a more standard notion).

A passive adversary is a machine that may compute more than required by its prescribed program, but the messages it sends and what it outputs are in accordance to its original program. (Passive adversaries may be thought of as machines who only try to violate the privacy constraint. They keep on running their prescribed programs correctly, but also run, "on the side", their favorite polynomial time program to try to compute more than their due share of knowledge. In an election protocol, a passive adversary may be someone who respects the majority's opinion—and thus does not want to corrupt the tally—and yet wants to discover who voted for whom.)

A malicious adversary is, instead, a machine that deviates from its prescribed program in any possible action. That is, we allow the program of such a machine to be replaced by any fixed probabilistic polynomial-time program. (Malicious adversaries not only have a better change of disrupting the privacy constraint, but could also make the outcome of a Tm-game vastly different than in an ideal run with a trusted party.)

For more on both passive and malicious adversaries, see our tutorial chapter on Adversaries, or look in the research section under the Passive and Active Adversaries tags, or under the general Adversaries tag.

We allow machines in a game network to become adversarial in a dynamic fashion, during the execution of a protocol. We also allow adversarial machines (of either type) to undetectedly cooperate. Adversarial machines are not allowed, however, to monitor the private tapes or the internal state of good machines.

We believe the malicious-adversary scenario to be the most adversarial among all the natural scenarios in which cryptography may help.

Later, the idea of an external adversary who corrupts parties adaptively during the protocol is proposed, and it is a more adversarial problem which cryptography can solve

Jumping ahead, we will show that all Tm-games are playable with any number of passive adversaries or with \(\lt\frac{n}{2}\) malicious adversaries.

Keep in mind that this is operating under the assumption that adversaries run in PPT, and therefore only offers protection in the cryptographic sense. In an information theoretic setting, only up to \(\frac{n}{3}\) parties can be malicious, as shown by Chaum, Crépeau, and Damgård the next year.

2.4. Indistinguishability of Random Variables

Throughout this paper, we will only consider families of RVs \(U=\{U_k\}\) where the parameter \(k\) ranges in the natural numbers. Let \(U=\{U_k\}\) and \(V=\{V_k\}\) be two families of RVs. The following notion of computational indistinguishability expresses the fact that, when the length of \(k\) increases, \(U_k\) becomes "replaceable" by \(V_k\), in the following sense. A random sample is selected either from \(U\), or from \(V\), and it is handed to a "judge". After studying the sample, the judge will proclaim his verdict: 0 or 1. (We may interpret 0 as the judge's decision that that the sample came from \(U_k\); 1 as the decision that the sample came from \(V_k\).) It is then natural to say that \(U_k\) becomes "replaceable" by \(V_k\) for \(k\) large enough if, when \(k\) increases, the verdict of any computationally bounded judge becomes "meaningless", that is essentially uncorrelated to which of the two distributions the sample came from.

To formalize the notion of computational indistinguishability we make use of nonuniformity. Thus, our "judge", rather than polynomial time Turing machine, will be a poly-size family of circuits. That is a family \(C=\{C_k\}\) of Boolean circuits \(C_k\) with one Boolean output such that, for some constants \(e,d\gt0\), all \(C_k\in C\) have at most \(k^e\) gates and \(k^d\) Boolean inputs. In order to feed samples from our probability distributions to such circuits, we will consider only poly-bounded families of RVs. That is families \(U=\{U_k\}\) such that, for some constant \(e\gt0\), all RV \(U_k\in U\) assigns positive probability only to strings whose length is exactly \(k^e\). If \(U=\{U_k\}\) is a poly-bounded family of RVs and \(C=\{C_k\}\) a poly-bounded sequence of circuits, we denote by \(P(U,C,k)\) the probability that \(C_k\) outputs 1 on input a random string from \(U_k\). (Here we assume that the length of the strings that are assigned positive probability by \(U_k\) equals the number of Boolean inputs of \(C_k\).)

Two poly-bounded families of RV's are computationally indistinguishable if, for all poly-size families of circuits \(C\), for all constants \(f\gt0\) and all sufficiently large \(k\in N\),

$$|P(U,C,k)-P(V,C,k)|<k^{-f}$$

Simply put, the probability of being correct on an input approaches the probability of being incorrect up to a negligible distance.

This notion was already used by Goldwasser and Micali¹ in the context of encryption, and by Yao² in the context of pseudo-random generation. For other notions of indistinguishability and further discussion see 3.

Remark 1 - Let us point out the robustness of the above definition. In this definition, we are handing out computationally bounded "judge" only samples of size 1. This, however, is not restrictive. It should be noticed that the two families of RVs \(\{U_k\}\) and \(\{V_k\}\) are computationally indistinguishable with respect to samples of size 1 if and only if they are computationally indistinguishable with respect to samples whose size is bounded by a fixed polynomial in \(k\).

At a first glance enforcing both correctness and privacy constraints of a Tm-game appears easy only for special cases of \(M\), say the ones computing a constant function. Nonetheless,

If trapdoor functions exist, there exists a Tm-game solver for passive adversaries.

In this extended abstract we limit ourselves to give a few indications, in an informal manner, about the proof of the above theorem.

Nonetheless, they give an excellent summary of how to build up to their main theorem, by presenting their building blocks one by one.

4.1. A New and General Oblivious Transfer Protocol

In 4, Rabin proposes the beautiful notion of an oblivious transfer. This is a probabilistic polynomial-time algorithm that allows A(lice), who knows the prime factorization of an integer \(n\), to send it to B(ob), who knows just \(n\), so that B will receive \(n\)'s factorization with probability ½ and A does not know whether or not B received it. Clearly, Rabin's notion of an OT supposes that factoring is computationally hard. Under this assumption, he proposed a protocol that, if A and B are allowed to be at most passive adversaries, correctly implements an OT. This protocol, however, may not work (i.e. no longer possesses a proof of correctness) if A and B are allowed to be malicious. Using the interactive proof-systems of 1, Fischer, Micali, Rackoff, and Wittenberg found⁵ a protocol that correctly implements OT under the simple (and in this context minimal) assumption that factoring is hard. Rabin's OT has proved to be a very fruitful notion, as exemplified by various applications proposed by Blum.⁶

A more general and useful notion of OT has been proposed by Even, Goldreich, and Lempel⁷, the one-out-of-two OT. In their framework, A has two messages, \(m_0\) and \(m_1\). By using a cryptosystem \(E\) she computes \(\sigma_0=E(m_0)\) and \(\sigma_1=E(m_1)\) and sends \(\sigma_0, \sigma_1\) to B. B chooses one of these encryptions, \(\sigma_i\). A one-out-of-two OT allows B to read the corresponding message \(m_i\), while A will not know which message B has read (whenever \(m_0\neq m_1\)). This notion achieves the right level of generality and is crucial to what follows. Even, Goldreich, and Lempel also proposed the first implementation of a one-out-of-two OT using public-key cryptosystems. Their protocol has the merit of having freed the implementation of an oblivious transfer from the algebraic setting to which it appeared to be confined. Their protocol, though, requires a quite strong set of assumptions even when the adversaries are only passive.

Below, we contribute a new protocol that correctly implements a one-out-of-two OT in presence of passive adversaries. The existence of trapdoor permutations suffices to prove the correctness of our protocol.

4.2. Strengthening Yao's Combined Oblivious Transfer

In 12, Yao presented a protocol that we call combined oblivious transfer (COT). The protocol involves two parties A and B, respectively owning private inputs \(a\) and \(b\) and any chosen function \(g\). It possesses the following property: upon termination, A computes \(g(a,b)\), while B has no idea of what A has computed. If we think of \(a\) and \(b\) as secrets, B appears to be obliviously transferring a prescribed combination of his and A's secret to A. Yao implemented COT based on the assumption that factoring is hard, (which yields, as shown by 6) a particular trapdoor permutation. We strengthen his result by showing that COT can be correctly implemented based on any trapdoor permutation. We do this by using the one-out-of-two OT of section 4.1 within Yao's scheme. Let us consider first the case where \(a\) and \(b\) are bits and \(g\) is the Boolean \(AND\). Consider figure 1.

Here \(E_1,\dots,E_6\) are independently selected encryption algorithms, respectively having decryption keys \(D_1,\dots,D_6\). \(E_1\) and \(E_2\) label the first input-wire, \(E_3\) and \(E_4\) the second input-wire, and \(E_5\) and \(E_6\) the output-wire. Each row in the gate is formed by the encryption of two strings. \(c\) and \(d\) are two randomly selected strings whose bit-by-bit exclusive-or equals \(D_5\). \(p\) and \(q\) are two randomly selected strings whose XOR equals \(D_6\); so are \(s\) and \(t\); so are \(u\) and \(v\). The 4 rows have been put in the gate in random order. \(E_1E_2\) and \(E_5E_6\) are publicly labelled by complementary bits. \(E_3\) and \(E_4\) are each secretly labelled by a bit; more precisely, \(E_3\) is SECRETLY labelled 0 with probability ½ and \(E_4\) is labelled with the complement of \(E_3\)'s bit. (This secrecy is pictorially indicated by drawing \(E_3\) and \(E_4\)'s bits by a dotted line.) Define the value of a wire to be 0 (1) if one ONLY possesses the decoding algorithm of encryption algorithm labelled 0 (1). Then figure 1 is an and-gate. For instance, assume that both the input-wires have value 0. That is, one possesses only \(D_1\) and \(D_4\). Then one is able to decrypt both entries only in the third row. By taking the xor of \(u\) and \(v\), one easily obtains \(D_6\), but has no idea what \(D_5\) may be. Thus the output-wire has value \(0=AND(0,0)\).

Corrections: replaced \(m\) and \(n\) with \(c\) and \(d\) to match the diagram. Also replaced "or-gate" with "and-gate".

More information about the combined oblivious transfer protocol, see the paper in which Yao presented it.

To COTransfer \(AND(a,b)\), B generates a COT AND-gate like in figure 1, keeping for himself all decoding algorithms and all the strings in the rows. Then he gives A the decoding algorithm of the second input-wire that corresponds to the value of \(b\), his own input. Notice that as the association between \(E_3,E_4\) and 0,1 is secret (and \(E_1,E_2,E_3,E_4\) enter symmetrically in the gate rows), this will not betray \(b\) at all. Now A will get either \(D_1\) or \(D_2\) according to the value of \(a\) by means of our one-out-of-two OT. Thus, B will not know which algorithm she got. At this point A can easily compute the value of the output wire. Thus, she will be the only one to know \(AND(a,b)\).

It is trivial to build a COT NOT gate. Notice that B may also keep secret the corresponding between 0,1 and \(E_5,E_6\).

Specifically, in a NOT gate, Alice has \(D_0\) (\(D_1\)) transferred to her, and they decode \(D_3\) (\(D_2\)), where \(D_0,D_2\) correspond to 0, and \(D_1,D_3\) correspond to 1. This is just as simply done within a gate (that is, by switching the order of the input(s) or outputs of a gate).

This allows the output wire to become an input wire of another gate. If the encryption algorithms of this second gate are publicly labelled 0/1 (see fig. 2), we see that A may evaluate any 2-gates function on her and B's inputs, without knowing intermediate results. Better said, B can "COTransfer" the value of any 2-gates function. By cascading this way COT AND-gates and COT NOT-gates (which are trivial to design), we can see that B can COTransfer the value of any function, provided that there is an upper bound to the length of A's and B's inputs, (else, the length of the inputs will be betrayed).

Note that the NAND gate is complete on GF(2), so we can indeed create any function.

There is soon to be an implementation of this within the site's implementation GitHub. Currently, we have a regular circuit correctly implemented; garbling will follow.

4.3. The Tm-game Solver for passive adversaries

Recall that a Tm-game solver wants to compute \(M(x_1,\dots,x_n)\) while respecting the privacy constraint. We want to use COT as a subroutine to construct a Tm-solver. This does not appear to be straightforward. For instance, if two parties \(i\) and \(j\) use COT so that \(i\) will compute \(g(x_i,x_j)\) for some function \(g\), this would already be a violation of the privacy constraint. Recall also that the Tm-game solver has to be polynomial not only in \(M\)'s running time, but also in \(n\), the number of players.

We find a way out by making special use of a lemma of Barrington's¹³ that simulates computation by composing permutations in \(S_5\), the symmetric group on 5 elements. The general picture is the following. First, transform the Turing machine \(M\) of a Tm-game to an equivalent circuit \(C\) in a standard way. The Boolean inputs of \(C\) will be \(b_1^1,\dots,b_l^1,\dots,b_1^n,\dots,b_l^n\), the bits of the \(n\), \(l\)-bit long inputs of our parties. This circuit \(C\) is then transformed to straight-line program as in 13. This straight-line program is essentially as long as \(C\) is big. In it,

For some notes on 5-permutations, see the short section at the bottom of the page.

• 0,1 are encoded by two (specially selected) 5-permutations
• the variables range in \(S_5\) and
• each instruction consists of multiplying (composing) two 5-permutations \(\sigma\) and \(\tau\), where \(\sigma\) (\(\tau\)) is either a constant, a variable, or the inverse (in \(S_5\)) of a variable.

Exactly when and how to perform each of these instructions in order to compute a program is explained by Barrington, and is outside the scope of this paper.

At the start, all parties take their private bits and encode them by a 5-permutation \(\sigma\) as in 13. Then each party divides \(\sigma\). That is, each party selects at random \(n-1\) 5-permutations \(\sigma_1,\dots,\sigma_{n-1}\) and gives the pair \((i,\sigma_i)\) to party \(i\) (keeping one pair). Each party then sets \(\sigma_n=(\sigma_1\cdots\sigma_{n-1})^{-1}\cdot\sigma\) and gives \((n,\sigma_n)\) to party \(n\). Now, inductively, assume that each variable is divided among the parties. That is, for each variable \(\sigma\), each player \(i\) possesses an index permutation pair \((x,\sigma_x)\) so that \(\prod\limits_{x=1}^n\sigma_x=\sigma\) and, given only \(n-1\) pieces, \(\sigma\) cannot be guessed better than at random. We now want to show that each instruction can be performed (i.e. that each party can compute an individual piece of the result) respecting the privacy constraint. There are essentially 3 cases.

Case 1: The instruction is of the form \(\sigma\cdot c\), where \(\sigma\) is a variable and \(c\) a constant. By induction, each party has a piece of the form \((x,\sigma_x)\). Then the party owning the piece \((n,\sigma_n)\) sets his new piece to be \((n,\sigma_n\cdot c)\) and all other parties leave their pieces untouched. It is immediately checked that the ordered product of the new pieces is \(\sigma\cdot c\) and that privacy has been preserved against \(n-1\) passive adversaries.

Case 2: The instruction is of the form \(\sigma^{-1}\cdot c\) where, again, \(\sigma\) is a variable and \(c\) a constant. It will be enough to show how to compute pieces for \(\sigma^{-1}\) respecting the privacy constraint. To do this, if a party has a piece \((x,\sigma_x)\), that party sets the new piece to be \((n-x+1, \sigma_x^{-1})\).

Case 3: the instruction is of the form \(\sigma\cdot\tau\), where both \(\sigma\) and \(\tau\) are variables. Then \(\sigma\cdot\tau=\sigma_1\cdots\sigma_n\cdot\tau_1\cdots\tau_n\), and assume for simplicity that party \(i\) possesses piece \(\sigma_i\) and \(\tau_i\). Unfortunately, party 1 cannot compute his or her piece of \(\sigma\cdot\tau\) by multiplying the two pieces known to him or her. In fact, they are \(n\) positions apart in the product and \(S_5\) is not commutative (a fact crucial in Barrington's argument). The idea will then consist of making "partial progress". That is, moving party 1's pieces closer together by "swapping" \(\sigma_n\) and \(\tau_1\). This can be correctly accomplished by giving party 1 a piece \(\tau_1'\) and party \(n\) a piece \(\sigma_n'\) so that \(\tau_1'\cdot\sigma_n'=\sigma_n\cdot\tau_1\). This way the product of the new (and newly ordered pieces) would remain \(\sigma\cdot\tau\).

So more specifically, we want party \(i\) for \(i\leq\frac{n}{2}\) to have \(\sigma_{2i-1},\sigma_{2i}\), and party \(i\) for \(i\gt\frac{n+1}{2}\) to have \(\tau_{2i-n},\tau_{2i-n+1}\). If we have an odd number of parties, party \(\frac{n+1}2\) will have pieces \(\sigma_n,\tau_1\). Since we can only swap pieces that are adjacent to each other in the overall product, we will need to perform \(\operatorname O(n^2)\) swaps. [Paragaph break not originally present.]

[Case 3 cont.:] One way of doing this would be of having party 1 and party \(n\) tell each other \(\sigma_n\) and \(\tau_1\). However, this would violate the privacy constraint with respect to a set of \(n-1\) passive adversaries. Instead, we use COT in the following way. Party \(n\) randomly selects a 5-permutation \(\rho\). Consider now the function \(g\) such that, for 5-permutations \(x\),\(y\), and \(z\), \(g(x,(y,z))=w\) where \(w\cdot z=y\cdot x\). Let now party 1 (with the role of A and input \(a=\tau_1\)) and party \(n\) (with the role of B and input \(b=(\sigma_n,\rho)\)) play COT with the function \(g\). Set \(\tau_1'=g(a,b)\) and \(\sigma_n'=\rho\). Then we have made the desired partial progress.

We should note, however, that such a function would not be particularly trivial. [Paragaph break not originally present.]

[Case 3 cont.:] In fact, not only the product of the new pieces is unaltered, but we have also respected the privacy constraint. Informally, party \(n\)'s new piece is a random 5-permutation selected by party \(n\) personally and thus can provide any information about neither party 1's old piece nor the new one; moreover the transference of \(g(a,b)\) is oblivious and thus cannot give party \(n\) any knowledge either. On the other side, party 1 is dealt a new piece \(g(\tau_1,(\sigma_n,\rho))\) and knows \(\tau_1\). However, as for all \(x\) and \(y\), \(g(x,(y,\cdot))\) is injective on \(S_5\), and \(\rho\) has been randomly and secretly selected by party \(n\), so party 1 does not get any knowledge that he or she did not possess before!

We will offer a slightly more formal outline through a simulation argument (under the assumption that the intermediate steps of the transfer are oblivious). We hope to show that party 1 can produce a transcript \(t\) for an interaction with party \(n\) that is computationally indistinguishable from an actual run of COT.

After fixing \(\sigma\), we start by noting that \(g\) is not only injective, but also surjective (easily provable since any 5-permutation is reachable from any other 5-permutation in one composition), and therefore bijective. Bijections have the property that the probability distribution of their output is also in a bijection with the probability distribution of their input; therefore, we know that the probability distribution party 1 sees on \(w\) is identical to the distribution on \(\rho\), for fixed \(\sigma\).

We know the probability distribution on \(\rho\) to be constant, since \(\rho\) was chosen randomly, so we know that \(w\)'s distribution is statistically indistinguishable from being picked uniformly at random as well. This situation is independent of \(\sigma\), since \(\sigma\) is always fixed before \(\rho\) is chosen.

With that in mind, we can show that party 1 can easily simulate a run of the protocol—not knowing \(\sigma\) or \(\rho\)—that is computationally indistinguishable from a real run. Party 1 performs the correct garbled circuit, but chooses a random decryption at each input gate for party \(n\)'s simulated 'input': since \(n\) was going to assign a decryption to his or her bits at random anyway, and party 1 cannot possibly learn the association, this is indistinguishable. Every internal gate's table can simply be assigned at random, since party 1 never learns anything about the inputs or outputs in either case. Party 1 also assigns each output gate's table randomly so that the full gate's output is any valid \(5\)-permutation; since, as we showed above, \(w\)'s probability distribution is indistinguishable from being selected uniformly at random, we get an identical distribution through party 1 selecting at random.

Since party 1's simulated transcript is indistinguishable from a real transcript at every input gate, at every internal gate, and at the output value, party 1 cannot possibly learn any information from this protocol—assuming, of course, that party 1 is only a passive adversary, since the one-out-of-two oblivious transfer protocol given is still vulnerable to malicious adversaries. [Paragaph break not originally present.]

[Case 3 cont.:] Notice also that during this "swap" we did not create any other pieces. Thus, after \(n\) "swaps" the only two pieces of party 1 will be in the first two positions in the product and party 1 can thus multiply them together. This product will be party 1's piece for the variable \(\sigma\cdot\tau\). It should be verified that the entire walk of party 1 \(\tau\)-piece towards the left preserves correctness and does not violate the privacy constraint. Essentially because a new, random piece is created at each step. This way, after \(\operatorname O(n^2)\) "swaps", and in polynomial time, all parties receive their piece of \(\sigma\cdot\tau\).

At the end of the straight-line program, for each output variable \(\gamma\), each party publicizes his own piece \((x,\gamma_x)\), the ordered product of these pieces is computed, and the output bit recovered so as to satisfy both the correctness and the privacy constraint. (A more formal argument will be given in the final paper.)

Before moving on, we should bring up an interesting special case that simplifies the problem significantly. When only dealing with two parties, it becomes much easier to drop the entire 5-permutation concept as being too computationally expensive, and instead dealing with exclusive or's.

For each of their input bits \(b_i\), both parties (\(P_1\) and \(P_2\)) transmit to the other a random bit \(r_i\), and keep for their own "share" \(r_i\oplus b_i\). As always in Boolean circuits, it suffices to demonstrate how to perform NOT, XOR, and AND.

NOT gates are trivial: one party flips their own share, and the other party does nothing.

XOR gates, too, are simple. Since XOR is commutative, the two parties can XOR any two values by XORing their own shares of those values. If the two parties are XORing \(b_1\) and \(b_2\), where \(P_1\) has shares \(b^1_1, b^1_2\) and \(P_2\) has shares \(b^2_1,b^2_2\), they are attempting to evaluate \(b_1\oplus b_2=(b_1^1\oplus b_1^2)\oplus(b_2^1\oplus b_2^2)=(b_1^1\oplus b_2^1) \oplus (b_1^2\oplus b_2^2)\). Since the two parties wish, at the end, to have one share each that XORs to the correct value, the XORs of their own shares clearly work perfectly.

AND gates are a tad more complex, since XOR does not distribute. To compute the AND of two bits \(b_1,b_2\) where, as above, party \(P_i\) possesses shares \(b^i_x\) for \(x\in\{1,2\}\), one of the parties (for concreteness, \(P_1\)) computes a truth table for the output bit \(b_3\), using the 4 possible shares of the other party and their own known shares:

Having calculated the values of \(b_3^j\) for \(j\in\{0,1,2,3\}\), party 1 chooses a new share of the output \(b_3^1\). The two parties then perform a 1-out-of-4 oblivious transfer (a simple extension of 1-out-of-2 oblivious transfer) in which party 2 receives \(b_{j,3}\oplus b_3^1\) for the \(j\) appropriate to the two shares in his or her possession.

Through this process, they can follow a similar process to the 5-permutation, multiparty version, by turning it into a series of easily computable gates. The main difference from simply using one of Yao's garbled circuits is that this process is interactive; this is an advantage and a disadvantage, notably taking away so called "constant round complexity".

There will be a tutorial section on the contrasts between Yao's garbled gate protocol and GMW's interactive construction.

6.1. Games

Essentially, a game consists of a set \(S\) of possible states, representing all possible instantaneous descriptions of the game, a set \(M\) of possible moves, describing all possible ways to change the current state of the game, a set \(\{K_1,K_2,\dots,K_n\}\) of knowledge functions, where \(K_i(\sigma)\) represents the partial information about state \(\sigma\) possessed by player \(i\), and a function \(p\), the pay-off function that, evaluated on the final state, tells the outcome of the game. Without loss of generality, the players make moves in cyclic order and the set of possible moves in any state are the same for all states. Also WLOG, the game goes on for a fixed number of moves \(m\). With little restriction we do assume that the players make use of recursive strategies for selecting their moves. (The classical model does not rule out selecting moves according to an infinite table.)

Let us now see how a game evolves using, in parenthesisas annotations, poker as an example. The game starts by having "NATURE" select an initial state \(\sigma_1\).

For poker, \(\sigma_1\) is a randomly selected permutation of the 52 cards; the first \(5n\) cards of the permutation representing the players initial hands and the remaining ones the deck.

Player 1 moves first. He does not know \(\sigma_1\)—nor does anybody else—he only knows \(K_1(\sigma_1)\), his own hand.

...the first 5 elements of permutation \(\sigma_1\).

Based solely on \(K_1(\sigma_1)\), he will select a move \(\mu\).

E.g. he changes 3 cards with the first 3 cards of the deck.

This move automatically updates the unknown current state to \(\sigma_2\).

The new state consists of the cards currently possessed by each player, the sequence of cards in the deck, and which cards were discarded by player 1. \(K_1(\sigma_2)\) consists of the new hand of player 1 and the cards he just discarded.

Now it is the turn of player 2. He also does not know the current state \(\sigma_2\), he only knows \(K_2(\sigma_2)\). Based solely on this information, he selects his move, which updates the current state, and so on. After the prescribed number of moves, the pay-off function \(p\) is evaluated at the final state to compute the result of the game.

In poker the result consists of who has won, how much he has won, and how much everyone else has individually lost.

Note that a Tm-game is indeed a game in which the initial state is empty and each player moves only once. State \(\sigma_i\) consists of the sequence of the first \(i\) moves. Each player has no knowledge about the current state and chooses his move to be the string \(x_i\), his own private input. The pay-off function \(M\) is then run on \(\sigma_n\). (Having probabilistic machines running on the final state, rather than deterministic ones, is a quite natural generalization.)

From this brief description it is immediately apparent that, by properly selecting the knowledge functions, one can enforce any desired "privacy" constraints in a game.

6.2. Playable Games

Game theory, besides an elegant formulation, also suggests to the players strategies satisfying some desired property (e.g. optimality). That is, game theory's primary concern is how TO SELECT MOVES WELL. However, and ironically!, it never addressed the question of how TO PLAY WELL. For a general \(n\)-player game, all we can say is that we need \(n+1\) parties to properly play it; the extra party being the "trusted party". The trusted party communicates privately with all players. At step \(t\), he knows the current state \(\sigma_t\) of the game. He kindly computes \(\alpha=K_{t\bmod{n}}(\sigma_t)\), communicates \(\alpha\) to player \(t\bmod{n}\), receives from him a move \(\mu\), secretly computes the new state \(S_{t+1}=\mu(S_t)\), and so on. At the end, the trusted party will evaluate the pay-off function on the final state and declare the outcome of the game. Clearly, playing with the trusted party achieves exactly the privacy constraints of the game description, and each player will get the correct outcome.

Now, the fact that, in general, an \(n\)-person game requires \(n+1\) people to be played, not only is grotesque, but also diminishes the otherwise wide applicability of game theory! In fact, in real-life situations, we may simply not have any trusted parties, whether persons or public computers. Recently, complaints have been raised about financial transactions in the stock market. The complaints were about the fact that some parties were enjoying knowledge that was considered "extra" before choosing their move, i.e. before buying stocks. Just another game, the stock market, but one in which you may desire trusting no one!

We are thus led to consider the notion of a (purely) playable game. This is an \(n\)-person game that can be implemented by the \(n\) players without invoking any trusted parties. In general, however, given the specification of a game with complicated knowledge functions, it is not at all easy to decide whether it is playable in some meaningful way. Here, among the "meaningful ways", we also include non-mathematical methods. Yet the decision may still not be easy.

Poker, for instance, has simple enough knowledge functions (i.e. privacy constraints) that makes it playable in a "physical" way. In it, we use cards with cards with equal "back" and "opaque", tables whose top does not reflect light too much, we shuffle the deck "a lot", and we hand cards "facing down". All this is satisfactory as, in our physical model (the world), we only see along straight lines. However, assume we define NEWPOKER as follows. A player may select his move not only based on his own hand, but also on the knowledge of whether, combining the current hands of all players, one may form a royal flush. NEWPOKER is certainly a game in the Von Neumann framework, but it is no longer apparent whether any physical realization of the game exists, particularly if some of the players may be cheaters.

This is what we perceive lacking in game theory: the attention to the notion of playability. At this point, a variety of good questions naturally arises:

Is there a model (physical or mathematical) which makes all games playable?

Or at least,

Does every game have a model in which it is playable?

And if not,

Should we restrict our attention to the class of playable games?

We show that the first question can be affirmatively answered in a computational complexity model.

6.3. A General Result

If any trapdoor function exists, any game is playable if more than half of the players are honest.

Essentially our result consists of a protocol for simulating the trusted party of an ideal game. That is, if more than half of the players follow our protocol, whatever a player (or a set of players of size less than \(\frac{n}{2}\)) knows at any step of the game, he would have also known in an ideal execution of the game with a trusted party. In our context, the knowledge constraints are satisfied in a computational complexity sense. Namely, any player (or collection of dishonest players), in order to compute anything more than his or her due share of the current state, should perform an exponential-time computation. Unfortunately, we cannot in this extended abstract elaborate on the relationship between general games and Tm-games, nor how to pass from solving the latter ones to solve the general case. We'll do this in the final paper.

We have yet to find the final paper. Without it, however, we can still see some connection between games and Tm-games: since the authors specifically noted in section 6.1 above that players must have a recursive strategy, it is likely that they connected their definition of general games to a recursive language, meaning that all general games would be decidable by some Turing machine. Since they defined Tm-games above to refer to any general Turing machine, that would mean that general games are a subset of Tm-games and therefore Theorem 2 implies Theorem 3.

6.4. A Completeness Theorem for Fault-Tolerant Computation

Our main theorem has direct impact to the field of fault-tolerant computation. This is so because protocols, when properly formalized (which we will do in the final paper), are games with partial information. Thus, as long as the majority of the players is honest, all protocols may be correctly played. Actually, slightly more strongly, the correct way to play a game can be found in a uniform manner. Namely, we exhibit a specific, efficient algorithm that, on input a protocol problem, outputs an efficient, distributed protocol for solving it.

It should be noticed that, before this, only a handful of multiparty protocol problems were given a satisfactory solution (e.g. collective coin flipping and poker over the telephone, secret exchange, voting, and a few others). Moreover the security of some of these solutions crucially depended on the "trapdoorness" of specific functions satisfying some additional, convenient property (e.g. multiplicativity). By contrast, our completeness theorem is proved based on any trapdoor function (multiplicative or not, associative or not, etc.). That is, we prove that, if public-key cryptography is possible at all, then all protocol problems are (automatically!) solvable if more than half the players are honest.