Introduction

Multiparty Unconditionally Secure Protocols is a 1988 paper by Chaum, Crépeau, and Damgård which offered the first plausibility result for protocols which are information-theoretically secure for all parties. Their work was lightly influenced by the GMW compiler, which also used secret sharing (in a cryptographic setting) to perform calculations, and more heavily influenced by a protocol published by Chaum and Damgård earlier the same year, which ensures information-theoretic security for a single party in the protocol.

This paper was foundational in the subfield of information theoretic multiparty computation. Its most important outcome is the demonstration that, for \(n\)-party computation, up to \(\left\lfloor n/3\right\rfloor\) parties can be malicious while allowing all parties to enjoy unconditional security. This bound (on this type of network) is optimal.

Goals and Results

This paper actually only cursorily addresses multiparty computation. After two years in which plausibility results for computation were heavily addressed, this research team focused more on what level of security could be hoped for in the face of adversaries. This paper—along with a similar one the next year—demonstrated how many malicious adversaries it is possible to thwart within a particular (but very common) framework of multiparty computation.

Specifically, the information theoretic security of any function is demonstrated in an authenticated secrecy network, with or without a broadcast channel, in the case where up to ⅓ of participants are malicious. While not the first time that these constraints on the network setting have been brought up or mentioned, it is one of the first times that this foundation network was presented so specifically, laying the groundwork for later generalizations on that setting.

Most of these results, as well as their general protocol, are based around the use of verifiable sharing schemes. The authors perform the construction of such a scheme using polynomial functions within Galois fields; notes explaining the key concepts relating to Galois fields and polynomials within them can be found at the bottom of the page. Under the assumptions of their network, and under the (optimal) assumption that there are only \(\left\lfloor n/3\right\rfloor\) malicious adversaries, their sharing scheme is information theoretically secure. However, its correctness is only probabilistically guaranteed (that is, a cheater can change the output with negligible probability).

The protocol they present is simply an adaptation of the GMW construction to their particular sharing scheme.

Assumptions

The authors are quick to note that information-theoretic security is only offered under the assumption that communication between parties is information-theoretically secure in the first place. As such, we must assume the existence of networks which are authenticated, secret, and unconditionally secure.

Protocols

Single Blob Commitment Scheme

• Number of parties: Any number of parties \(n\)
• Function(s): All parties (including the committing party) receive a single 'share' of polynomial function \(f\) chosen by the committing party. The commitment is opened by the committing party broadcasting everyone's shares and calculating \(f(0)\).
• Privacy constraints: No coalition of fewer than \(\lfloor n/3 \rfloor\) parties can determine \(f(0)\) before the committing party opens the commitment.
• Cheating: The committing party cannot succeed in creating a blob which can be opened in multiple ways except by predicting at least \(2m/3\) coin tosses for some security parameter \(m\). Conversely, no malicious coalition (working against the commitment) can possibly prevent it from being created correctly; however, they can prevent it from being opened correctly (see the next protocol).
• Subprotocols: For security, this protocol uses a cut-and-choose proof as below for up to \(mn/3\) rounds.
• Bits exchanged: \(\operatorname{O}(mn^3\log n)\) where \(n\) is the number of parties and \(m\) is the security parameter on the cut-and-choose protocol.
• Runtime: \(\operatorname{O}(mn^2\log n)\) where \(n\) is the number of parties and \(m\) is the security parameter on the cut-and-choose protocol.
• Assumptions: Identical to paper's assumptions.
• Notes: Byzantine agreement was not taken into account for the above runtime/bit-exchange calculations.

• Bits exchanged: \(\operatorname{O}(n^2\log n)\) where \(n\) is the number of parties
• Runtime: \(\operatorname{O}(n\log n)\) where \(n\) is the number of parties.

Double Blob Commitment Scheme

• Number of parties: Any number of parties \(n\).
• Function(s): All parties (including the committing party) receive a single 'share' of polynomial function \(f\) chosen by the committing party, as well as a single 'share' of every other party's share. The commitment is opened by the every party broadcasting everyone's shares and calculating \(f(0)\).
• Privacy constraints: No coalition of fewer than \(\lfloor n/3 \rfloor\) parties can determine \(f(0)\) before the committing party opens the commitment.
• Cheating: The committing party cannot succeed in creating a blob which can be opened in multiple ways except by predicting at least \(2m/3\) coin tosses for some security parameter \(m\). No other party can succeed in doing the same thing with their own share of the committing party's blob with the same probability. No malicious coalition (working against the commitment) can possibly prevent it from being created correctly.
• Subprotocols: This protocol uses the above single blobs, complete with cut-and-chooses. Additionally, another \(m\) cut-and-choose procedures are used on this double blob as a whole (see below).
• Bits exchanged: \(\operatorname{O}(m^2n^4\log n)\) where \(n\) is the number of parties and \(m\) is the security parameter on the cut-and-choose protocol.
• Runtime: \(\operatorname{O}(m^2n^3\log n)\) where \(n\) is the number of parties and \(m\) is the security parameter on the cut-and-choose protocol.
• Assumptions: Identical to paper's assumptions.
• Notes: Byzantine agreement was not taken into account for the above runtime/bit-exchange calculations.

