Multiparty Computation

home

learn

research

build

resources

about us

Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation 1988 Michael Ben-Or Shafi Goldwasser Avi Wigderson

“[Chaum, Crépeau, and Damgård] have to allow an exponentially small error probability for both correctness and privacy (we can guarantee them with no errors).... In [their solution] the simulation is of Boolean operations while our solution allows direct simulation of arithmetic operations in large finite fields.”

Editor's Overview

Introduction

Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation is a 1988 paper by Ben-Or, Goldwasser, and Wigderson which demonstrated the bounds of (and described a protocol for) multiparty computation which is information theoretically secure. It is one of two papers in the same year which demonstrates that up to ⅓ parties can be actively malicious without affecting correctness or privacy. The other paper offers information theoretic security in a very similar manner, while this paper additionally guarantees correctness (as opposed to a negligible probability of incorrectness).

One major difference between this paper and its chronological counterpart is the type of computation performed. Chaum's construction is based around Boolean operation simulations, while this protocol uses an arithmetic circuit within a finite field. Very significantly, this finite field is not arbitrary as implied in the paper: it must be of the form $GF(p^{k\operatorname\phi(n)})$, where $n$ is the number of parties who must participate, $p$ is any prime that is not a factor of $n$ (generally the minimal prime), and $k$ is any³ positive integer. This is necessary in order to allow for the fault tolerance properties sought; more details can be found in Section 5.

Note that a true protocol specification is not given in this work; it offers completeness theorems, and uses a more general specification in order to prove its purposes. For example, no particular algorithms for the error checking or correctness is given, but its existence is sufficient to prove their claims.

Goals and Results

The authors intended to find upper bounds on what types of computation are possible in the information-theoretic model, and the bounds they found were optimal. This result is, of course, dependent on the specification of the network (which can be found in Assumptions).

Simply put, protocols can guarantee both correctness and information-theoretic security in the case when $t\lt\frac n 3$ parties are malicious. This paper additionally extends the cryptographic privacy on passive adversaries—$t\lt\frac n 2$—to information-theoretic multiparty computation. These two limits are not achievable simultaneously through the protocol presented.

The authors provided privacy using a familiar verifiable secret sharing scheme based on finite fields. Their methodology for correctness is more clever; by ensuring the VSS scheme was constructed such that it had an error correcting code (using the Discrete Fourier Transform), they reduced fault tolerance within the scheme to known algorithms for error correction.

Assumptions

This paper made a point of not relying on any cryptographic assumptions; its results are only based on the type of network, which is specified to be complete, synchronous, secret, and authenticated.

Definitions

Definition 1 - $t$-privacy

A protocol is $t$-private if any set of at most $t$ players cannot compute after the protocol more than they could have jointly compute solely from their set of privacy inputs and outputs.

Definition 2 - $t$-resiliency

A protocol is $t$-resilient if no set of $t$ or fewer players can influence the correctness of the outputs of the remaining players. For this to make sense, the function definition should be extended to specify what it is if some players neglect to give their inputs or are caught cheating (see appendix).

Theorems

Lemma 1: (Linear Functional)

For any $t,\,(t\leq n-1)$, any linear functional $$F(x_0,\dots,x_{n-1})=a_0x_0+\cdots+a_{n-1}x_{n-1},$$ where each $P_i$ has input $x_i$ and the $a_i$ are known constants, can be computed $t$-privately.

Corollary 1: (Matrix Multiplication)

Let $A$ be a constant $n\times n$ matrix, and let each $P_i$ have an input variable $x_i$. Let $X=(x_0,\dots,x_{n-1})$ and define $Y=(y_1,\dots,y_n)$ by $$Y=X\cdot A$$ then for any $t,\,(t\leq n-1)$, we can $t$-privately compute the vector $Y$ such that the only information given to $P_i$ will be the value of $Y_i$, for $i=0,\dots,n-1$.

Theorem 1:

For every (probabilistic) function $f$ and $t\lt\frac n 2$ there exists a $t$-private protocol.

Theorem 2:

There are functions for which there are no $\frac n 2$-private protocols.

Theorem 3:

For every probabilistic function and every $t\lt\frac n 3$ there exists a protocol that is both $t$-resilient and $t$-private.

Theorem 4:

There are functions for which there is no $\frac n 3$-resilient protocol.

Referencing This Paper

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

M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation. Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 1-10. ACM. 1988.

Annotated Paper (extended abstract)

Abstract

Every function of $n$ inputs can be efficiently computed by a complete network of $n$ processors in such a way that:

If no faults occur, no set of size $t\lt\frac n 2$ of players gets any additional information (other than the function value),
Even if Byzantine faults are allowed, no act of size $t\lt\frac n 3$ can either disrupt the computation or get additional information.

Furthermore, the above bounds on $t$ are tight!

1. Introduction

The rapid development of distributed systems raised the natural question of what tasks can be performed by them (especially when faults occur). A large body of literature over the past ten years addressed this question. There are two approaches to this question, depending on whether a limit on the computational power of processors is assumed or not.

The cryptographic approach, inaugurated by Diffie and Hellman^[3], assumes the players are computationally bounded, and further assumes the existence of certain (one-way) functions, that can be computed but not inverted by the player.

This simple assumption was postulated in [3] in order to achieve the basic task of secure message exchange between two of the processors, but turned out to be universal! In subsequent years, ingenious protocols based on the same assumption were given for increasingly harder tasks such as contract signing, secret exchange, joint coin flipping, voting, and playing poker. These results culminated, through the definition of zero-knowledge proofs^[8] and their existence for NP-complete problems^[6], in completeness theorems for two-party^[12] and multiparty^[7] cryptographic distributed computation. In particular the results of Goldreich, Micali, and Wigderson in [7] were the main inspiration to our work. They show that, if (non-uniform) one-way functions exist, then every (probabilistic) function of $n$ inputs can be computed by $n$ computationally bounded processors in such a way that: (1) If no faults occur, no subset of the players can compute any additional information, and (2) Even if Byzantine faults are allowed, no set of size $t\lt\frac n 2$ can either disrupt the computation or compute additional information.

The non-cryptographic (or information-theoretic) approach does not limit the computational power of the processors. Here, the notion of privacy is much stronger—for a piece of data to be unknown to a set of players it does not suffice that they cannot compute it within a certain time bound from what they know, but simply that it cannot be computed at all!

To facilitate the basic primitive of secret message exchange between a pair of players, we have secure channels. (For an excellent source of results and problems in the case no secure channels exist, see [1]). Unlike the cryptographic case, very little was known about the capabilities of this model. Two main basic problems were studied and solved (in the synchronous case): Byzantine agreement^[4] and collective coin flipping^[13].

