Introduction

Protocols for Secure Computations is a short 1982 research paper by Andrew Yao that is known for defining the Millionaires' Problem, and for being the first paper to pose the problem of multiparty computation. Its results were mostly foundational: only a few very general theorems were offered, all without proof, and the vast majority of the paper is spent describing (the not-then named) multiparty computation as a whole, as opposed to defining any particular problems, perspectives, or contexts.

The main exception to that indefiniteness is the basic problem and protocol he detailed, now commonly known as the Millionaires' Problem (and Protocol). Perhaps the most common illustration of multiparty computation, its simplicity and brevity make it an excellent case study into secure two-party computation (as can be seen in the tutorial page that focuses on it). While Yao mentioned other application cases, some of which were frankly even better candidates for such popularity, the Millionaires' Problem nonetheless remains the most common example of multiparty computation to date.

The significance of this particular paper to this field is difficult to overstate. Despite its shortcomings (namely, its lack of proof and its limited direct application), its focus on defining a general problem as opposed to being limited to a specific one ultimately vaulted it into the realm of influence, and most research into multiparty computation which followed it can be framed within the definitions Yao presented here.

Goals and Results

Yao's main goal was to lay the groundwork for later research by outlining the framework of a few different basic types of problems, as well as citing a few basic applications. He defined the problem of multiparty computation in terms of:

• The limitations of privacy and security constraints. Yao cited two extreme examples to display the difference. On the extreme privacy side, he gave the Millionaires' Problem as an example, in which it is assumed that no saboteurs are on the line, but in which both parties want the other to learn nothing about their own input. On the extreme security side, he cited any basic encryption/decryption scheme in which a message needs to be sent over an insecure line from one party to the other. Multiparty computation protocols can be private, secure, or both, and all in varying degrees.
• Deterministic vs. probabilistic computation. Yao mentions that both are possible, though the latter is rather obviously more difficult to prove secure, especially if the probability density of the inputs is not constant.
• Number of parties. Yao assumes the two-party case for the majority of the paper, but expands the ideas to any \(m\) parties near his conclusions. The \(m\) party case is generally more difficult to deal with due to collusions that are impossible in the two-party case; however, Yao states that it is possible to create a protocol for any \(m\) parties with any function.
• Trust, cheating, and collusion. Parties may not trust that the other parties are following the protocol correctly, and that must be built into some protocols in order to ensure that the results are still viable. Cheating (as opposed to sabotage, below) may affect correctness, privacy, or both. Collusion is a particular subset of cheating under which multiple cheaters work together. Yao states that any computable function \(f\) can be turned into a protocol with an upper-bounded probability of successful cheating.
• Sabotage and eavesdropping. Parties may not be able to communicate without interference or eavesdropping by outside parties, affecting correctness, security, or both. Yao mentions these as issues to be discussed elsewhere, and in general sabotage and eavesdropping are both dealt with by using cryptographic primitives rather than as a part of the protocol.

Yao specifically mentions, as an aside, that his theorems prove that mental poker can be played with any public-key system, a generalization of previous research.

Assumptions

Some of Yao's results are dependent on the existence of one-way functions. His Millionaires' Problem protocol, for one. Since this extended abstract only briefly explains most of his theorems, we must assume that Theorems 1-5 and 9 depend on the existence of such functions. Theorem 6 determines a lower bound, and 7 and 8 are impossibility results, so we can safely assume that they do not.

Definitions

Let \(\epsilon,\delta > 0\), and \(f(i,j)\) be a \(0-1\) valued function. Assume that initially all pairs of \((i,j)\) values are equally likely. Suppose Bob and Alice carry out the computation faithfully according to the protocol. At the end, Alice can in principle, from her computed value \(v\) of the function and the strings in her possession, compute a probability distribution of the values of \(j\); call this \(p_i(j)\). A protocol is said to satisfy the \((\epsilon,\delta)\)-privacy constraint if the following conditions are satisfied:

1. \(p_i(j)=\frac{1}{|G_i|}(1+\operatorname O(\epsilon))\) for \(j \in G_i\), and \(0\) otherwise, where \(G_i\) is the set of \(j\) for which \(f(i,j)=v\),
2. if Alice tries afterwards to perform more calculations with no more than \(O(N^k)\) evaluations of \(E\)'s and \(D\)'s, then with probability at least \(1-\delta\) she will still get the above distribution on \(j\), and
3. the above requirement is also true for Bob.

Consider an instance in the execution of a protocol. We will consider it to be a successful cheating by Alice, if Alice does not behave consistently with any value of \(i\) and yet Bob does not detect it. A successful cheating by Bob is defined similarly.

Theorems

Let \(A\) be a protocol, let \(T(A)\) denote the maximum number of bits exchanged between Alice and Bob when \(A\) is used.

For any \(\epsilon,\delta > 0\) and any function \(f\), there exists a protocol for computing \(f\) that satisfies the \((\epsilon,\delta)\)-privacy constraint.

Let \(1 > \epsilon,\delta > 0\) and \(f(i,j)\) be a \(0-1\) function. If \(f\) can be computed by a boolean circuit of size \(C(f)\), then there is a protocol \(A\) computing \(f\) satisfying the \((\epsilon,\delta)\)-privacy constraint such that \(T(A)\)\(\in\operatorname O(C(f)\log{\frac{1}{\epsilon\cdot\delta}})\).

Let \(\frac{1}{5} > \epsilon,\delta > 0\) be fixed. Let \(F_n\) be the family of 0-1 valued function \(f(i,j)\) with \(i\) and \(j\) being \(n\)-bit integers. Let \(f\) be a random element of \(F_n\), then any protocol \(A\) that computes \(f\) with \((\epsilon,\delta)\)-privacy constraint must have \(T(A)\)\(\gt2^\frac{n}{2}\) for all large \(n\).

Let \(1\gt\gamma\gt0\). Under the same assumption of Theorem 2, there exists a protocol \(A\) for computing \(f\) such that

1. \(T(A)\)\(\in\operatorname O\left(C(f)\log{\frac{1}{\epsilon\cdot\delta\cdot\gamma}}\log{\frac{1}{\gamma}}\right)\), and
2. if one participant behaves according to \(A\), the probability of a successful cheating by the other participant is at most \(\gamma\)

Let \(K'\) be defined such that the set \(\{P_i\;|\;i \in K'\}\) is the set of people who are attempting to collude with each other in order to cheat.

For any \(\epsilon,\delta,\gamma\gt0\), there exists a protocol \(A\) for computing \(f\) which satisfies the \((\epsilon,\delta)\)-private constraint and which has the property that, for any \(K' \neq \{1,…,m\}\), the probability for \(K'\) to have a successful cheating can not be more than \(\gamma\).

There exist functions \(f\) for which any protocol \(A\) satisfying the conditions in Theorem 5 must have \(T(A)\)\(\in \operatorname\Omega\left((|X_1|\cdot |X_2|\cdot\cdots\cdot|X_m|)^\frac{1}{4}\right)\).

No protocol \(A\) with finite \(T(A)\) which generates a bit with a transcendental bias \(\alpha\) can be robust.

Suppose Alice and Bob wish to exchange a pair of solutions \(x, y\) with \(\operatorname E_a(x) = 1\) and \(\operatorname E_b(y) = 1\).

Let \(A\) be any protocol for exchanging [such] secrets. Then either Alice or Bob will be able to doublecross successfully with probability at least ½.

Let \(\epsilon\gt0\) be fixed. There is a protocol \(A\) with polynomial (in \(N\)) running time which exchanges secrets \(\operatorname D_b(w)\) and \(\operatorname D_a(u)\), and under which the probability of anyone double-crossing successfully is bounded by \(\epsilon\).

Protocols

Millionaires' Protocol