• Bits exchanged: \(\operatorname{O}(mn^4\log n)\) where \(n\) is the number of parties and \(m\) is the security parameter on the cut-and-choose protocol.
• Runtime: \(\operatorname{O}(mn^3\log n)\) where \(n\) is the number of parties and \(m\) is the security parameter on the cut-and-choose protocol.

Robust Double Blob Commitment Scheme

• Number of parties: Any number of parties \(n\).
• Function(s): All parties (including the committing party) receive a single 'share' of polynomial function \(f\) chosen by the committing party, as well as a single 'share' of every other party's share. The commitment is opened by the every party broadcasting everyone's shares and calculating \(f(0)\).
• Privacy constraints: No coalition of fewer than \(\lfloor n/3 \rfloor\) parties can determine \(f(0)\) before the committing party opens the commitment.
• Cheating: The committing party cannot succeed in creating a blob which can be opened in multiple ways except by predicting at least \(2m/3\) coin tosses for some security parameter \(m\). No other party can succeed in doing the same thing with their own share of the committing party's blob with the same probability. No malicious coalition (working against the commitment) can possibly prevent it from being created correctly. No malicious coalition can prevent the blob from being opened correctly without cheating in the double blob protocol.
• Subprotocols: This protocol uses the above double blobs and single blobs, complete with cut-and-chooses. Additionally, another cut-and-choose proof is used on this robust double blob as a whole (see below).
• Bits exchanged: \(\operatorname{O}(m^3n^5\log n)\) where \(n\) is the number of parties and \(m\) is the security parameter on the cut-and-choose protocol.
• Runtime: \(\operatorname{O}(m^3n^4\log n)\) where \(n\) is the number of parties and \(m\) is the security parameter on the cut-and-choose protocol.
• Assumptions: Identical to paper's assumptions.
• Notes: Byzantine agreement was not taken into account for the above runtime/bit-exchange calculations.

Note that this protocol was defined here, not in the original paper.

• Bits exchanged: \(\operatorname{O}(m^2n^5\log n)\) where \(n\) is the number of parties and \(m\) is the security parameter on the cut-and-choose protocol.
• Runtime: \(\operatorname{O}(m^2n^4\log n)\) where \(n\) is the number of parties and \(m\) is the security parameter on the cut-and-choose protocol.

Computing the AND of Two (Robust) Double Blobs

• Number of parties: Any number of parties \(n\).
• Function(s): All parties compute solely on the shares of the two blobs that they have. They are left with shares of a single blob representing their product (equivalently, AND).
• Privacy constraints: No coalition of fewer than \(\lfloor n/3 \rfloor\) parties can determine \(f(0)\) of the new blob before the committing party opens the commitment.
• Cheating: Parties cannot hold shares of anything other than the product of the original two shares without predicting at least \(2m/3\) coin flips.
• Subprotocols: This protocol uses robust double blobs, and a complex cut-and-choose (as below). Every participant must perform both cut-and-chooses \(m\) times.
• Bits exchanged: \(\operatorname{O}(mn^3\log n(S(m,n)+m^2n^2))\) where \(n\) is the number of parties, \(m\) is the security parameter on the cut-and-choose protocol, and \(S(m,n)\) is the number of bits needed for one party to commit to a single bit.
• Runtime: \(\operatorname{O}(mn^3\log n(T(m,n)+m^2n))\) where \(n\) is the number of parties, \(m\) is the security parameter on the cut-and-choose protocol, and \(T(m,n)\) is the runtime of the commitment scheme used.
• Assumptions: Identical to paper's assumptions.
• Notes: Byzantine agreement was, at best, included only in the commitment scheme's runtime and bit count.

We assume the existence of some commitment scheme which exchanges \(S(m,n)\) bits to commit to (and later open) one bit, and runs in \(T(m,n)\) time for one bit.

• Bits exchanged: \(\operatorname{O}(n^2\log n\cdot S(m,n))\) where \(n\) is the number of parties and \(m\) is the security parameter.
• Runtime: \(\operatorname{O}(n^2\log n\cdot T(m,n))\) where \(n\) is the number of parties and \(m\) is the security parameter.

For more information on what the constructed blobs actually are, read the section linked.

• Bits exchanged: \(\operatorname{O}(m^2n^4\log n)\) where \(n\) is the number of parties and \(m\) is the security parameter.
• Runtime: \(\operatorname{O}(m^2n^3\log n)\) where \(n\) is the number of parties and \(m\) is the security parameter.

Further Reading

For more about the GMW compiler construction, the basis on which this more secure compiler was built, read the original paper.

To see Chaum and Damgård's original construction, on which this one was built, visit their chapter on it.

A similar (and concurrent) paper by Ben-Or, Goldwasser, and Wigderson found here demonstrates the same results using a different method.

This paper is part of a series covering the completeness theorems on tolerability of adversarial structures:

1. How to Play Any Mental Game (1987): Cryptographic Security for Honest Majority, No Fault Tolerance
2. Multiparty Computation Ensuring Privacy... (1988): Information-Theoretic Security for One Party, Negligible Probability of Cheating
3. Multiparty Unconditionally Secure Protocols (1988): Information-Theoretic Security for \(2n/3\) Honest Parties, Negligible Probability of Cheating
4. Completeness Theorems for Non-Cryptographic... (1988): Information-Theoretic Security for \(2n/3\) Honest Parties, Perfectly Fault Tolerant for \(2n/3\) Honest Parties
5. Verifiable Secret Sharing and Multiparty Protocols... (1989): Information-Theoretic Security for Honest Majority, Negligible Probability of Cheating

Referencing This Paper

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

D. Chaum, C. Crépeau, I. Damgård. Multiparty Unconditionally Secure Protocols (extended abstract). Proceedings of the Twentieth Annual ACM Symposium on the Theory of Computing, pages 11-19. ACM. 1988.

Abstract

Assume \(n\) participants \(P_1,P_2,\dots,P_n\) share the knowledge of a multivariable function \(F\) and that they want to publicly compute \(z=F(x_1,x_2,\dots,x_n)\), where \(x_i\) is a secret input provided by \(P_i\). The difficulty is to simultaneously provide the secrecy of each \(x_i\) and to guarantee the correctness of the common result \(z\). Such a task has been accomplished in [1] under the assumption that trapdoor permutations exist. The result we propose in this extended abstract is that, under the assumption that each pair of participants can communicate secretly, any reasonable function can be computed if at least \(\frac{2n}{3}\) of the participants are honest and this is proved without any cryptographic assumption. Our result is based on a non-cryptographic verifiable secret-sharing protocol that we also introduce in this paper.

1. Introduction

The problem of multiparty function computation is as follows: \(n\) participants \(P_1,P_2,\dots,P_n\) sharing the knowledge of a multivariable function \(F\) want to publicly compute \(z=F(x_1,x_2,\dots,x_n)\), where \(x_i\) is a secret input provided by \(P_i\). The goal is to preserve the maximum privacy of the \(x_i\)'s and to simultaneously guarantee the correctness of the common result \(z\). Intrinsically, the value of \(z\) will reveal some information about the secret inputs. We say that input value \(x_i\) is cryptographically secure in this context if it is believed hard to determine in polynomial time more information about \(x_i\) than what is necessarily given by \(z\).

The problem of achieving secure multiparty function computation in a public key cryptographic setting, was first posed by Yao^[2]. He also asked for which functions this problem admitted a solution. The answer to these questions was found by Goldreich, Micali, and Wigderson^[1] who showed that a solution, based on the existence of trapdoor one-way permutations, exists no matter what the function is. They exhibited a "compiler" that transforms any multiparty function computation problem into a multiparty cryptographically secure protocol.

Inspired by their work, Chaum, Damgård, and Van de Graaf presented a more direct and practical solution^[3] based on a specific trapdoor function. Their protocol had the advantage that one \(x_i\) was unconditionally secure, i.e. no information at all is available about it, other than the amount released by \(z\). All these constructions rely on trapdoor one-way functions, and therefore must assume essentially that public key cryptography is possible.

A much weaker assumption is to assert the existence of authenticated secrecy channels, i.e. a way of communicating in which the identity of the sender is known (authentication) and the data transferred is revealed only to the single person it is designed for (secrecy). Such channels are very practical and can be implemented very easily: for example, this channel can be obtained by writing down messages on pieces of paper and physically handing them out to the other parties. They can also be implemented using conventional cryptography (secret key systems). Two fundamental questions remain: Which protocol problems can be solved assuming only the existence of these authenticated secrecy channels between pairs of participants, and can all parties have their secrets unconditionally secure?

2. The Model

For convenience, the number of participants will be called \(n\), which can always be written as \(n=3d+a\), where \(a=\) 1, 2, or 3. Let \(P_1,P_2,\cdots,P_n\) be the participants.

Our assumptions about at least \(2d+a\) of the participants are that:

• They do not leak secret information to other participants; and
• They send the correct messages defined by the protocol

We call a participant satisfying the above properties reliable. At the start of the protocol, it is of course not generally agreed which participants are reliable. Our basic assumptions about the communication between reliable participants \(P_A\) and \(P_B\) are that:

• When \(P_A\) sends a message to \(P_B\), nobody else can learn anything about its content;
• When \(P_B\) receives a message from \(P_A\), \(P_B\) can be certain that nobody but \(P_A\) could have sent the message; and
• Messages sent will be received in a timely manner.

Finally, we complete our model by assuming the following:

• All participants agree on the protocols to be followed; and
• Participants can determine whether messages sent to them were sent before deadlines set in the protocol.

Our protocols ensure that all reliable participants obtain the correct result. It is proved constructively in [5], under a model like ours, that a necessary and sufficient condition for all reliable participants to agree on a message—such as the result of a protocol—is that at least \(2d+a\) of the participants are reliable. Hence, our two-thirds assumption is optimal. A polynomial algorithm solving this problem is presented in [12]. Their construction allows us to obtain an efficient "broadcast" channel: a means allowing any participant to make a message known to all participants, in such a way that all reliable participants will obtain the same value of the message. (Assuming a broadcast channel, moreover, would not enable us to weaken our other requirements, but remains interesting in some other context, as explained in Section 6.)