This paper provides a full understanding of the power and limits of this model, by proving a few completeness theorems. Comparing these results to the cryptographic case of [7], one gets the impression that one-way functions are "more powerful" than secure channels. This should not be surprising, if one considers the case of $n=2$. Clearly, here a secure channel is useless, and indeed two (non-fault) players can compute the OR function of their bits using cryptography, while the reader can be convinced (it will be proven later) that any protocol will leak information in the information-theoretic sense. The lower bounds we provide show that the same phenomenon is true for any value of $n$. A similar situation arises in the Byzantine case where, using cryptography, one can allow $t\lt\frac n 2$ fault players, but in the non-cryptographic case one must have $t\lt\frac n 3$.

As happened in the cryptographic case, the protocols are based on a new method for computing with shared secrets. Our constructions are based on Algebraic Coding Theory, particularly the use of generalized BCH codes.

It is important to stress here that our main protocols require only a polynomial amount of work from the players. (In fact, they are efficient enough to be practical!). Putting no bound on the computational power serves only to allow the most stringent definition of privacy and the most liberal definition of faultiness, both of which we can handle.

Essentially the same results we obtain here were independently discovered by Chaum, Crépeau, and Damgård^[2]. We briefly point out the small differences of this work from ours. The simple case of no faults is almost identical. Their solution in the case of Byzantine faults is elementary and requires no error correcting codes. The error correction is achieved using a clever scheme of zero knowledge proofs. This has two consequences: They have to allow an exponentially small error probability for both correctness and privacy (we can guarantee them with no errors), and the frequent zero knowledge proofs increase the complexity of their protocols. In the solution of [2] the simulation is of Boolean operations while our solution allows direct simulation of arithmetic operations in large finite fields. Thus, for example, computing the product of two $n$-bit numbers using [2] calls for $O(\log{n})$ communication rounds. This can be done in $O(1)$ rounds using our solution.

We mention that the above results already found application in the new constant expected number of rounds protocol for Byzantine agreement of Feldman and Micali^[5].

We proceed to define the model, state the results and prove them. In the full paper we mention generalizations and extensions of our results to other tasks (playing games rather than computing functions), to other model parameters (synchrony, communication networks), and other complexity measures (number of rounds).

2. Definitions and Results

For this abstract, we define the model and state the results on an intuitive level. Since even the formal definition of the notions of privacy and resiliency are nontrivial, we give them explicitly in an appendix.

The model of computation is a complete synchronous network of $n$ processors. The pairwise communication channels between players are secure, i.e. they cannot be read or tampered with by other players. In one round of computation each of the players can do an arbitrary amount of local computation, send a message to each of the players, and read all messages that were sent to it at this round.

We shall be interested in the computational power of this model when imposing privacy and fault tolerance requirements. For simplicity, we restrict ourselves to the computation of (probabilistic) functions $f$ from $n$ inputs to $n$ outputs. We assume that player $i$ holds the $i$th input at the start of computation, and should obtain the $i$th output at the end, but nothing else.

A protocol for computing a function is a specification of $n$ programs, one for each of the players. We distinguish two kinds of faults: "Gossip" and "Byzantine". In the first, fault processors send messages according to their predetermined program, but try to learn as much as they can by sharing the information they received. In the second, they can use totally different programs, collaborating to acquire more information or even sabotage the computation.

A protocol is $t$-private if any set of at most $t$ players cannot compute after the protocol more than they could jointly compute solely from their set of privacy inputs and outputs.

A protocol is $t$-resilient if no set of $t$ or fewer players can influence the correctness of the outputs of the remaining players. For this to make sense, the function definition should be extended to specify what it is if some players neglect to give their inputs or are caught cheating (see appendix).

We can now state the main results of this paper.

Theorem 1:

For every (probabilistic) function $f$ and $t\lt\frac n 2$ there exists a $t$-private protocol.

Theorem 2:

There are functions for which there are no $\frac n 2$-private protocols.

Theorem 3:

For every probabilistic function and every $t\lt\frac n 3$ there exists a protocol that is both $t$-resilient and $t$-private.

Theorem 4:

There are functions for which there is no $\frac n 3$-resilient protocol.

3. Proof of Theorem 1

Let $P_0,\dots,P_{n-1}$ be a set of players, and let $n\geq 2t+1$. Let $F$ be the function which this set of players wants to compute $t$-privately, where each player holds some input variables to the function $F$. Let $E$ be some fixed finite field, with $|E|\gt n$. Without loss of generality we may assume that all inputs are elements from $E$ and that $F$ is some polynomial (in the input variables) over $E$, and that we are given some arithmetic circuit computing $|F|$, using the operations $+,\times$, and constants from $E$.

To simplify our explanation, we divide the computation into three stages.

Stage I

The input stage, where each player will enter his or her input variables to the computation using a secret sharing procedure.

Stage II

The computation stage, where the players will simulate the circuit computing $F$, gate by gate, keeping the value of each computed gate as a secret shared by all players.

Stage III

The final stage, where the secret shares of the final values of $F$ are revealed to one or all of the players.

Stages I and III are very simple and we describe them below, and delay the details of the computation stage to the next section.

3.1. The Input Stage

Let $a_0,\dots,a_{n-1}$ be some $n$ distinct non-zero points in our field $E$. (This is why we need $|E|\gt n$.) Each player holding some input $s\in E$, introduces the input to the computation by selecting $t$ random elements $a_i\in E$, for $i=1,\dots,t$, setting $$f(x)=s+a_1x+\cdots+a_tx^t$$ and sending to each player $P_i$ the value $s_i=f(a_i)$.

As in Shamir's^[11] secret sharing scheme, the sequence $(s_0,\dots,s_{n-1})$ is a sequence of $t$-wise independent random variables uniformly distributed over $E$, thus the value of the input is completely independent from the shares $\{s_i\}$ that are given to any set of $t$ players that does not include the player holding the secret.

We proved the above (and otherwise discuss it further) in Chaum, Damgård, and Crépeau's paper of the same year.

3.2. The Final Stage

To keep the $t$-privacy condition, we will make sure that the set of messages received by any set of $t$ players will be completely independent from all the inputs. During the whole computation each gate which evaluates to some $s\in E$, will be "evaluated" by the players by sharing the secret value of $s$ using a random polynomial $f(x)$ of degree $t$, completely independent from all the inputs, with the only restriction that $f(0)=s$. In particular at the end of the computation we will have the value of $F$ shared among the players in a similar manner. If we want to let just one player know the output value, all the players send their shares to that particular player. This player can compute the interpolation polynomial $f(x)$ and use its free coefficient as the result.