• Number of parties: 2
• Function(s): Comparisons between \(x_0\) and \(x_1\) (i.e. \(\lt,\gt,\leq,\geq\)). Two honest parties will get the same output.
• Privacy constraints: Negligible probability that \(P_i\) learns more about \(x_{(1-i)}\) than offered by the computed function.
• Cheating: One malicious adversary in the protocol can change the outcome of the protocol to a value of their choosing.
• Subprotocols: A trapdoor permutation for encryption/decryption. Assumed to run in \(\operatorname O(N)\) time.
• Bits exchanged: \(\operatorname O(Nn)\) where \(N\) is the bit-length of \(i\) and \(j\), and \(n\) is their range.
• Runtime: \(\operatorname O(Nn)\), where \(n\) is the range of \(i\) and \(j\)
• Assumptions: Existence of trapdoor functions.
• Implementations: We have our own version in Java here.

Further Reading

For more about the Millionaires' Problem, see the related tutorial section.

For more about exchanging secrets as in Theorems 8 and 9, or for a deep explanation of Theorem 2, see Yao's follow-up paper How to Generate and Exchange Secrets.

Referencing This Paper

To cite this paper, simply copy and paste the below into your citation:

A.C. Yao. Protocols for Secure Computations (extended abstract). Proceedings of the 23rd Annual IEEE Symposium on the Foundations of Computer Science, pages 160-164. IEEE. 1982.

1. Introduction

Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each other's wealth. How can they carry out such a conversation?

This is a special case of the following general problem. Suppose \(m\) people wish to compute the value of a function \(f(x_1, x_2,\dots, x_m)\), which is an integer-valued function of \(m\) integer variables \(x_i\) of bounded range. Assume initially person \(P_i\) knows the value of \(x_i\) and no other \(x\)'s. Is it possible for them to compute the value of \(f\), by communicating among themselves, without unduly giving away any information about the values of their own variables? The millionaire's problem corresponds to the case when \(m = 2\) and \(f(x_1, x_2) = 1\) if \(x_1\lt x_2\), and 0 otherwise. In this paper, we will give precise formulation of this general problem and describe three ways of solving it by use of one-way functions. These results have applications to secret voting, private querying of database, oblivious negotiation, playing mental poker, etc. We will also discuss the complexity question "How many bits need to be exchanged for the computation", and describe methods to prevent participants from cheating. Finally, we study the question "What cannot be accomplished with one-way functions".

Before describing these results, we would like to put this work in perspective by first considering a unified view of secure computation in the next section.

2. A Unified View of Secure Computation

Since one-way functions were first proposed in 1976 ^[1], they have been used in two kinds of applications. The first kind is concerned with the encryption and transmission of messages to make them unreadable and unalterable for eavesdroppers and saboteurs ^[1][2][3][4]. The second kind of applications includes "mental poker"^[5], in which two players deal cards by communicating over a telephone line, and "coin flipping" ^[6], in which two mutually suspecting parties are to generate an unbiased bit. It would be desirable to have a unified framework where all these applications can be related, and where common proof techniques can be developed for proving the security of protocols. More fundamentally, such a framework is essential if we are ever to understand the intrinsic power and limitation of one-way functions. For example, without a precise model it would be hard to answer a question such as "Is it possible for three mutually suspecting parties to interactively generate a bit with bias \(\frac{1}{e}\)?"

Yao answers this question in Theorem 7, which states that transcendental biases are not achievable robustly.

In response to this need, we propose to adopt the following view. Two parties Alice and Bob, in possession of private variables \(i\) and \(j\) respectively, wish to communicate so that Alice can evaluate a function \(f(i, j)\), and Bob a function \(g(i, j)\). There may be some eavesdroppers or saboteurs on the communication line. The purpose of a protocol would be to design an algorithm for Alice and Bob to follow, such that certain security constraints (against saboteur) and privacy constraints (Alice may not wish to reveal the exact value of \(i\)) can be satisfied.