For simplicity in the following descriptions, we use the terminology of information theory because we make the assumption that the channels are unconditionally secure. Notice however that in fact we get protocols as strong as the secrecy and authentication of the channels used. If the channels were not unconditionally secure, for example, the protocol would not be unconditionally secure for all participants but its correctness would still be guaranteed.

3. Implementing Blobs using Secret Sharing

In [13], a fundamental protocol primitive is described: the blob. The purpose of blobs is to allow a participant \(P_A\) to commit to a bit in such a way that he or she cannot later change his or her mind about the bit, but nobody else can discover it without the participant's help. The defining properties of blobs are as follows:

1. \(P_A\) can obtain blobs representing 1 and blob representing 0.
2. When presented with a blob, nobody can tell which bit it represents.
3. \(P_A\) can open blobs by showing the other participants the single bit each represents; there is no blob \(P_A\) is able to "open" both as \(0\) and as \(1\).
4. Any other participant can at will obtain blobs representing 0 and 1. Moreover, these blobs must look exactly like the blobs obtained by \(P_A\).

To implement blobs in our model, we use a variation on Shamir's secret sharing scheme^[7]. This variation was proposed by Blakley^[6], who independently discovered secret sharing schemes, and it is more efficient than Shamir's original construction.

For our purposes, the scheme may be described as follows: a polynomial \(f\) of degree at most \(d\) over \(GF(2^k)\) is chosen uniformly, where \(k\) is an integer such that \(2^k\gt n\). The secret to be shared is defined for convenience as the value of \(f\) at 0. The protocol also assigns a distinct non-zero point \(i_B\) in the field to each participant \(P_B\). The secret can now be divided among the \(n\) participants by providing each \(P_B\) with the value of \(f(i_B)\). It is not hard to see that more than \(d\) shares completely determine \(f\), and therefore the secret, while no Shannon information about the secret is revealed by any number of shares not exceeding \(d\).

Recall that \(GF(p^n)\) is the Galois field of characteristic \(p\) and degree \(n\). For a short introduction to Galois fields and their properties (along with some information about polynomials in the context of Galois fields), see the bottom of the page.

While the security is indeed clear to see, we prove its security nonetheless. To convince yourself of the information theoretic security of a blob (for anything less than \(d+1\) shares), recall that given \(d+1\) points in a polynomial of degree \(d\), we can determine the polynomial completely, e.g. through Lagrange interpolation. If we fix the first \(d\) shares \((i_1,f(i_1)),\dots,(i_d,f(i_d))\) of some unknown polynomial \(f\), and we fix the input \(i_{d+1}\) of the next share, we note that there are \(2^k\) possible next shares of the form \((i_{d+1},y\stackrel{\text{def}}{=}f(i_{d+1}))\) where \(y\in GF(2^k)\). By unisolvence theorem, we can interpolate any polynomial of degree \(d\) using any \(d+1\) points on that polynomial. By that logic, any distinct \(y\) will produce a distinct polynomial^[17], while any two polynomials of degree \(d\) sharing \(d+1\) points must be identical.

We already know that the final share has a constant probability distribution, since the polynomial was chosen uniformly at random (which, as discussed above, is an identical statement to "the \(d+1\) shares were chosen uniformly at random"). Let's prove the existence of a bijection between value of the final share \(y\) and the value of the interpolated function at \(0\), as that will nicely allow us to demonstrate their identical probability distributions. We keep the \(d\) shares and the value \(i_{d+1}\) fixed, and define the relation \(R:\;GF(2^k)\mapsto GF(2^k)\) to map the value of \(y\) to the value of \(f(0)\) (calculated after interpolation).

To prove injectivity, we must demonstrate that \(y_0=y_1\) implies \(R(y_0)=R(y_1)\). We choose any two distinct shares for \(i_{d+1}\), interpolating \(f_0\) and \(f_1\). Assume for a moment that our relation is not injective, so \(R(f_0(i_{d+1}))\neq R(f_1(i_{d+1}))\). By definition of our relation, this statement is equivalent to \(f_0(0)\neq f_1(0)\). However, we have two polynomials sharing the original \(d\) points, plus an additional shared point \((i_{d+1},y_0=y_1)\), so they must be identical (\(f_0=f_1\)). This violates our assumption that \(f_0(0)\neq f_1(0)\). Clearly, our relation is injective.

To prove surjectivity, we choose an arbitrary value in GF(\(2^k\)), \(v\), to demonstrate that there exists a \(y\) such that the interpolation to some \(f\) will satisfy \(f(0)=v\). Indeed, we simply need to interpolate polynomial \(f\) using the original \(d\) shares and new share \((0,v)\), setting \(y=f(x)\). Since \(\forall\,y\in GF(2^k)\,\exists x \text{ s.t. } R(x)=y\), our relation is surjective.

So clearly we have a bijection between \(y\) and \(f(0)\). As previously mentioned, the value of \(y\) has a constant probability distribution even given \(d\) other shares; by property of bijection, the value of \(f(0)\) must also have a constant probability distribution. We can conclude that no information could have been released by only \(d\) shares.

We generalize slightly by allowing blobs to represent any value in \(GF(2^k)\). Blobs are now readily achieved:

The above statement is important. A blob can represent any \(s\in\{0,1\}^k\), despite the definition above stating a blob only represents 1 bit (i.e. \(k=1\)).

1. To obtain a blob representing the value \(v\), participant \(P_A\) chooses uniformly a polynomial \(f\) with \(deg(f)\leq d\), such that \(f(0)=v\). \(P_A\) then calculates \(n\) shares as above and distributes one to each participant. Using the subprotocol described below, the other participants are convinced that a consistent set of shares was distributed.
2. Since the number of unreliable participants is smaller than \(d\), no collusion will gain any information in the Shannon sense about the value represented by a blob.
3. To open a blob, \(P_A\) first broadcasts what itseveryone's shares should be \((\{\cancel{i_B}\boldsymbol{(i_B,f(i_B))}\;|\;1\leq B\leq n\})\). Then each participant broadcasts a message stating whether they agree with their share that was broadcast by \(P_A\). If a participant does not agree, that participant is said to be complaining about \(P_A\). It is required that at least \(2d+a\) of the participants do not complain. By the remarks below, this condition ensures that \(P_A\) can only open a blob to reveal the single value it represents.

Correction: \(i_B\) was originally defined as only the input value used to define a single share, and did not include the output value. The correct description of a single share in its entirety—which is what should be sent to open the blob—is \((i_B,f(i_B))\).

We note here that, if a participant complains once, then that participant is assumed to be complaining for the remainder of the protocol. A less vague phrasing for the above might say that a participant who disagrees during a round of the protocol becomes a complaining participant, as opposed to simply 'performing the act of complaining' as may be (incorrectly) inferred. Complaining participants can be safely ignored for the remainder of the protocol, assuming there are not enough of them, since their actions and shares will be ignored.

4. Any participant can choose a polynomial and distribute shares of it, whence it is impossible to tell from a blob who generated it.

By distributing inconsistent shares to reliable participants, a coalition of unreliable participants could allow \(P_A\) to open a blob in two or more different ways. The following proof, which we informally call a "cut-and-choose procedure" (and is similar to the construction of [8]) enables us to remove this inconsistency. Let the original blob chosen by \(P_A\) be \(\beta\). Then the cut-and-choose works as follows:

1. \(P_A\) establishes a new independently chosen blob \(\delta\).
2. One of the other participants flips a coin and asks \(P_A\) to open \(\delta\), or to open \(\delta+\beta\), where \(\delta+\beta\) denotes the blob defined by the sum of corresponding shares of \(\delta\) and \(\beta\).

The only way for \(\beta\) to be an invalid blob is for it to be consistent with a polynomial of degree \(\gt d\). In order for \(P_A\) to hide this inconsistency during the cut-and-choose, \(P_A\) would need to make sure that the opened blob is always of degree \(\leq d\). If \(P_A\) makes it so that \(\delta\) is valid when opened, \(\delta+\beta\) must have the same terms of degree \(\gt d\) as \(\beta\) since they could not have been cancelled out by \(\delta\); if \(P_A\) wants to cancel those terms to make \(\delta+\beta\) valid, he or she must do so by making \(deg(\delta)\gt d\).

3. Steps (a) and (b) are repeated until no complaints have occurred in \(m\) consecutive rounds, or until more than \(d\) participants have complained about \(P_A\). In the first case the proof is accepted, otherwise it is rejected.

When caught in a lie—i.e. when asked to open an inconsistent blob—a malicious \(P_A\) in a coalition of size \(d\) could either try to release \(\delta\)'s that will succeed with probability ½ (try to beat step b), or choose a set of \(d+a\) reliable participants with which to stay consistent, thereby choosing a value for \(\beta\) since it can now only be opened one way.

The participants take turns in executing step (b). By assumption, this means that \(P_A\) will be unable to predict the coin flips at least \(\frac{2d+a}{n}\) of the time.

Note that the proof will always terminate: even if all unreliable participants work against an honest \(P_A\), they cannot enlarge the number of rounds by more than \(md\).

When \(\beta\) is later opened, the shares held by complaining participants are of course ignored.

If the proof is accepted, then the following holds with probability exponentially close to 1 in \(m\): all reliable participants who did not complain (of which there are at least \(d+a\)) have shares consistent with one polynomial of degree at most \(d\).

Thus, with very high probability, \(P_A\) cannot convincingly claim that her blob contains anything but the secret determined by the \(d+a\) valid shares guaranteed by the fact above, since otherwise the condition in step (iii) would be violated.

To see why this is satisfied, it suffices to consider the behavior of reliable participants, corresponding to the worst case assumption that all unreliable participants will try to help \(P_A\) by always agreeing. For any blob \(\gamma\), consider a polynomial consistent with a maximal number of shares of \(\gamma\), and let \(C(\gamma)\) be the number of remaining shares held by reliable and non-complaining participants. Thus \(C(\gamma)\) may vary over time. In other words, no matter how \(P_A\) tries to open \(\gamma\), at least \(C(\gamma)\) participants will complain. The case where \(P_A\) created \(\gamma\) correctly corresponds of course to \(C(\gamma)=0\).