Note that there is a one-to-one correspondence between the set of all shares and the coefficients of the polynomial $f(x)$. Since all the coefficients of $f(x)$, except for its free coefficient, are uniform random variables that are independent of the inputs, the set of all shares does not contain any information about the inputs that does not follow from the value of $f(x)$.

4. The Computation Stage

Let $a,b\in E$ be two secrets that are shared using the polynomials $f(x),\,g(x)$ respectively, and let $c\in E,\;c\neq0$ be some constant. It is enough to show how one can "compute" $c\cdot a,\,a+b$, and $a\cdot b$.

The two linear operations are simple and for their evaluation we do not need any communication between the players. This is because if $f(x)$ and $g(x)$ encode $a$ and $b$, then the polynomials $h(x)=c\cdot f(x)$ and $k(x)=f(x)+g(x)$ encode $c\cdot a,\,a+b$ respectively. Thus to compute for example $a+b$, each player $P_i$ holding $f(a_i)$, and $g(a_i)$ can compute $k(a_i)=f(a_i)+g(a_i)$. Likewise, since $c$ is a known constant, $P_i$ can compute $h(a_i)=c\cdot f(a_i)$. Furthermore, $h(x)$ is random if only $f(x)$ was, and $k(x)$ is random if only one of $f(x)$ or $g(x)$ was.

As a corollary we immediately have

Lemma 1: (Linear Functional)

For any $t,\,(t\leq n-1)$, any linear functional $$F(x_0,\dots,x_{n-1})=a_0x_0+\cdots+a_{n-1}x_{n-1},$$ where each $P_i$ has input $x_i$ and the $a_i$ are known constants, can be computed $t$-privately.

From the lemma we have

Corollary 1: (Matrix Multiplication)

Let $A$ be a constant $n\times n$ matrix, and let each $P_i$ have an input variable $x_i$. Let $X=(x_0,\dots,x_{n-1})$ and define $Y=(y_1,\dots,y_n)$ by $$Y=X\cdot A$$ then for any $t,\,(t\leq n-1)$, we can $t$-privately compute the vector $Y$ such that the only information given to $P_i$ will be the value of $Y_i$, for $i=0,\dots,n-1$.

Proof:

Matrix multiplication is just the evaluation of $n$ linear functionals. By the Lemma, we can compute each linear functional $Y_i$ independently, and reveal the outcome only to $P_i$.

4.1. The Multiplication Step

The multiplication step is only a bit harder. Let $a$ and $b$ be encoded by $f(x)$ and $g(x)$ as above. We now assume that $n\geq 2t+1$. Note that the free coefficient of the polynomial $h(x)=f(x)g(x)$ is $a\cdot b$. There are two problems with using $h(x)$ to encode the product of $a$ times $b$. The first, and obvious, one is that the degree of $h(x)$ is $2t$ instead of $t$. While this poses no problem with interpolating $h(x)$ from its $n$ pieces since $n\geq 2t+1$, it is clear that further multiplications will raise the degree, and once the degree passes $n$ we will not have enough points for the interpolation. The second problem is more subtle. $h(x)$ is not a random polynomial of degree $2t$ (ignoring, of course, the free coefficient). For example, $h(x)$, as a product of two polynomials, cannot be irreducible.

To be more direct, this is a problem because the final share of the polynomial now no longer (necessarily) has a constant probability distribution, which means that $2t$ shares may leak information: so if, by some odd coincidence, only one final share would make the polynomial reducible, it must be the final share.

To overcome these two problems we will, in one step, randomize the coefficients of $h(x)$, and reduce its degree while keeping the free coefficient unchanged. We first describe the degree reduction procedure and then combine it with the randomization of the coefficients.

4.2. The degree reduction step

Let $$h(x)=h_0+h_1x+\cdots+h_{2t}x^{2t}$$ and let $$s_i=h(\alpha_i)=f(\alpha_i)g(\alpha_i),$$ for $i=0,\dots,n-1$, be the "shares" of $h(x)$. Each $P_i$ holds an $s_i$. Define the truncation of $h(x)$ to be $$k(x)=h_0+h_1x+\cdots+h_tx^t,$$ and $r_i=$$k(\alpha_i)$ for $i=1,\cdots,n-1$.

Claim:

Let $S=(s_0,\dots,s_{n-1})$ and $R=(r_0,\dots,r_{n-1})$ then there is a constant $n\times n$ matrix $A$ such that $$R=S\cdot A.$$

Proof:

Let $H$ be the $n$-vector $$H=(h_0,\dots,h_t,\dots,h_{2t},0,\dots,0)$$ and let $K$ be the $n$-vector $$K=(h_0,\dots,h_t,0,\dots,0).$$

Let $B=(b_{i,j})$ be the $n\times n$ (Vandermonde) matrix, where $b_{i,j}=\alpha_j^i$ for $i,j=0,\dots,n-1$. Furthermore, let $P$ be the linear projection $$P(x_0,\dots,x_{n-1})=(x_0,\dots,x_t,0,\dots,0).$$

We have $$H\cdot B=S$$ $$H\cdot P=K$$ and $$K\cdot B=R.$$