In one extreme, when the computation component is trivial, e.g. if \(f\) = constant and \(g(i, j) = i\), then we get the first kind of applications mentioned before, in which the basic concern is eavesdropping and sabotage. In the other extreme, when such external threats can be ignored, but the computation of \(f\) and \(g\) is nontrivial, then we get the problem which is to be studied in this paper. (Mental poker and coin flipping represent a stochastic version of this problem which will also be discussed.) Note that, although we have used Alice and Bob in the above description, all discussions can be extended to the case of \(m\) parties communicating.

The 'unified view of secure computation' as defined in the above two paragraphs is perhaps the most general useful definition that can be applied to the whole of multiparty computation. In the spirit of that unification, and considering this paper is the formative paper for the field, a slightly reworded version of this very definition is the one used in the tutorials and across the site in order to link specific papers and protocols to the more general problem.

It would be natural to discuss these two special cases together. However, due to length consideration, we will report here only the results corresponding to the computation-intense case with no outside saboteurs. Results on the other case will be reported elsewhere.

There is soon to be a tutorial section dealing with adversaries and saboteurs, as it is one of the most varied and well-studied aspects of cryptography.

3. Deterministic Computations

4. Probabilistic Computations

Let us consider the case with two parties Bob and Alice \((m = 2)\). Let \(V\) and \(W\) be finite sets. A function \(p\) from \(V \times W\) to the interval \([0, 1]\) is called a probability density if the sum of \(p(v,w)\) over \(v\) and \(w\) is equal to \(1\). Let \(P(V,W)\) be the set of all such probability densities.

Let \(I, J\) be finite sets of integers. Let \(F = \{f_{ij} | i \in I, j \in J\} \subseteq P(V,W)\) be a family of probability densities. Initially, Alice knows the value of \(i \in I\), and Bob knows \(j \in J\); the values of \((i, j)\) obey a certain initial probability density \(q \in P(I, J)\). They wish to send messages between them, so that at the end Alice will obtain a value \(v \in V\) and Bob a value \(w \in W\) with probability \(f_{ij}(v,w)\). The privacy constraint is that the information Alice can obtain about \(j\) and \(w\) is no more than what can be inferred from her values of \(i\) and \(v\) (plus a corresponding constraint on Bob). This statement can be made precise in terms of \(q\) and \(F\); we omit its full generality here but simply give an illustration for the special case \(q\) = constant. In this special case, the distribution \(h(w)\) that Alice can infer from the computation she has done, according to the privacy constraint, is equal to

$$\frac{1}{|J|}\sum\limits_{j\in J}\frac{f_{ij}(v,w)}{\sum\nolimits_{x\in W} f_{ij}(v,x)}$$

Keep in mind that this is the probability of \(w\) given a particular \(i\) and \(v\); Bob's equation would be the same, but with \(j\) and \(v\) instead. Since \(q\) is constant, the probability of each \(j\) is equally likely to any other, so we can simply add all \(|J|\) probabilities together and divide by \(|J|\) at the end.

For example, mental poker would correspond to the following situation: \(I = J = {0}\), \(q\) is a constant, \(V = W\) is the set of all 5-element subsets of \({1, 2,\dots, 52}\), \(f_{00}(v,w)\) is \(0\) if \(v\) and \(w\) are not disjoint and equal to a constant otherwise.

The results in Section 3 have generalizations to the probabilistic case. Basically, a reasonable probabilistic computation remains feasible when the privacy constraints are imposed. We will not give the details here.

One interesting corollary of our results is that mental poker can be played with any general public-key system. It differs from Shamir et. al's solution^[5] in that we do not require the one-way functions used to be commutative, and that we can play it with a public-key system (instead of using private keys). (A solution with a special one-way function with publicized keys for playing mental poker was known in [2], but that solution depends on the special properties of the one-way function involved.) Moreover, the present solution uses much fewer bits as the number of cards becomes greater. Suppose we have a deck of \(n\) cards, and Alice and Bob each want to draw a random card from the deck in turn. All the previously known solutions transmit \(cn\) bits of information between Bob and Alice, while our scheme only needs about \(c(\log{n})^2\) bits.

5. Generalization to \(m\)-Party Case