In any of the rounds of the subprotocol above, it is easy to see that because the sum of \(\delta\) and \(\delta+\beta\) is just \(\beta\), \(C(\delta)+C(\delta+\beta)\geq C(\beta)\) must hold. So if at any point \(C(\beta)\gt 0\), then \(P_A\) cannot go through \(m\) rounds without complaints except by predicting roughly \(\frac{2m}{3}\) coin flips.

The above inequality is a restatement of the fact that \(P_A\) has no way of opening both \(\delta\) and \(\delta+\beta\) without at least as many inconsistencies as opening \(\beta\).

In [13], it is shown how one can construct, using only blobs, efficient minimum disclosure proofs for membership in a very large class of languages, including NP and BPP. Since we can construct blobs in our model, we can also perform all such proofs directly.

4. VSS and Fault Tolerant Blobs

When opening a blob, \(P_A\) was to broadcast the shares distributed in creating it. If \(P_A\) is trying to prove some statement using the techniques of [13], the previous section's results imply that it is in \(P_A\)'s interest to create and broadcast the shares properly. But in other cases, communication failures or a change of heart, for example, might keep \(P_A\) from ultimately broadcasting the shares. Even if the other participants were to make \(P_A\)'s shares public in efforts to open the blob without \(P_A\)'s help, they would be left with a computational problem: unreliable participants might make public false values for their shares, and finding the value represented may require searching the exponentially many subsets of shares of size \(2d+a\) for one consistent with one polynomial of degree smaller than \(d\). Even worse, if \(P_A\) was already cheating when creating the blob, the majority of complainers could be reliable. In such cases, unreliable participants could choose at the time of opening between broadcasts that would leave no unique solution for the secret or other broadcast that would yield a particular value unambiguously.

Aside from the huge (\(\binom{n}{2d+a}\)) search space of subsets, we note that the problem is quite possibly impossible to solve. If, for instance, we find we have some subset of size \(2d+a-1\) that is consistent with a polynomial of degree \(d-1\) or less, then ALL of the additional shares will describe consistent polynomials of degree \(d\) or less.

This is where the secret sharing scheme becomes insufficient and a VSS is needed. To avoid the problems mentioned above, and assist with things to be presented later, we provide for the "sharing of the shares of a blob" (as was done for similar reasons in [14]). Thus, to create a double blob \(\delta, P_A\) proceeds as follows:

1. \(P_A\) creates an ordinary blob in the same way as in the previous section. This blob is called the top level blob, and contains the secret committed to.
2. For each participant \(P_B\), the following is done: suppose \(P_A\) sent the share \(s_B\) of the original blob to \(P_B\). Then \(P_B\) creates a sub-blob, i.e. creates a blob \(\beta_B\) containing the share \(s_B\).
3. By the remarks in the previous section, all participants are now committed to their share of the top-level blob. A cut-and-choose procedure is now used to check that everybody has committed to the proper share: \(P_A\) creates a number of additional double blobs \(\delta_1,\delta_2,\cdots,\delta_t\) (for which all participants create their own sub-blobs), and according to coin flips made by other participants, either all shares of the new double blob are made public or the sum of corresponding shares of the new and the original double blob are broadcast. Thus in each round, all participants open a sub-blob of their own (either a new one or a sum) to confirm their agreement or disagreement with \(P_A\) on what was sent originally. In order for the proof to be accepted, a subset consisting of at least \(2d+a\) participants must agree with \(P_A\) in all rounds. If a participant disagrees with \(P_A\) at any point, then that participant's share and sub-blob will be ignored when the original double blob is later opened.

It is easily seen that if the proof in (3) above is accepted, then the following holds with probability exponentially close to 1 in the number of coin flips:

• all sub-blobs accepted by the cut-and-choose contain a uniquely defined share of the top-level blob; and
• all these shares are consistent with one polynomial.

To open a double blob, all participants broadcast their shares of the top level blob as well as all shares of their sub-blobs. The result of the opening is uniquely and easily determined, since in this case the effect of the sub-blobs is to prevent unreliable participants from issuing improper shares of the top level blob: if any participant cannot confirm their share by opening their sub-blob correctly, it will just be ignored.

5. Multiparty Computations

This section considers general multiparty computations. These may involve secret input from each participant, and a single output which should become known to all reliable participants.

In the first step of the protocol, all participants commit to their secret input bits by distributing shares of them to all participants. The basic idea is now to do the computation by having each participant perform a corresponding computation on the shares he or she received. There are two problems with this idea: first, we cannot trust all participants to do the correct computation. Therefore participants must be committed to their shares, so that they can prove that the protocol was followed. This suggests a structure similar to that of a double blob. Secondly, for technical reasons explained later, all reliable participants must be able to complete the computation on their shares. Thus we cannot tolerate any complaints about the shares distributed, since there may be no way to tell whether a complainer is reliable or not. This leads to the following definition of a robust double blob:

1. like a double blob, a robust double blob has a top-level blob and sub-blobs, where the top-level contains the bit committed to.
2. all sub-blobs contain valid shares of the top-level blob.