Since $B$ is not singular (because the $\alpha_i$'s are distinct) we have $$S\cdot(B^{-1}PB)=R$$ but $A=B^{-1}PB$ is some fixed constant matrix, proving our claim.

4.3. The Randomization Step

As noted above, the coefficients of the product polynomial are not completely random, and likewise the coefficients of its truncation $k(x)$ may not be completely random. To randomize the coefficients, each player $P_i$ randomly selects a polynomial $q_i(x)$ of degree $2t$ with a zero free coefficient, and distributes its shares among the player. By a simple generalization of the argument in Shamir's^[11] scheme, it is easy to see that knowing $t$ values on this polynomial gives no information on the vector of coefficients of the monomials of $x,x^2,\dots,x^t$ of $q_i(x)$.

This is also a simple generalization of the argument we make for the information-theoretic security of any $k\leq x$ shares for any $x$-degree polynomial, here.

Thus instead of using $h(x)$ in our reduction we can use $$\widetilde{h}(x)=h(x)+\sum\limits_{j=0}^{n-1}{q_j(x)}$$ which satisfies $\widetilde{h}(0)=h(0)$ but the other coefficients of $x^i,1\leq i\leq t$, are completely random. Since each player can evaluate his or her point $\widetilde s_i = \widetilde h(\alpha_i)$, we can now apply the truncation procedure using the matrix multiplication lemma to arrive at a completely random polynomial $\widetilde k(x)$ which satisfies both $\operatorname{deg}\widetilde k(x)=t$ and $\widetilde k(0)=a\cdot b$, and $\widetilde k(x)$ is properly shared among all the players.

Corrected "$k(x)$ is shared properly" to "$\widetilde k(x)$ is shared properly".

Thus (omitting many well known details, see [6]) we have proved

Theorem 1:

For every (probabilistic) function $f$ and $t\lt\frac n 2$ there exists a $t$-private protocol.

Remarks:

The complexity of computing $F$ $t$-privately is bounded by a factor polynomial in $n$ multiplied by the complexity of computing $F$.
If $F$ can be computed by an arithmetic circuit over some field using unbounded fan-in linear operations and bounded fan-in multiplication, in depth $d$, then $F$ can be computed $t$-privately in $\operatorname O(d)$ rounds of exchange of information.
In our construction we have to reduce the degree of our polynomial only when its degree is about to pass $n-1$. Thus if $t=\operatorname O(n^{1-\epsilon})$, for some fixed $\epsilon\gt 0$, and we start with polynomials of degree $t$, the players can simulate many steps of the computation before the degree comes close to $n$, by doing the computation each on their own shares, without any communication(!). When the degree does get close to $n$, we reduce the degree back to $t$ in one randomizing, degree reducing step.

Two simple examples are:
1. Any Boolean function $F:\,\{0,1\}^n\;\rightarrow\;\{0,1\}$ can be represented as a multilinear polynomial over the field $F$. Thus if $t=\operatorname O(n^{1-\epsilon})$ we can compute $t$-privately, in parallel, all the monomials of $F$ in $\operatorname O(1)$ number of rounds and then use a big fan-in addition to evaluate $F$. This procedure may use exponentially long messages but only constant number of rounds.
2. The Boolean Majority function has a polynomial size $\operatorname O(\log n)$ depth circuit, and thus for $t\,=\,\operatorname O(n^{1-\epsilon})$, this function can be computed $t$-privately using only polynomically long messages in constant number of rounds.

For completeness we state the following simple result.

Theorem 2:

There are functions for which there are no $\frac n 2$-private protocols.

Proof:

It is easy to see that two players, each holding one input bit, cannot compute the OR function of their bits without one of them leaking some information. This immediately generalizes to prove the theorem.

Specifically, this is for the following reason: say that Alice has input 0. Bob must give Alice enough information to output his own bit; this by definition leaks information. This is, of course, not true if Alice has input bit 1—but without already knowing that Alice has bit 1 (which constitutes a leak), Bob must assume the worst case and give Alice a possibility of a leak.

5. Sharing a Secret with Cheaters

Let $n=3t+1$ and let $P_0,\dots,P_{n-1}$ be a set of $n$ players among which we want to share a secret such that:

Any set of at most $t$ players does not have any information about the secret and
It is easy to compute the secret from all its shares even if up to $t$ pieces are wrong or missing.

The following scheme achieves both requirements:

Let $E$ be a finite field with a primitive $n$-th root of unity, $\omega\in E,\,\omega^n=1$ and for all $1\leq j\lt n,\,\omega^j\neq 1$. Without loss of generality we can assume that our secret $s$ is in $E$.

While originally the above stated $1\lt j\lt n$, we can expand this to $1\leq j$ because, if $\omega^1=1$, then obviously $\omega=1$ and therefore the statement would be false for all $j$.

We note that the above requirement on $E$—that it have a primitive $n$th root of unity—is non-trivial. A finite field of order $q$ has a primitive $n$th root of unity if and only if $n\,|\,q-1$.² We must therefore restrict ourselves to finite fields of order $p^k$ such that $n\,|\,p^k-1$. Since the statement $n\,|\,p^k-1$ is equivalent to the statement $p^k\equiv1\bmod n$, we can solve this congruency using the Fermat-Euler theorem: for any $p$ coprime to $n$, $p^{\operatorname\phi(n)}\equiv1\bmod n$. Since $p$ must be prime anyway, we come to the conclusion that we must use $E=GF(p^{\phi(n)})$ for any $p\in\mathbb P$ such that $p\not|\;n$. Notably, if $n$ is even, $p$ cannot be 2. For completeness, note that $p^{\phi(n)}$ is always strictly greater than $n$ for any valid choice of $p$.³

Pick a random polynomial $f(x)\in$$E[x]$, of degree $t$ such that $f(0)=s$. That is, set $\alpha_0=s$ and pick random $a_i\in E$ for $i=1\dots t$ and set $$f(x)=a_0+a_1x+\cdots+a_tx^t.$$ Define the share of $P_i,\,i=0\dots n-1,$ to be $s_i=f(\omega^i)$. As in [11], the $s_i$'s are $t$-wise independent random variables that are uniformly distributed over $E$, and thus our first requirement (A) is met.

Note that setting $a_i=0$ for $i\gt t$ makes our secret shares the Discrete Fourier Transform of the sequence $(a_0,\dots,a_{n-1})$. Let $\hat f(x)=s_0+s_1x+\cdots+s_{n-1}x^{n-1}$. By the well known formula for the inverse transform $$a_i=\frac 1 n\hat f(\omega^{-i})$$ and in particular $\hat f(\omega^{-i})=0$ for $i=t+1,\dots,n-1$. Explicitly the $s_i$ satisfy the linear equations $$\sum\limits_{i=0}^{n-1}\omega^{r\cdot i}\cdot s_i=0\;\text{for}\;r=1,\dots,2t.$$ Thus the polynomial $g(x)\,=\,\prod\nolimits_{i=t+1}^{n-1}(x-\omega^{-i})$ divides the polynomial $\hat f(x)$, which in the language of Error Correcting Codes says that the vector $s=(s_0,\dots,s_{n-1})$ is a codeword in the Cyclic Code of length $n$ generated by $g(x)$. By our choice of $g(x)$, this cyclic code is the well known Generalized Reed-Müller code. Such codes have a simple error correction procedure to correct $\frac 1 2\operatorname{deg}g(x)=t$ errors. See for example [10], page 283.

Intuitively, we can see that $g(x)\,|\,\hat f(x)$ since they share the same zeroes.

Reed-Müller codes and how to work with them is well outside the scope of this website; for more on working with them, we recommend MathWorld, an explanatory research paper published by MIT, or the book mentioned in the reference (on Google Books).

6. Verifying a Secret

Assume that player $P$ has distributed a secret in the manner described above. Before entering this shared secret into a computation, we wish to verify that the secret shares we are holding are shares of a real secret and not some $n$ random numbers. We want to do so without revealing any information about the secret or any of its shares. This is easily done using the following Zero Knowledge proof technique. We will later show how to verify a secret using a different technique that has absolutely no probability of error. We present this Zero Knowledge technique because it is simpler, and uses fewer rounds of communication.

6.1. Simple Verification of a Secret

Let $f_0$ be the original polynomial. Let $f_1,\dots,f_m,\,m=3n$ be random polynomials of degree $t$ generated by $P$, and have $P$ send to $P_i$ the values $f_j($$\omega^i)$ for $j=1,\dots,m$. Each $P_i$ selects a random $\alpha_i\neq 0$ from $E$ and sends it to all the other players. After reaching agreement on the set of $\alpha$'s, the dealer broadcasts the set of polynomials $f^\alpha=\sum\nolimits_{k=0}^m\alpha^kf_k$ to all players. Each player $P_i$ checks that, at the point $\omega^i)$, the shares received satisfy the required equations for all the $\alpha$'s. If some $P_i$ finds an error he or she broadcasts a complaint. If $t+1$ or more players file a complaint, we decide that the dealer is faulty and take some default value, say 0, to be the dealer's secret (and pick 0 for all the needed shares).

Claim:

Let $T$ be a set of good players that did not complain. Let $f_i^T$ be the interpolation polynomial through the points in $T$ of the original polynomial $f_i$. Then, with probability at least $$1-\frac{m2^n}{|E|},$$ all the polynomials $f_i^T$ are of degree $t$.

Proof:

Omitted

Keeping in mind the (polynomial) complexity of the players' computation, we can certainly allow $|E|\geq 2^{2n}$. This makes the error probability exponentially small. (The case of small $|E|$ is similar: Using a somewhat large $m$, each player, using a different set of random polynomials, asks the dealer to reveal either $f_i$ or $f_0+f_i$.)

Note that if $n\geq5t+1$, then our secret sharing scheme can correct $2t$ errors. If a secret is accepted, then at most $t$ good players may have wrong values. This together with at most $t$ more wrong values that may come from the bad players, gives altogether at most $2t$ errors. Thus in this case the secret is uniquely defined and there is a simple procedure to recover its value using the error correcting procedure.

To handle the case of $n=3t+1$ we must make sure that all the pieces in the hands of the good players lie on a polynomial of degree $t$. To achieve this we ask the dealer of the secret to make public all the values that were sent to each player who filed a complaint. We now repeat the test, using new random $\alpha$'s. Each player now checks at his or her own point and at all the points that were made public, and if there is an error he or she files a complaint. If by now more than $t+1$ players have complained we all decide that the secret is bad and take the default zero polynomial. Otherwise,

Claim:

With very high probability, all good players are on a polynomial of degree $t$.

Proof:

Omitted.

Note that if the dealer is correct, then no good player's value will become public during the verification process. This, together with the fact that all the polynomials that the dealer reveals during this verification procedure are completely independent from the secret polynomial $f_0$, ensures that the bad players will not gain any information about the dealer's secret. (Detailed proof omitted).

6.2. Absolute Verification of a Secret

The verification procedure described above leaves an exponentially small probability of error. In this section we describe a secret verification procedure that leaves no probability of error.¹

Instead of just sending the shares $\{s_i\}$, the dealer of the secret selects $n$ random polynomials $f_0(x),\dots,f_{n-1}(x)$, with

$s_i=f_i(0)$ for $i=0,\dots,n-1$, and
$\sum\nolimits_{i=0}^{n-1}$$\omega^{r\cdot i}$$f_i(x) = 0$ for $r=1,\dots,2t$

In other words, the dealer selects a random polynomial $f(x,y)$, of degree $t$ in both variables $x$ and $y$, with the only restriction that $f(0,0)=s$ (the secret to share). The dealer then sends the polynomials $f_i(x)=f(x,$$\omega^i$$)$ and $g_i(y)=f($$\omega^i$$,y)$ to player $P_i$, for $i=0,\dots,n-1$. The real share is just $s_i=f_i(0)$, but for the purpose of its verification, the dealer also sends the polynomials $f_i(x)$ and $g_i(y)$. At this point, each player $P_i$ sends $s_{i,j}=f_i($$\omega^j$$)=f($$\omega^j,\omega^i$$)=g_j($$\omega^i$$)$ to each player $P_j$.

Note that if the dealer is correct, then when a good player $P_j$ is looking at the sequence $SS_j=(s_{0,j},s_{i,j},\dots,s_{n-1,j})$, then all these points should be on $P_j$'s known polynomial $g_j(y)$. Therefore $P_j$ can compare the incoming values with that polynomial and find out which values are wrong. Furthermore it is clear that in this case no good player will have to correct any value coming from other good players.

On the other hand we have

Lemma:

If no correct player has to correct a value given by a correct player, then there is a polynomial of degree $t$ that passes through the interpolation points of all the correct players.

Proof:

Simple algebra. Omitted.

To make sure that the condition of this lemma is satisfied, each player $P_j$ broadcasts a request to make public the coordinates $(i,j)$ that were incorrect. If $P_j$ detects more than $t$ wrong incoming values, or had to correct his or her own value, the dealer is clearly faulty. In such a case $P_j$ broadcasts a request to make both $f_j(x)$ and $g_j(y)$ public. At this point the dealer broadcasts the (supposedly true) values $s_{i,j}$ at all these points, and the polynomials that were to be made public. Note that making $f_j$ and $g_j$ public makes all the $s_{k,j}$ and $s_{j,k}$ public for $0\leq k\lt n$, for that particular $j$.

Now if some $P_i$ observes that some new public $s_{i,j}$ contradicts the polynomials in that player's possession, or finds out that the public information already contradicts itself, he or she broadcasts a request to make all of his or her information public. Here once more, the dealer makes public all the requested information. Finally, each $P_i$ checks all the public and private information received from the dealer. If any $P_i$ finds an inconsistencies, the player broadcasts a complaint by asking all his or her private information to be made public.

If all this point $t+1$ or more players have asked to make their information public, the dealer is clearly faulty and all the players pick the default zero polynomial as the dealer's polynomial. Likewise, if the dealer did not answer all the broadcasted requests, the dealer is declared faulty. On the other hand, if $t$ or fewer players have complained, then there are at least $t+1$ good players who are satisfied. These uniquely define the polynomial $f(x,y)$ and they conform with all the information that was made public. In this case, the complaining players take the public information as their share.

Note that if the dealer has distributed a correct secret then no piece of information of any good player was revealed during the verification process. If however the dealer was bad, we do not have to protect the privacy of the secret, and the verification procedure ensures us that all the good players values lie on some polynomial of degree $t$.

7. Some More Tools

Before going into the computation stage, we need two more tools.

Generating (and verifying) a random polynomial of degree $2t$, with a zero free coefficient.
Allowing a dealer to distribute three secrets, $a,\,b$, and $c$, and verifying that $c=a\cdot b$.

Both of these are not needed when $n\geq4t+1$, but are required to handle the $n=3t+1$ case.

7.1. Generating Polynomials of Degree $2t$

Let each player $P_i$ distribute $t$ random (including the free coefficient) polynomials $g_{i,k}(x),\,k=1,\dots,t$, of degree $t$. Define $f_i(x)$ by $$f_i(x) = \sum\limits_{k=1}^t{x^k\cdot g_{i,k}}$$ and let the players evaluate from their points on the $g_{i,k}$'s their corresponding point on $f_i(x)$.

After we have verified that indeed $\operatorname{deg}g_{i,k}\leq t$, it is clear that $\operatorname{deg}f_i(x)\leq 2t$, and $f_i(0)=0$. (It is also clear that the vector of coefficients of the monomials of $x^i,\,i=1,\dots,t$, in $f_i(x)$ are uniformly distributed and are completely independent from the information held by any set of at most $t$ players that does not include $P_i$.)

Finally, as our random polynomial we take $$f(x)=\sum\limits_{i=0}^{n-1}{f_i(x)}.$$

7.2. Verifying that $c=a\cdot b$

Let the player $P$ distribute $a$ and $b$ using the polynomials $A(x)$ and $B(x)$ respectively. We want $P$ to also distribute a random polynomial encoding $c=a\cdot b$, in such a way that the players can all verify that indeed $c=a\cdot b$. Let $$D(x)=A(x)\cdot B(x)=c+c_1x+\dots+c_{2t}x^{2t}$$ and let $$\begin{align}D_t(x)&=r_{t,0}+r_{t,1}x+\dots+r_{t,t-1}x^{t-1}+c_{2t}x^t\\D_{t-1}(x)&=r_{t-1,0}+\dots+r_{t-1,t-1}x^{t-1}+[c_{2t-1}-r_{t,t-1}]x^t\\\vdots\quad&\quad\vdots\\D_1(x)&=r_{1,0}+\dots+r_{1,t-1}x^{t-1}+[c_t-r_{t,1}-r_{t-1,2}-\dots-r_{2,t-1}]x^t\end{align}$$ where the $r_{i,j}$ are random elements from $E.\;P$ selects the $D_i(x)$ and distributes their shares to all the players. After verifying that $A(x),\,B(x)$ and all the $D_i(x)$ are of degree $t$, define $$C(x)=D(x)-\sum\limits_{i=1}^tx^i\cdot D_i(x).$$ and verify that $C(x)$ is also of degree $t$. From the construction of $C(x)$ it is clear that $C(x)$ is a random polynomial of degree $t$ with the only restriction that $C(0)=a\cdot b$.

8. Proof of Theorem 3

We separate again the computation to its Input, Computation, and Final stages. At the input stage, we let all players enter their inputs to the computation using our secret sharing scheme, while verifying that each secret shared is indeed some polynomial of degree $t$. The secret verification assures that the inputs of any Byzantine player is well defined, but does not ensure that it is in the domain of our function. For example, in a 0-1 vote, we must verify that the input is 0 or 1. We defer this type of verification to the computation stage.

The final stage is exactly the same as in the proof of Theorem 1. When we have simulated the circuit, and the players are holding the pieces of a properly shared secret encoding the final output, they send all the pieces to one or all the players. As at most $t$ pieces are wrong, each player can use the error correcting procedure and recover the result.

8.1. The Computation Stage - Byzantine Case

Let $a$ and $b$ be properly encoded by $f(x)$ and $g(x)$ respectively, where by "properly encoded" we mean that all the pieces of the good players are on some polynomial of degree $t$. Since $f(x)$ and $g(x)$ are properly encoded, the polynomials $f(x)+g(x)$ and $c\cdot f(x)$ properly encode $a+b$ and $c\cdot a$ for any constant $c\in E$. The same argument of Theorem 1 implies that we can do the computation of any linear operation with no communication at all.

Here again, the multiplication step is more involved. To repeat the procedure of theorem 1 using the degree reduction step, via the Matrix Multiplication Lemma, we must make sure that all the players use, as input to this procedure, their correct point on the product polynomial $h(x)=f(x)g(x)$. To guarantee that this indeed happens, we use the Error Correcting Codes again.

Let $a_i=f($$\omega^i$$),\,b_i=g($$\omega^i$$)$ and $c_i=h($$\omega^i$$)=a_i\cdot b_i$ be the points of $P_i$ on these polynomials. We ask each $P_i$ to pick a random polynomial of degree $t,\,A_i(x)$, such that $a_i=A_i(0)$, and use this polynomial to distribute $a_i$ as a secret to all the players. Similarly, $P_i$ distributes $b_i$ using $B_i(x)$. We also ask $P_i$ to distribute $c_i$ using the polynomial $C_i(x)$, while verifying that $A_i(x),\,B_i(x),\,C_i(x)$ are all of degree $t$, and that $C_i(0)=A_i(0)B_i(0)$.

We want to verify that the free coefficients of the polynomials $C_i(x)$ are all points on the product polynomial $h(x)$. It is enough to verify that all the free coefficients of the $A_i(x)$ and $B_i(x)$ are on $f(x)$ and $g(x)$ respectively. We do this as follows.

The free coefficients of the $A_i(x)$'s are a code word with at most $t$ errors. By our assumption, all the $A_i(x)$ are properly distributed. We can therefore use them to compute any linear functional. In particular, using the same $A_i(x)$'s we can compute the polynomials $$S_r(x)=\sum\limits_{i=0}^{n-1}{\omega^{r\cdot i}A_i(x)}$$ for $r=1,\dots,2t$. At this point, all the players reveal their points on the polynomials $S_r(x)$, enabling all the players to recover the value of $s_r=S_r(0)$, for $r=1,\dots,2t$.

Note that if all the $A_i(0)$ are correct (i.e. on a polynomial of degree $t$) then $s_r=0$ for all $r$. Thus the computed value of the $s_r$ are just a function of the errors introduced by the Byzantine players. In particular, this implies that the value of the $s_r$ does not reveal any information that is held in the hands of the good players!

Since at most $t$ of the $A_i(0)$ can be wrong, the value of the $s_r$'s, the so-called Syndrome Vector, is the only information needed by the error correction procedure to detect which coordinates $A_i(x)$ encode a wrong $A_i(0)$, and give the correct value. Therefore if some $s_r\neq 0$, all the players compute the wrong coordinates, the correct value of $f$($\omega^i$), and use the constant polynomial with this value, instead of $A_i(x)$.

In a similar way we can check and correct the $B_i(x)$. We can, therefore, also check (and correct) the $C_i(x)$, so we are sure that all the inputs to the linear computation we have to do in the degree reduction procedure are correct.

Note that much of this is not needed when $n\geq 4t+1$, because then we can still correct up to $t$ errors on polynomials of degree $2t$. In this case we can do the error correction on the points of $h(x)$ directly.

As in the proof of Theorem 1, we have,

Theorem 3:

For every probabilistic function and every $t\lt\frac n 3$ there exists a protocol that is both $t$-resilient and $t$-private.

For completeness we state,

Theorem 4:

There are functions for which there is no $\frac n 3$-resilient protocol.

Proof:

Follows immediately from the lower bound for Byzantine Agreement in this model. We note that even if we allow broadcast as a primitive operation, theorem 4 remains true. This is because we can exhibit functions for three players that cannot be computed resiliently, when one player is bad. This generalizes immediately to $\frac n 3$.

Remark:

All the remarks following the statement of theorem 1 also apply to theorem 3.

Appendix

Formal Notation

Let $F$ be a field. Let $U=F^n$ denote the standard $n$-dimensional vector space over $F$ and $M_n(F)$ the ring of $n\times n$ matrices over $F$.

Let $R$ be a random variable with distribution $D$ over $F$. Then $R^k\,(R^*)$ denotes $k$ (finitely many) independent draws from $D$.

Comment:

Unless otherwise specified, $F$ will be finite, and $D$ the uniform distribution over $F$.

The Basic Model

Fix $n\gt 0$ and a field $F$. Intuitively, an $(n,F)$-network is a complete synchronous network of $n$ probabilistic machines (players) $P_0,P_1,\dots,P_{n-1}$. At every round each players can send one message (element of $F$) to each other player, receive a message from each other player, and perform arbitrary computation.

If we assume for convenience that players send messages to themselves too, a round of communication is neatly described by a matrix $M\in M_n(F)$, where each $P_i$ sent the $i$th row of $M$, and receives the $i$th column of $M$. (This formalizes the security of private channels).

Formally, a $T$ round $(n,F)$-network is a set of players $\{P_0,P_1,\dots,P_{n-1}\}$. Each $P_i$ is a tuple $$P_i=\left\langle Q_i,q_i^{(0)},R_i,\delta_i\right\rangle,$$ where $Q_i$ is a set of states, $q_i^{0}$ the initial state, $R_i$ is a random variable over $F$ (distributed like $R$) and $$\delta_i:\,[T]\times Q_i\times F^n\times R_i^*\rightarrow Q_i\times F^n$$ is a transition function that, given a round number, state, previous round input, and private coin tosses, computes the next state and this round's output.

A protocol is simply $\delta=\left\langle\delta_0,\delta_1,\dots,\delta_{n-1}\right\rangle$, the transition functions prescribing to each player what to do in each round.

A run $M$ of a protocol $\delta$ is a sequence $(M_1,M_2,\dots,M_T),\,M_j\in M_n(F)$ of matrices describing the communication in rounds $j=1,2,\dots,T$. Note that $M$ is a random variable, depending on $\{w_i^{(0)}\}$, the initial states, and $\{R_i^*\},\,(=R^*)$, the random draws from $D$.

A (probabilistic) function is a function $f$, $$f:\;F^n\times R^m\rightarrow F^n.$$

Intuitively, a protocol computes a function $f$ if, for all $v\in F^n$, if $P_i$ is given $v_i\in F$ before round 1, then after round $T$ it knows $u_i$, such that $u=\left\langle u_0,u_1,\dots,u_{n-1}\right\rangle$ is distributed exactly like $f(v\times R^m)$. For convenience we denote a vector $\left\langle a_0,a_1,\dots,a_{n-1}\right\rangle$ by $\langle a_i\rangle$. Also, $q_i^{(j)}$ denotes the state of $P_i$ after round $j$.

To formally define what it means for a protocol to compute a function, we assume fixed input and output functions, $I_i,O_i:\,Q_i\rightarrow F$ for each player $P_i$. Now $\delta$ computes $f$, if for every choice of $\left\langle q_i^{(0)}\right\rangle$, we have $\left\langle O_i\left(q_i^{(T)}\right)\right\rangle=\operatorname f\left(I_i(q_i^{(0)})\times R^m\right)$ (as random variables).

Some Intuition

The bad players in our model can completely coordinate their actions. Hence, for a bad set (coalition) $C\subseteq[n]=\{0,1,2,\dots,n-1\}$, the transition functions $\delta_i,\,i\in C$ are replaced by arbitrary functions $\delta_i'$ that compute the next state and messages of $P_i$ from the joint information of the current state, previously received messages and random choices of all $\{P_i\},\,i\in C$. We denote any protocol in which a set of $C$ is bad (in this sense) by $\delta_C$.

We distinguish two types of bad behavior. The benign (gossip) kind, in which bad players send messages according to the original protocol $\delta$, but try to learn as much as they can from it by joining their forces. The malign (Byzantine) kind puts no restrictions on the bad players, i.e. the $\delta_i'$ can really be arbitrary.

To formalize the benign kind of bad behavior we need the following definition: Two protocols $\delta$ and $\delta'$ look alike if their runs have the same distribution, i.e. $M=M'$ as random variables, for every fixed initial state $\left\langle q_i^{(0)}\right\rangle$ of all players.

A bad coalition $C$ is called gossip if the protocol $\delta_C$ looks like $\delta$, otherwise it is called Byzantine.

In the case of gossip, we don't have to worry about the correctness of computing $f$—this follows from the definition "look alike". Here all we shall have to prevent is leakage of information. In case of Byzantine faults, we will have to guarantee also the correctness of the computation. We proceed now to define the important notions of Privacy and Correctness.

Privacy (preliminary):

Intuitively, a coalition $C$ did not learn anything from a protocol for computing $f$, if whatever it can compute after the protocol (from its final states), it could compute only from its input (initial states) and its components of the function values.

Let $Q_C=\prod\nolimits_{i\in C}Q_i$ and $A$ be an arbitrary set. Also, if $u=\left\langle u_0,u_1,\dots,u_{n-1}\right\rangle,\,u_C$ denotes the sub-vector of $u$ that contains $u_i,\,i\in C$. Formally a set $C$ is ignorant in a protocol $\delta$ (for computing $f$), if for every set of initial states $\left\langle q_i^{(0)}\right\rangle$, every protocol $\delta_C$ that looks like $\delta$, and every function $g':\;Q_C\rightarrow A$ there exists a function $g:\;Q_C\times F^{|C|}\rightarrow A$ satisfying $$g'\left(q_C^{(T)}\right)=g\left(q_C^{(0)},\,f\left(\left\langle I_i(q_i^{(0)})\right\rangle\right)_C\right)\quad\quad(*)$$

The above was corrected; originally, a function $d$ was defined, but never used, while $g$ was used, but never defined. There was additionally an extra comma after $f$ which made the function poorly-defined.

A protocol $\delta$ (for computing $f$) is $t$-private if every coalition $C$ with $|C|\leq t$ is ignorant.

Correctness:

This issue is problematic, since some of the bad players can obliterate their initial inputs, and the function value is not well defined (a simple example is Byzantine agreement). To ignore bad inputs for every set $B\subseteq[n]$, we need a (sub)function of $f$ that depends on the input coordinates of only $[n]\backslash B$. (A special case is assigned default values to input coordinates in $B$).

So now by $f$ we mean a family of functions $\{f_B:\;F^{n\backslash B}\times R^m\rightarrow F^n\}\;B\subseteq[n]$, with $f_\varnothing$ being the original function $f$. Typically, (as in Byzantine agreement) this exponential size family is very succinctly described.

So now, a computation is correct if all good players compute a function $f_B$, where $B$ is a subset of the bad players.

More formally, a coalition $C$ is harmless if, for every set of initial states $\left\langle q_i^{(0)}\right\rangle$ and every protocol $\delta_C$, $$\left\{\left\langle O_i\left(q_i^{(T)}\right)\right\rangle\right\}_{[n]\backslash C}\;=\;f_B\left(\left\{\left\langle I_i\left(q_i^{(0)}\right)\right\rangle\right\}_{[n]\backslash B}\right)_{[n]\backslash C}$$ for some $B\subseteq C$.

A protocol is $t$-resilient if every coalition $C$ with $|C|\leq t$ is harmless.

Privacy Revisited:

For the case of Byzantine faults, the assumption that $\delta_C$ looks like $\delta$ is invalid. For any harmless coalition $C$ we can remove this assumption from the definition of ignorance, and replace $f$ in $(*)$ above, by $f_B$, the function that will actually be computed by the good players.

Now the notion of a protocol that is both $t$-resilient and $t$-private is well defined.

Footnotes

Our original protocol was simplified by Paul Feldman who independently observed that the verification procedure can be accomplished in a constant number of communication rounds.
Claim: $GF(q)$ has a primitive $n$th root of unity if and only if $n\,|\,q-1$. To quickly demonstrate this, assume we have a primitive $n$th root of unity $\omega$ for $GF(q)$ where $n\not|\;q-1$. Take any generator $g$ in this field: by definition of a generator, there exists an $a$ such that $g^a=\omega$. Since the field is a multiplicative ring, $g^{q-1}=g^0=1$. But $g^{an}=1$, and by definition of a primitive root of unity, there is no smaller (non-zero) exponent such that this is true. So $g^{an}=g^{q-1}$ therefore implies $an=q-1$, clearly contradicting our assumption that $n\not|\;q-1$.
Claim: $p^{\phi(n)}\gt n$ for any $n\in\mathbb Z^{\gt2},\;p\in\mathbb P,\,p\not|\;n$. This follows simply from a (loose) lower bound on $\operatorname\phi:\;\operatorname\phi(n)\geq\sqrt n,\;n\gt6$. The lower bound on $p$ is clearly 2, so we simply need to prove that $2^{\sqrt n}\gt n$. Keeping in mind that the logarithm function is monotonically increasing, this statement is equivalent to $$\begin{align}\log{2^{\sqrt n}}\;&\gt\;\log n\\\sqrt n\cdot\log2\;&\gt\;\log n\end{align}$$ which is true for all $n\gt0$. We are left only to demonstrate that $p^{\operatorname\phi(n)}\gt n$ for 3 ($2^2\gt 3$), 4 ($3^2\gt 4$), 5 ($2^4\gt5$), and 6 ($5^2\gt6$). We have therefore demonstrated that, for all $n$, and for the lowest valid $p,\,p^{\phi(n)}\gt n.\quad\blacksquare$

References

M. Ben-Or and N. Linial, Collective coin flipping, FOCS86.
D. Chaum, C. Crépeau, and I. Damgård. Multiparty unconditionally secure protocols. These proceedings.
W. Diffie and M. E. Helman, New directions in cryptography, IEEE Trans. Inform. Theory, Vol. IT-22, pp.644-654, 1976.
D. Dolev and R. Strong. Polynomial algorithms for multiple processor agreement. STOC82.
P. Feldman and S. Micali, Optimal algorithms for Byzantine agreement. These proceedings
O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but the validity of the assertion, and a methodology of cryptographic protocol design. FOCS86, pp. 174-187.
O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. STOC87, pp.218-229.
S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. STOC85, pp. 291-304.
M. Pease, R. Shostak, and L. Lamport. Reaching agreement in the presence of faults, JACM. Vol. 27, pp. 228-234. 1980.
W. W. Peterson and E. J. Weldon, Error correcting codes, Second Ed., MIT Press. 1972.
A. Shamir, How to share a secret. CACM 22, pp. 612-613. 1979.
A. C. Yao, How to generate and exchange secrets. STOC86.
A. C. Yao, On the succession problem for Byzantine Generals, manuscript. 1983.

Problem with this page?

Created by Nicolas Schank 2014, Brown University

All original work is free for any use by anyone whatsoever.

For more information about liability and licensing Yao's original paper, see Liability.

Multiparty Computation

home

learn

research

build

resources

about us

Editor's Overview

Introduction

Goals and Results

Assumptions

Definitions

Theorems

Further Reading

Referencing This Paper

Annotated Paper (extended abstract)

Abstract

1. Introduction

2. Definitions and Results

3. Proof of Theorem 1

3.1. The Input Stage

3.2. The Final Stage

4. The Computation Stage

4.1. The Multiplication Step

4.2. The degree reduction step

4.3. The Randomization Step

5. Sharing a Secret with Cheaters

6. Verifying a Secret

6.1. Simple Verification of a Secret

6.2. Absolute Verification of a Secret

7. Some More Tools

7.1. Generating Polynomials of Degree \(2t\)

7.2. Verifying that \(c=a\cdot b\)

8. Proof of Theorem 3

8.1. The Computation Stage - Byzantine Case

Appendix

Formal Notation

The Basic Model

Some Intuition

Privacy (preliminary):

Correctness:

Privacy Revisited:

Footnotes

References