When \(m\) parties \(A_1,A_2,\dots,A_m\) collaborate to compute a function \(f(x_1, x_2,\dots,x_m)\), more than one parties may collude to cheat. We will show that even the most severe constraint can be met in the following sense: No matter how many participants may collude, any cheating act will be detected and identified by all the honest parties (even if as many as \(m−1\) dishonest guys try to help cover up). We now make it precise.

Remember, however, that some collusions and types of cheating are impossible to fight against: Yao is only referring to collusions and cheating which involve inconsistencies in input variables. As an example, if ten people are trying to compute the sum of their private variables securely, but nine of them collude in order to determine the tenth's private variable, the protocol will not make a difference: they need only share those nine values and follow the protocol correctly, and they will all know the tenth value as well, by subtracting from the total sum. The guarantee Yao is making is that none of those people could convince someone they did the protocol correctly if they actually used changing random numbers throughout.

Let \(V\) be the range of the function \(f(x_1, x_2,\dots,x_m)\), where \(x_i \in X_i\). For any nonempty \(K \subseteq \{1, 2,\dots,m\}\), define \(H_K = X_{t_1} \times X_{t_2} \times \cdots \times X_{t_{|K|}}\) , where \(\{t_1, t_2,\dots, t_{|K|}\} = K\). Let \(K' = \{1, 2,\dots,m\} − K\), and define \(H_{K'}\) similarly. For any \(i \in H_{K'}\) and \(v \in V\) , let \(G_i(v) \subseteq H_K\) be the set of all \(j \in H_K\) such that the (unique vector) \(x = (x_1, x_2,\dots, x_m)\), whose projection on \(H_{K'}\) and \(H_K\) equals \(i\) and \(j\) respectively, satisfies \(f(x) = v\). Let \(q_{i,v}(j) = \frac{1}{|G_i(v)|}\) for \(j \in G_i(v)\) and 0 otherwise. (If all the participants \(A_r\) with \(r \in K'\) collude to infer the probability distribution of the variable values of other participants, and if the only information available, in addition to their only variable values \(i\), is that the function \(f\) has value \(v\), then \(q_{i,v}(j)\) is the distribution they can infer.) Let \(\epsilon,\delta\gt0\). A protocol \(A\) is said to satisfy the \((\epsilon,\delta)\)-private constraint if for every nonempty \(K\), even if the participants in \(K\) are allowed to perform in private an amount of calculation polynomial in \(T(A)\), they will still infer, with probability at least \(1−\delta\), that the distribution on \(j\) is equal to \(q_{i,v}(j)(1+\operatorname O(\epsilon))\). A successful cheating by \(K'\) (with respect to a protocol \(A\)) is an instance of the execution of \(A\), in which at least one participant \(A_r\) with \(r \in K'\) behaves inconsistently with any \(x_r \in X_r\) without being detected by all the participants of \(K\).

The above paragraph is extremely dense, so let's clarify a bit. \(K\) is the set of all honest parties, while \(K'\) is the set of all dishonest parties. The \((\epsilon,\delta)\)-privacy constraint is defined by specifying that all members of \(K\) (and therefore all honest parties) are only able to infer the probability distribution \(q_{i,v}(j)(1+\operatorname O(\epsilon))\). A successful cheating is defined by specifying that all of \(K'\) together was able to trick at least one member of \(K\) into not realizing they had behaved inconsistently with at least one value of \(x\).

For any \(\epsilon,\delta,\gamma\gt0\), there exists a protocol \(A\) for computing \(f\) which satisfies the \((\epsilon,\delta)\)-private constraint and which has the property that, for any \(K' \neq \{1,\dots,m\}\), the probability for \(K'\) to have a successful cheating can not be more than \(\gamma\).

The value of \(T(A)\) in the above theorem is \(\operatorname O(|X_1|\cdot |X_2|\cdot\cdots\cdot|X_m|\cdot|V|)\), which is almost optimal in general as the next theorem shows.

There exist functions \(f\) for which any protocol \(A\) satisfying the conditions in Theorem 5 must have \(T(A)\)\(=\Omega((|X_1|\cdot |X_2|\cdot\cdots\cdot|X_m|)^\frac{1}{4})\)

We should take a second to notice that this is an unreasonably high lower bound for a lot of real world applications. As an example, if there are \(m\) parties trying to calculate \(f\) on \(n\)-digit numbers, then that leaves a lower bound of \(\operatorname\Omega(2^{\frac{nm}{4}})\).

In special cases protocols can be designed with better running time than the bound given in Theorem 5. For example, the parity function \(f(x_1, x_2,\dots, x_m)\) = \(x_1 \bigoplus x_2 \bigoplus \cdots \bigoplus x_m\) and the tally function \(f(x_1, x_2,\dots, x_m) =\) # of 1's in the \(x\)'s (the \(x\)'s are boolean variables) both have protocols satisfying Theorem 5 with running time polynomial in \(m\).

The security measure as we considered above is a strong one. For some purposes, less stringent measures would be adequate. (For example, one may only require that no subset \(K'\) be able to force the outcome of the computation to be a certain value.) Sometimes protocols with better running time can be designed under such less stringent requirements. For example, there is a protocol with running time \(\operatorname O(p(m) \log{q})\), where \(p(m)\) is a polynomial, for \(m\) parties to compute the function \(f(x_1, x_2,\dots, x_m)\) = \(x_1 +x_2 +\cdots+x_m\pmod{q}\), under a security criterion only slightly relaxed from that given in Theorem 5.

6. What Cannot Be Done?

There are security constraints that can not be achieved by any protocols. We will only mention two results here.

The first impossibility result is valid for all three models given in this paper. Suppose \(m\) people try to generate a bit with bias \(\alpha\). It is easy to see how it can be done for \(m\gt2\). For example, A generates a random unbiased bit \(\alpha_1\) and sends it to B, B generates a random \(\alpha_2\) and sends it to C, C generates a random \(\alpha_3\) and sends it to A. Now let \(\alpha = \alpha_1 + \alpha_2 + \alpha_3\), and we get an unbiased \(\alpha\) with the property that it remains unbiased even if one of the persons cheats by generating a biased bit. Let us call a protocol for generating a bit with bias \(\alpha\) robust, if the bias remains correct if somebody has cheated.

No protocol \(A\) with finite \(T(A)\) which generates a bit with a transcendental bias \(\alpha\) can be robust.

The second result is valid for the model defined in Section 3.2. Suppose Alice and Bob wish to exchange a pair of solutions \(x, y\) with \(\operatorname E_a(x) = 1\) and \(\operatorname E_b(y) = 1\). Is there a protocol such that an honest party will not be doublecrossed, i.e. swindled out of its secret without getting the secret from the other party?

Let \(A\) be any protocol for exchanging secrets. Then either Alice or Bob will be able to double-cross successfully with probability at least ½.

It is of interest to mention that a different type of exchanging secrets is possible in the same model. Suppose Alice wants to know the solution \(y\) to \(\operatorname E_b(y) = w\) and Bob wants to know the solution \(x\) to \(\operatorname E_a(x) = u\), but Bob does not know the value of \(w\) and Alice does not know \(u\). Let \(N\) be the number of bits that the encryption functions \(\operatorname E_a\) and \(\operatorname E_b\) operate on.

Let \(\epsilon\gt0\) be fixed. There is a protocol \(A\) with polynomial (in \(N\)) running time which exchanges secrets \(\operatorname D_b(w)\) and \(\operatorname D_a(u)\), and under which the probability of anyone double-crossing successfully is bounded by \(\epsilon\).

As a short summary of theorems 8 and 9, when viewed together: either Alice or Bob can double-cross the other easily assuming that they know the value they are decrypting. If they do not know the value they are decrypting, their ability to double-cross can be bounded.

Different kinds of exchanging secrets have been considered previously. Blum^[6] showed that it is possible to exchange factors of large composite numbers (a special type of secrets) with vanishing chance for cheating. Even (private communication, 1981) also devised some protocols for exchanging secrets.