The double blob as described in the previous section clearly does not always satisfy these properties. We can, however, get robustness by using the fact that a double blob, once verified by cut-and-choose, can always be opened without the help of its creator, and even in spite of unreliable participants. First, notice that the content of a top-level blob is completely determined by the shares of the sub-blobs (called sub-shares), if these are consistent. Thus, to create a robust double blob \(\rho,\,P_A\) creates a set \(S=\{\delta_1,\delta_2,\cdots,\delta_n\}\) of double blobs, where each one is supposed to contain a share of \(\rho\) (note that the sub-blobs in \(\delta_B\) are created by \(P_B\) after receiving shares from \(P_A\)). Once each \(\delta_B\) is verified as in the previous section, it is opened to \(P_B\). Remember that this operation can be achieved without the help of \(P_A\). At this point \(P_B\) commits to the share hidden in the double blob \(\delta_B\) using a single blob \(\beta_B\). A gigantic cut-and-choose is then used over this structure to prove its correctness. Two things have to be proven about this structure:

• All double blobs in \(S\) contain shares of \(\rho\) consistent with one polynomial.
• Each \(P_B\) has committed to the same share as is contained in the double blob \(P_A\) made for him (\(Contents(\beta_B)=Contents(\delta_B)\)).

We leave it as an exercise to design a cut-and-choose procedure that will establish this fact.

We don't. The first property can be proven using a cut-and-choose technique very similar to the one used for single and double blobs; loosely, \(P_A\) creates a set of other robust double blobs \(\xi_1\dots\xi_t\) and, contingent on a coin flip, either opens \(\xi_i\) in its entirety, or opens \(\rho+\xi_i\). Some subset of \(2d+a\) participants must not complain in all \(t\) rounds. Just as when performing cut-and-choose on single blobs, \(\rho\) being inconsistent necessarily means that either \(\xi_i\) is inconsistent or \(\rho+\xi_i\) is inconsistent; if the latter, then \(\rho\) is inconsistent.

For the second, \(P_B\) creates \(t\) single blobs \(\zeta_1,\dots,\zeta_t\) and \(t\) double blobs \(\eta_1,\dots,\eta_t\) such that \(Contents(\zeta_i)=Contents(\eta_i)\). One round at a time, contingent on a coin flip, \(P_B\) either opens both \(\beta_B+\zeta_i\) and \(\delta_B+\eta_i\) or both \(\zeta_i\) and \(\eta_i\), in both cases to demonstrate their equality. Intuitively, the two pairs should only both be equal polynomials if \(P_B\) did not attempt to cheat.

Note that this protocol leaves no possibility for \(P_A\) to cheat and blame the resulting disagreement on some other participant: if less than \(d\) participants complain about \(P_A\), then a valid commitment has (with very high probability) been constructed, and otherwise it is obvious that \(P_A\) is unreliable.

When this first phase including creation of commitments for all input bits and proofs of validity is completed successfully, the protocol is fault-tolerant: there is no way the unreliable participants can stop any reliable participant from computing the result.

The computation is specified by a boolean circuit composed of XOR and AND gates. It is then clearly sufficient to be able to safely compute from two robust double blobs a new one both as the XOR of the two inputs and also as the AND.

This is why robustness was necessary: the resulting blob may not actually owned by anyone (if the blobs belong to two different participants), so the top level will be completely determined by the sub-blobs.

Computing the XOR of two double blobs is easy, based on the remarks in previous sections: all participants simply add their shares, both for the top-level blobs representing the actual bits, and for the sub-blobs. The outcome is just a new double blob representing the XOR of the inputs.

Basically, computing the AND is just as simple: the participants merely multiply their shares. But this raises some technical problems, since the computation involves polynomials of degree larger than \(d\); polynomials of this large degree will not be robust enough against unreliable participants.

Consequently, the AND is instead done in two steps:

1. All participants multiply their shares of the two top-level blobs and commit to the product using a sub-blob. They then each prove by a cut-and-choose (to be described below) that the multiplication was done correctly.

The result of step 1 is a double blob containing the AND of the two bits, but with a large degree polynomial in the top-level blob. We cannot continue the computation with this blob, since for one thing the degree would eventually grow too large for the secrets to be uniquely determined. Therefore, this degree is brought down below \(d\) as follows:

2. Each participant chooses a pair of robust double blobs constructed as in the beginning of this section, and such that the top level involves a pair of randomly chosen polynomials \((f,g)\), where \(\operatorname{deg}(f)\lt 2d, \; \operatorname{deg}(g)\lt d,\) and \(f(0)=g(0)\in\{0,1\}\). We leave as an (easy) exercise construction of a cut-and-choose for proving correctness of such a pair. When all these pairs are added, the result will be a pair still satisfying the conditions above, but such that nobody knows the common value of \(f\) and \(g\) in 0. Finally, the double blob constructed with \(f\) is XORed with the one computed in step 1, and the result is opened. If this result is 0, then the computation continues with the blob from \(g\), otherwise \(1+g\) (the complemented bit) is used.

We have now only to describe the cut-and-choose mentioned in step 1. In principle, this procedure is essentially the same as the computation protocols of [15]: the prover has committed to \(s_1,s_2,\) and \(s_3\), and claims that \(s_1s_2=s_3\). The prover then commits to a row-permuted version of the multiplication table for the field used. The other participants, responsive to their coin flips, now ask the prover either to open the entire table or to prove that one of the rows contains commitments to the tuple \((s_1,s_2,s_3)\). This is repeated to attain the desired level of certainty. Note that since the size of the field need only just exceed \(n\), only a number of messages quadratic in \(n\) are sent.

The cut-and-choose for step 2 is simple, and very similar to the cut-and-choose for robust blobs: in each round, the prover chooses double blobs \(\mu,\,\nu\) such that \(\operatorname{deg}(\mu)\lt2d\) and \(\operatorname{deg}(\nu)\lt d\), and such that they contain the same secret. We define \(\kappa,\,\lambda\) to be the robust double blobs for \(f\) and \(g\) respectively. Contingent on coin flips by the verifiers, the prover opens either \((\mu,\nu)\) or \((\mu+\kappa,\nu+\lambda)\). In both cases, the verifier ensures that the first blob has degree \(\lt2d\), the second blob has degree \(\lt d\), and that they contain equal secrets.

We call attention to the possibility of a tradeoff between vulnerability to disruption and efficiency of the protocol. The initial commitment phase could in fact be completed correctly using only ordinary double blobs, if we require that nobody complains about anybody during the initial phase. This requirement is easily seen to imply that all the double blobs constructed are (with very high probability) robust. With this method, however, it is not possible to find out who has not been following the protocol in the first phase, if complaints do occur.

6. Generalizations

The one third assumption on the number of unreliable participants is necessary to ensure that Byzantine agreement is possible. It is natural, however, to ask what can be done if we ensure this simply by assuming the existence of a broadcast channel as part of the model?

In fact, even with this assumption, it is impossible to implement unconditionally secure blobs while tolerating more than \(d\) unreliable participants. Informally, this is so, since if \(P_A\) tries to commit to some secret, then \(P_A\) must send a set of messages containing enough Shannon information to determine that secret completely. \(P_A\) cannot use the broadcast channel for this, since the secret would then become public immediately. Moreover, if there are \(U\) unreliable participants, then no subset of this size or smaller must be given enough information to determine the secret, since the set of unreliable participants is unknown. When later the participants try to determine which secret \(P_A\) is in fact committed to, the unreliable participants are free to fabricate some set of messages which they will claim \(P_A\) sent them originally. Since any subset of \(U\) messages leaves the secret completely undetermined, it is easy to construct the set of false messages such that it is consistent with the messages sent to \(U\) reliable participants. We thus have a situation where \(2U\) participants seem to agree on something, while the rest, say \(R\), participants are complaining. But if we allow \(U\gt n/3\), then \(R\leq U\), and thus there is no way of finding out whether the situation is in fact as described above, or the \(R\) participants are just unreliable ones, complaining for no good reason! Moreover, this ambiguous situation could result, even if \(P_A\) has followed the protocol. However, an extension is possible^[16] using this broadcast channel: more unreliable participants can be tolerated if we are willing to revert to a cryptographic assumption in the case where \(n/3\lt U\lt n/2\). An "Obliviously Cryptographic" multiparty computation protocol may therefore be achieved given this feature.

It is also possible to tolerate more unreliable participants, if we change the model by restricting their behavior. If we assume that no participant will ever send an incorrect message during the protocol, then two forms of behavior remain, that may cause problems in the protocol:

1. Sharing secret information with the other participants; and
2. Stopping the protocol too early.

In the following, assume that at least \(C\) participants will complete the protocol, while at most \(L\) participants will leak secrets to others.

Clearly, information about the inputs to a computation must be distributed in such a way that any subset of \(C\) participants or more can recover all inputs, since otherwise there is no guarantee that the computation can be completed. But if the inputs are to remain unconditionally protected, this means that we must have \(L\lt C\).

One can now make the simplifying assumption that the set of participants is partitioned in one subset in which participants may show both forms of unreliable behavior mentioned above, and another subset, where there is no deviation from the protocol at all. This means that \(C+L=n\), and therefore that \(L=\left\lfloor\frac{(n-1)}{2}\right\rfloor\lt C\). Hence the best a protocol can hope to do in this case is to tolerate the situation where \(L=\left\lfloor\frac{(n-1)}{2}\right\rfloor\) and \(C=n-L\). But this can easily be accomplished using our basic protocol with polynomials of degree \(L\). Because of the inequality on \(L\), multiplication of polynomials will not lead to loss of information. As usual, protection against early stopping is effective after the initial commitment phase, where double blobs are used. If a participant stops, the remaining ones can use the corresponding subshares as input to a separate instance of the basic protocol which will simulate the missing participant.

Without the assumption that \(C+L=n\), things seem to become more complicated. It is clear that as long as \(L\leq\left\lfloor\frac{(n-1)}{2}\right\rfloor\), then the solution outlined above still works, but without this condition it is not clear what happens. The method with multiplication of polynomials does not work any more, because it leads to polynomials of a degree larger than the number of available shares. Therefore the construction of a general computation protocol under these special assumptions remains an open problem.

7. Acknowledgements

We would like to thank Gilles Brassard, Ernie Brickell, Shafi Goldwasser, Jeroen van de Graaf, Silvio Micali, Michael Sacks and Avi Wigderson for the discussions about this paper and their interest in our result.