and since each $R_j$ and each $X_j$ is invertible,
revealing $S_1,\dots,S_N$ gives no information about $X_1,\dots,X_N.$
That is, the list of elements $(S_1,\dots,S_N)$ is distributed uniformly
at random, given by the following easy lemma:

Let $G$ be a group.  For any $X_1,\dots,X_N \in G,$
$\uniform( G^N ) =$

$\{(R_0,\ldots,R_N) \leftarrow \uniform(G^{N+1}));$

S_1 \leftarrow R_0 X_1 R_1^{-1};
\ldots;
S_N \leftarrow R_{N-1} X_N R_N^{-1}:
(S_1,S_2,\ldots,S_N) \}

Formally speaking, protocol computes a four robust and private
intermediate functions.  The first function $F^1$ supplies each player with
pieces of random group elements; the second, $F^2,$ provides pieces of
their inverses; the third, $F^3,$ generates a public (hence robust)
uniformly distributed (hence private) vector of values $(S_1,\ldots,S_N);$
and the fourth provides pieces of $Y.$ Theorem <ref>
implies the resilience of .

Applying Theorem <ref>, we need only $O(C)$ rounds to invert
each secret $R$ in (IM2).  Steps (IM3) and (IM6) use constant depth
circuits and are easily performed with a constant number of rounds of
interaction.  Step (IM4) requires a round of interaction and step (IM5)
requires none.

§ THE POWER OF ITERATED MULTIPLICATION

In this section we prove the crucial and surprising result that is the
focus of this chapter.  The result depends critically on the ability to
perform iterated multiplication of secret $3 \times 3$ matrices;
Theorem <ref> of the previous section is key.
Let $ANC^1$ denote the class of functions which can be written
as polynomial size algebraic formulas, or logarithmic depth circuits,
over a fixed finite field $E.$
(The abbreviation derives from “Algebraic NC.”)
The standard approach of simulating a circuit suggests that the number
of rounds required to evaluate $F \in ANC^1$ grows unboundedly, and
it was conjectured that a logarithmic lower bound on the number of
rounds would hold.  We prove to the contrary that a fixed number
of rounds suffice.

constant rounds!NC1
For $3t<n$ and any function $F \in ANC^1$ (or $F \in NC^1$),
there exists a $t$-resilient protocol to compute $F$
in a constant number of rounds, with polynomial message sizes.

In [7] Barrington showed that $NC^1$ is equivalent
to multiplying polynomially-many permutations of 5 elements.
Ben-Or and Cleve [24] generalized this to show that computing
polynomial-size algebraic formulas (complete for $ANC^1$)
over a field $E$ is equivalent
to multiplying polynomially-many $3 \times 3$ matrices over that field.
Our method for computing $ANC^1$ was facilitated by a table-chaining technique
suggested by M. Rabin [104].

Let $F$ be representable by an algebraic formula $\scf$ of depth $d$ having
variables $X_1,\dots,X_n.$ By [24], there is a sequence of $3 \times
3$ matrices $M_1,\dots,M_{p(d)}$ whose product $M[\scf]$ contains
$F(X_1,\dots,X_n)$ in the upper right entry $(1,3).$ Here, $p(d)=O(4^d).$

For completeness we describe the sequence of matrices corresponding to
$\scf.$  Let

\[
\begin{tabular}{rclrcl}
$J_1$ & = &
\begin{tabular}{rrr}
0 &  1 &  0 \\
-1 &  0 &  0 \\
0 &  0 &  1 \\
\end{tabular}
\right]$
$J_2$ & = &
\begin{tabular}{rrr}
0 &  0 & -1 \\
1 &  0 &  0 \\
0 &  1 &  0 \\
\end{tabular}
\right]$
\\
$J_3$ & = &
\begin{tabular}{rrr}
0 &  1 &  0 \\
0 &  0 &  1 \\
1 &  0 &  0 \\
\end{tabular}
\right]$
$J_4$ & = &
\begin{tabular}{rrr}
0 &  0 &  1 \\
-1 &  0 &  0 \\
0 &  1 &  0 \\
\end{tabular}
\right]$
\end{tabular}
\begin{tabular}{lcr}
$J_5$ & = &
\begin{tabular}{rrr}
-1 &  0 &  0 \\
0 &  0 &  1 \\
0 &  1 &  0 \\
\end{tabular}
\right]$
\end{tabular}
\]

Furthermore, let

$M[f]$     =
\begin{tabular}{rrr}
1 &  0 &  $f$ \\
0 &  1 &  0 \\
0 &  0 &  1 \\
\end{tabular}
\right)$

Constants and variables are represented by $M[c]$ and $M[x_i].$ The product
$M[\scf]$ is derived from the following observations:

\begin{eqnarray*}
M[f+g] & = & M[f] \cdot M[g] \\
M[f \cdot g] & = & J_1 \cdot M[g] J_2 \cdot M[f]
\cdot J_3 \cdot M[g] J_4 \cdot M[f] \cdot J_5.
\end{eqnarray*}

The protocol is simple: each $M[x_i]$ is shared by player $i,$ and the
network multiplies all the matrices together.  Notice that the matrices are
all full-rank and therefore form a group under multiplication.  According
to Theorem <ref> and
Corollary <ref>, the secret product $M[\scf]$ takes a
constant number of rounds to compute.  The result is the secret $M[\scf](1,3)$
and is revealed or left secret for use in further protocols.

Figure <ref> gives more details.  For the sake of efficiency,
the constant matrices are collapsed at the start:
let $H=\set{M_i \mid M_i
\mbox{\hspace{0.1in} contains a variable}},$
let $q = \abs{H},$ let $h(i)$ be the index of
the $i^{th}$ member of $H,$ let $G(i)=\set{M_j \mid h(i)<j<h(i+1)}$ be the
set of constant matrices to the right of $M_{h(i)},$ and let $G(0)$ be the
set of matrices to the left of $M_{h(1)}.$ Define $N_1 = [\prod G(0)] H(1)
[\prod G(1)]$ and $N_j = H(j)[\prod G(j)].$

* Each player $i$ shares $x_i.$

* Secretly compute each $N_1,\ldots,N_q$ using , noninteractively.

* Run ($N_1,\ldots,N_q$) to obtain secret matrix $M[\scf].$

* The result is the top right secret of $M[\scf],$ i.e. $M[\scf](1,3).$

Protocol to evaluate $NC^1$ or $ANC^1$ circuit in constant rounds and
polynomial message sizes.

§.§ Reducing Rounds for Polynomial Size Circuits

The results of the previous section easily show how to reduce the number of
rounds for circuit-based protocols.

For $3t<n$ and any function family $F$ described by a polynomial-size
circuit family $C_F,$ there exists a $t$-resilient protocol to compute $F$
using $O({\tt depth}(C_F)/(\log nm))$ rounds, with messages of size
polynomial in $n$ and $m.$

Define the slice function $F^i$ to be the set of outputs at the $(i\cdot
\log nm)^{th}$ level of circuit $C_F.$ Clearly, $F$ can be written as the
product of ${\tt depth}C_F/(\log nm)$ of these functions, and each function
is in $NC^1.$ By Theorem <ref>, there is a set of protocols to
evaluate each slice function; by eliminating the final step
from each protocol, we obtain a protocol that produces secretly
shared values rather than revealing the outputs of that level.  By
Theorem <ref>, the concatenation is $t$-resilient.  The number
of rounds required by the concatenated protocol is clearly $\log nm$ times
the number of rounds to compute a slice function, which is constant.

§.§ Determinants in Constant Rounds

In fact, Theorem <ref> gives a stronger result using iterated
multiplication of $n \times n$ matrices.  By
Theorem <ref> and Corollary <ref>, there
is an expected constant-rounds protocol to compute the product of a
polynomial number of matrices.  Cook [50] and Berkowitz
[30] show that the iterated product of integer $n \times n$
matrices is complete for , the class of all problems that are
$NC^1$ reducible to DET, namely those that are $NC^1$ reducible to
computing the determinant of an $n \times n$ matrix.

For $3t<n$ and any function $F \in \mbox{DET$^*$},$ there exists a
$t$-resilient protocol to compute $F$ in a constant expected number
of rounds, with polynomial message sizes.

§ ANY FUNCTION IN CONSTANT ROUNDS

In fact, at the expense of a possible exponential blowup in message size,
it is certainly possible to achieve secure protocols in constant rounds for
$3t<n.$ The idea is based on representing a function $F(x_1,\ldots,x_n)$ as
a weighted sum whose addenda are computable in constant rounds.  The
message size depends on the number of addenda, which itself depends on $F.$
Ignoring the number of addenda, each of which can be computed in parallel
and then added non-interactively, the protocol requires constant rounds.

Any function $F : E^n \rightarrow E$ has a canonical representation
as a function $c_F$ such that on $\set{0,1}^n,$ $c_F(x_1,\ldots,x_n) =
F(x_1,\ldots,x_n),$ in the following manner:

\[
c_F(x_1,\ldots,x_n) =
\sum_{(\epsilon_1,\ldots,\epsilon_n) \in \set{0,1}^n}
F(\epsilon_1,\ldots,\epsilon_n)  \cdot
\delta((\epsilon_1,\ldots,\epsilon_n),(x_1,\ldots,x_n))
\]

where $\delta((\epsilon_1,\ldots,\epsilon_n),(x_1,\ldots,x_n))=1$
Kronecker delta
delta function
iff each $\epsilon_i=x_i,$ and otherwise is 0.

For $3t<n$ and any function $F,$
there exists a $t$-resilient protocol to compute $F$
in a constant number of rounds.  The message sizes may grow
exponentially, depending on the nature of $F.$

The protocol is trivial, given Lemma <ref> and a means to
compute $\delta$delta in constant rounds: in parallel,
secretly compute $\delta$
for all $(\epsilon_1,\ldots,\epsilon_n)$ values such that
$F(\epsilon_1,\ldots,\epsilon_n)\not=0,$ and then compute the secret linear
combination of the results using the publicly-known weights
$F(\epsilon_1,\ldots,\epsilon_n)$ as specified.

Define the normalization of $x$ to be $\norm{x}=1$ iff $x \not= 0,$ and
$\norm{0}=0.$  Then we have

\[
\delta((\epsilon_1,\ldots,\epsilon_n),(x_1,\ldots,x_n)) =
1- \norm{ \sum_{i=1}^n  \norm{\epsilon_i-x_i} ~~~ }
\]

But Theorem <ref> states that there is a constant-rounds
protocol for computing the extended multiplicative inverse of a secret.
Clearly, $\norm{x}=x \cdot x^{-1},$ for this extended inverse.  Then the
protocol to compute $\delta$ is simple: normalize each difference by
calling the protocol on $\epsilon_i-x_i;$ sum the results
non-interactively; normalize the sum; and subtract the result from 1,

An alternative but equivalent formulation arises from the following

Any function $F : E^n \rightarrow E$ has a canonical representation as a
polynomial $c_F$ of degree $n$ such that on $\set{0,1}^n,$
$c_F(x_1,\ldots,x_n) = F(x_1,\ldots,x_n).$  In particular, any function
$F : \set{0,1}^n \rightarrow \set{0,1}$ has such a representation as a
polynomial of degree $n$ over $E.$

Follows from simple algebra and the following definition:

\[
c_F(x_1,\dots,x_n) =
\sum_{(\epsilon_1,\ldots,\epsilon_n) \in \set{0,1}^n}
F(\epsilon_1,\ldots,\epsilon_n)  \cdot
\prod_{i=1}^n (1 - (x_i-\epsilon_i)(-1)^{\epsilon_i} )
\]

§ FORMAL PROOFS

Describing an interface is usually far more tedious and difficult than
giving a convincing argument that the information held by an adversary is
independent of the inputs of reliable players.  It should be remarked that
the protocol designer need not concern himself with the details of the
interface; given a protocol compiler and a list of subprotocols that can be
concatenated, the actual implementation of a protocol has nothing to do with
the specification of a interface for the protocol.  Thus the only purpose
of the following specifications are to prove the resilience of the protocol
and are irrelevant to the implementation.

§.§ Step By Step Simulation

In constructing messages from reliable players or reconstructing the state
of a newly corrupted player, it is essential to distinguish which portion
of the player's information is implicitly or explicitly determined by the
current view of the adversary, and which portion is completely unknown to
the adversary. In our protocols there are two extremes: either the
adversary already “knows” the value of a variable held by a reliable
player (as in the case of a piece distributed by a corrupted player), or it
“knows” nothing, in the sense that the variable is uniformly distributed
(e.g. over the set of field elements).  Thus the task of the
interface is easy, once it has determined which local variables have
already been fixed; it must simply choose the other local
variables according to the appropriate conditional distributions (fixed and
usually uniform).

There are many dependencies among the random variables describing the views
of the players and the adversary; therefore, we introduce a notation to
clarify the conditional distributions which the interface samples from when
interacting with the adversary.  The important point to note about each
variable is whether it is known (i.e. determined by a current view) or
hidden (i.e. unknown but distributed according to some known

(Compromised Information)
Let $T \subseteq [n] \cup \set{A},$ and let $\rho \leq r.$
A random variable $\rv(v_i,\rho)$
of player $i$ at round $\rho$ is
compromised by $T$ at round $r$
if there exists a function $f$ such that $f(\view_T^r) = \psi(v_i,\rho).$
We write this as $\view_T^r \vdash \rv(v_i,\rho).$

§.§ Data Structures and Local Variables

In order to examine the progressive states of each player and in order to
implement any of the protocols, we need to list explicitly the local
variables that make up each player's state.  The value of each variable is
a string representing a bit, a field element, or a message; if unassigned,
the value is $\Lambda.$  The local variables listed below are certainly
redundant to some degree:

* $x_i,$ its input.

* $a_i,$ its auxiliary input.

* $y_i,$ its auxiliary input.

* $\randfield_i = (\rho_{i1},\rho_{i2},\ldots),$
an array of generic values, some of which may represent secretly shared
values (e.g. wire values), other public information (e.g.
publicly known constants and other information), and other information
necessary to the particular protocol (e.g. information used to verify

* $\randbits_i = (b_{i1},b_{i2},\ldots),$
an array of random bits.

* $\vec{s} = (s_1,s_2,\ldots),$
an array of known values, some of which may represent secrets and others of
which may represent information necessary to the protocol (such as
additional information used to verify pieces).

* $\pieces_i = (\piece_1(s_1),\ldots,\piece_n(s_1);
\piece_1(s_2),\ldots,\piece_n(s_2); \ldots),$
an array of the pieces of all the secrets.  Player $i$ will know either one
of the pieces or all of the pieces of each given secret.

* $\disqual_i = (d_1,d_2,\ldots,d_n),$
an array of disqualifications.  $\disqual_i[j]=1$ if player $i$ believes
player $j$ to be corrupt; otherwise it is 0.

* $\globdisqual_i = (g_1,g_2,\ldots,g_n),$
an array of global disqualifications.  $\globdisqual_i[j]=1$ if player $i$
believes all reliable players have disqualified player $j.$  (This should
have the same value among all reliable players.)

* $\mess([n],i,1..R),$ messages from other players.

* $\mess(i,[n],1..R),$ messages to other players.

A state $q_i$ is specified by the vector

\begin{eqnarray*}
& (x_i,a_i,\randfield_i,\randbits_i,\vec{s}_i,\pieces_i,\disqual_i,
\globdisqual_i, &  \\
& \mess([n],i,1..R),\mess(i,[n],1..R)). &
\end{eqnarray*}

As in Chapter <ref>, <ref>, we use these as
labels to parametrize distributions in more detail.  That is, instead of
considering simply the distribution $\rv(q_i,r)$ on the state of player $i$
at round $r,$ we consider the distribution $\rv(\piece_i(s_1),r)$ on the
value of player $i$'s local variable $\piece_i(s_1)$ at round $r,$ the
distribution $\rv(\piece_i(s_2),r)$ on the value of player $i$'s local
variable $\piece_i(s_2)$ at round $r,$ and so on. The collection of random
variables is parametrized by $r$ and the set $\rvnames'$ of variable names
obtained from $\rvnames$ by replacing each $q_i$ in $\rvnames$ by the
individual labels listed above.

Our goal is to specify the distributions $\rvAA$ describing variables for
$\VSS$ and the distributions $\rvASB$ describing variables for $\VSS$
induced by $\interface$ in the $\idealname(\share)$ protocol and to show
that they are equal.  Some are not sampled by $\interface,$ and we denote
unsampled variable values by $\rvASB(v,r)=\notsamp.$
Implicit in the operation of an interface is the specification that
after each round of interaction with $A,$ $\interface$ sets
$\rvASB(v,r+1)=\rvASB(v,r)$ for each $v$ such that
$\rvASB(v,r) \not= \lambda.$

In each round we
describe corruptions and then rushed messages from $\tbar.$ After each
round of $\VSS,$ $\interface$ records messages from $A$ in
$\rvASB(\mess(T,\tbar,r),r)$ accordingly.
We give arguments along the way that $\rvAA(v,r)=\rvASB(v,r)$ for
sampled variables.

§.§ Proofs of Resilience

§.§.§ Verifiable Secret Sharing

Theorem <ref>
We would like to show that $\VSS \resilasFa \idealname(\share) \resilasFa
\vacuous.$  First we construct an interface $\interface$ from $\VSS$ to
$\idealname(\share).$  For clarity we refer to player $i$ in $\VSS$ and
to player $i_{id}$ in $\idealname(\share).$

The $\idealname(\share)$ protocol allows the dealer, $D,$ to supply pieces
to the host, who distributes them if they are properly interpolatable, but
otherwise sends   to all players.  The interface runs most of
$\VSS$ with $A$ before finishing the first round of $\idealname(\share).$

Remark.  The intuition that $A$ gains no information by
complaining and forcing $D$ to reveal pieces because $A$ knows them already
is formalized by $\interface$ having at a given stage in $\VSS$ set the
random variable $\rvASB(x,r)$ to some value that either has come from $A$
or has been generated by $S$ for $A$ in response to a corruption request.

If $A$ corrupts $D$ before it supplies secret $s,$ $\interface$ requests
$D_{id}$ be corrupted and supplies $A$ with $s.$  If $A$ requests $i$ be
corrupted, $\interface$ corrupts $i_{id}$ and returns the auxiliary input.

(V1)  If $D$ is corrupt, $\interface$ does nothing but record the
outgoing message of $A$ as $\rvASB(\mess(D,[n],1),1).$
$\interface$ chooses $\rvASB(\piece_i(s),1) \leftarrow \uniform(E)$
for all $i \in T,$ constructs

\[
\{ p_i(u) \leftarrow \unifpolyn(n,t,\piece_i(s)) \}
\]

\[
\{ q_i(v) \leftarrow \unifpolyn(n,t,0) \mid
(\forall j  \in T)  q_i(\omega^{j-1}) = p_j(\omega^{i-1}) \},
\]

and delivers these messages to $A.$  By Lemma <ref>,
the conditional distributions satisfy

\[\rvASB(\mess(D,i,1;(p_i(u),q_i(v))),1) =
\rvAA(\mess(D_{id},n+1,1;(p_i(u),q_i(v))),1).
\]

(V2)  If $A$ newly corrupts $D,$ $\interface$ corrupts $D_{id},$ sets

\[
\{ g(u) \leftarrow \unifpolyn(n,t,s) \mid
(\forall i \in T)  g(\omega^{i-1}) = \piece_i(s) \},
\]

sets for all $i \not\in T$

\[
\{ p_i(u) \leftarrow \unifpolyn(n,t,\piece_i(s)) \mid
(\forall j \in T)  p_i(\omega^{j-1}) = q_j(\omega^{i-1}) \},
\]

\[
\{ h(v) \leftarrow \unifpolyn(n,t,s) \mid
(\forall i \in T)  h(\omega^{i-1}) = q_i(0) \},
\]

sets for all $i \not\in T$

\[
\{ q_i(v) \leftarrow \unifpolyn(n,t,h(\omega^{i-1}) \mid
(\forall j \in T)  p_i(\omega^{j-1}) = q_j(\omega^{i-1}) \},
\]

and sets $\rvASB(\mess(D,i,1),1) = (p_i(u),q_i(v))$ for all $i \in T.$
Interface $\interface$ sends $A$ the view of $D$ using $x_D,$ $a_D,$

By Lemma <ref>
each of these distributions satisfies $\rvASB(x,1) = \rvAA(x,1)$
and is polynomial-time computable, being uniform over an easily computed set
of solutions determined by the conditions listed above.  This computation
in effect induces the variable $\rvASB(p(u,v),1) = \rvAA(p(u,v),1).$

If $A$ newly corrupts player $i$ we must consider whether $D$ is yet
corrupted.  If $D$ is corrupt, then all information held by $i$ is
known, in particular, $\rvASB(\mess(D,i,1),1).$
The interface corrupts $i_{id}$ to obtain $a_{id}$
(note that $x_{id}$ is nil)
and constructs $\view_i^1$ from these values.
It then provides $A$ with the view.
If $D$ is not corrupt, then $\interface$ must construct the
$(p_i(u),q_i(v))$ message that $D$ sent to $i$ in round (V1).

To generate rushed messages from nonfaulty players, if $D$ is nonfaulty
then $\interface$ sets $\rvASB(\mess^{\broad}(i,[n],2),2) = 0$
for all $i \not\in T,$ since a nonfaulty player will accept the
proper (but private) message from a nonfaulty dealer.
If $D$ is faulty, then its messages to nonfaulty players are
determined by $\rvASB(\mess(D,[n],1),1),$ and $\interface$
sets $\rvASB(\mess^{\broad}(i,[n],2),2)$ to be $0$ if the
message to $i$ describes polynomials of degree $t,$ and $\interface$
sets the variable to $1$ otherwise.  Clearly this is the same
probabilistic computation $\delta_i$ that each nonfaulty player
applies in (V2).

Now, if $A$ newly corrupts $i$ while $D$ is nonfaulty, $\interface$
generates $p_i(u)$ and $q_i(v)$ as in (V1), and returns them.  If $D$ is
already corrupt, $\interface$ uses $\rvASB(\mess(D,T,1),1)$ to determine
$p_i(u)$ and $q_i(u).$

To generate messages from nonfaulty players, $\interface$ does the
following.  For each $i\not\in T$ and $j \in T,$  the $p_i(w^{j-1})$
values sent by nonfaulty players are determined already by the values
sent to corrupt players, so $\interface$
sets $\rvASB(\mess(i,j,2;p_i(\omega^{j-1})),2) =
\rvASB(\mess(D,j,1;p_i(\omega^{j-1})),1).$

(V4)  If $A$ newly corrupts $D,$ corrupt $D_{id}$ and construct
$\rvASB(\mess(D,T,1..2),1..2)$  as before.  If $A$ newly corrupts $i,$
$\interface$ creates an earlier view as in (V3) and must then construct
incoming messages about $p_k(\omega^{i-1})$ in round (V3).
For each $k \in T,$ check if $k$ sends $i$ a proper
$p_k(\omega^{i-1})$ according to whether
$\rvASB(q_i(\omega^{k-1}),1) =
\rvASB(\mess(i,k,2;q_i(\omega^{k-1})),2).$
The former is fixed by previous computations of $\interface.$
Set $L(i,k)$ accordingly.
If $D$ is nonfaulty then set $L(i,k)=0$
for all $k \not in T,$
because all nonfaulty players send what $D$ sent them.
If $D$ is faulty but $k \not in T,$ use $\rvASB(\mess(D,k,1),1)$ and
$\rvASB(\mess(D,i,1),1)$ to determine whether $i$ complains.
This determines $\rvASB(L(i,k),2)$ for all $k,$ and $\interface$ supplies
it along with $a_i$ (obtained by corrupting $i_{id}$) to $A.$

To generate the broadcast messages from nonfaulty players, $\interface$
performs the same computation as the new corruption of $i$ just described.
It uses the vector $L(i,\cdot)$ as the broadcast value from $i\not\in T.$

The view of a newly corrupt dealer includes that generated according to
(V4) along with the broadcast messages $\rvASB(\mess^{\broad}(T,[n],4),4)$
and $\rvASB(\mess^{\broad}(\tbar,[n],4),4)$ generated by $A$ and
$\interface$ in round (V4).  The view of a newly corrupted $i$ is generated
as in (V4), also attaching the list of broadcast messages.

If $D$ is nonfaulty, all disputes involve at least one faulty player $i,$
so $\interface$ has already specified in
$\rvASB(\mu(D,i,1;p_i(\omega^{i-1}),1)$ the correct
value.  So $\interface$ sets $\rvASB(\mess(D,[n],4;p(i,j)),4)=
\rvASB(\mu(D,i,1;p_i(\omega^{i-1}),1).$   If $D$ is faulty, no messages
from nonfaulty players need be generated.

New corruptions of $D$ or player $i$ are treated as in (V5), and
$\interface$ adds on the messages broadcast by $D$ in (V5), whether
generated by $\interface$ or by $A.$

If $D$ is nonfaulty, every player $i\not\in T$ does not impeach $D,$ so
$\rvASB(\mess^{\broad}(i,[n],6;M(i)),6) = 0.$  Otherwise it is easy for
$\interface$ to compute whether player $i\not\in T$ impeaches $D$
from the values of $\rvASB(\mu(D,i,1),1)$ and
$\rvASB(\mu(D,[n],4),4),$ since these previous messages  from $D$ to $i$
have already been recorded (if not generated) by $\interface,$ and since
\rvAA(\mu(D,i,1),1)$ and
\rvAA(\mu(D,[n],4),4).$

New corruptions of $D$ or $i$ are treated as in (V6), adding the broadcast
impeachments from (V6) on the end of the views.

If $D$ is nonfaulty, impeachments come from faulty players only,
so $D$ will broadcast $(p_i(u),q_i(v))$ values that $\interface$
has already generated:

\begin{eqnarray*}
\rvASB(\mess^{\broad}(D,[n],7;M'(i)),7) & = &
\rvASB(\mess(D,i,1),7) \\
& = & \rvAA(\mess(D,i,1),7) \\
& = & \rvAA(\mess^{\broad}(D,[n],7;M'(i)),7)
\end{eqnarray*}

For $i\not\in T,$ $D$ broadcasts $M'(i)=0,$ of course.  If $D$ is faulty,
$\interface$ simply records $\rvASB(\mess^{\broad}(D,[n],7),7)$
as generated by $A.$

New corruptions are as in (V7), with the broadcast values
$\rvASB(\mess^{\broad}(D,[n],7),7)$ concatenated at the end.

If player $i$ is nonfaulty, $\interface$ checks whether
If so, it sets $\rvASB(\mess^{\broad}(i,[n],8),8)=0.$
Otherwise, it checks whether, for all $j$ for which $D$
broadcasts $(p_j(u),q_j(v)),$ the values agree with $i$'s
value $p_j(\omega^{i-1})$ as derived accordingly from
$\rvASB(\mess(D,i,1),8)$ or
or $\rvASB(\mess^{\broad}(D,[n],7),8),$
the choice depending on whether $i$ has complained before.
If so, $\interface$ sets $\rvASB(\mess^{\broad}(i,[n],8),8)=0,$
and otherwise sets it to $1.$

Finally, if $\rvASB(\globdisqual_i(D),8)=1$ for any $i\not\in T$
($\interface$ calculates this easily from
$\rvASB^{\broad}(\tbar,[n],8),8)$), then $\interface$
requests that the corrupted dealer $D_{id}$ send
$\Lambda$ in the ideal protocol.
The trusted host will supply each player with the output,
$(0,\rej).$  Otherwise, if the dealer $D$ is corrupted,
$\interface$ requests that $D_{id}$ send the pieces
that were finally accepted by nonfaulty players, and fills out
the list with values for corrupted players $i_{id}$ that provide
a polynomial of degree $t.$  These corrupted players will receive
those values but their outputs are considered to be $\Lambda,$
as described in Chapter <ref>.  The nonfaulty players
in $\idealname(\share)$ will output

This concludes the description of $\interface.$  We claim that for
every $r$ and every $v$ such that
$\rvASB(v,r) \not= \lambda,$
$\rvASB(v,r) = \rvAA(v,r).$
At each step, $\interface$ samples new variables $\rvASB(v,r)$
as a probabilistic function (sometimes even deterministic,
as when reporting values already broadcast) $f$ of earlier samples.
Each time, $\interface$ uses either:

* a previous output of $A;$

* uniform distributions based on Lemma <ref>;

* direct computation of a nonfaulty player on values already broadcast
or known by virtue of correct behavior of other nonfaulty players
(e.g. nonfaulty players do not impeach other nonfaulty

With the aid of Lemma <ref> and broadcast channel properties,
it holds that

\[
\rvASB(v,r+1) = f(\rvASB(v_1,r),\ldots,\rvASB(v_K,r)) =
f(\rvAA(v_1,r),\ldots,\rvASB(v_K,r)) = \rvAA(v,r+1)
\]

for some $K.$  In particular,
$\rvAA(\outfn(q_i),8) = \rvASB(\outfn(q_i),8)$ for all
$i$ and $\rvAA(q_A,8) = \rvASB(q_A,8),$ hence
$\ensAAlpha\protoIn =
\ensASBeta\protoIn.$

§.§.§ Multiplication

0.7in 0.4in 0.4in
0.4in 0.4in 0.4in
Fix $E=E(m,n)$ and $\omega.$

$(1 \leq i \leq n)$

$\{ p(u,v) \leftarrow \uniform( p \in E[u,v] \mid  p(0,0) = s,
p(u,v) = \sum_1^t \sum_1^t p_{ij} u^i v^j \}$

$D \rightarrow i:$
$(p_i(u),q_i(v)) = (p(u,\omega^{i-1}), q(\omega^{i-1},v))$

$(1 \leq i \leq n)$

$i \rightarrow [n]:$
degree $t$ $0$ $1.$

$(1 \leq i,j \leq n)$

$i \rightarrow j:$

$(1 \leq i,j \leq n)$

$L(i,j) = \left\{
\begin{array}{ll}
0 & \mess(j,i,3;p_j(\omega^{i-1})) =  \mess(j,i,3;q_i(\omega^{j-1})) \\
1 & \mbox{ otherwise }
\end{array}
\right.$

$i \rightarrow [n]:$

$(1 \leq i \leq n)$

$L'(i) = \left\{
\begin{array}{ll}
0 & \mess(i,[n],4;L(i,j))=0 \\
p_i(\omega^{j-1}) & \mbox{ otherwise }
\end{array}
\right.$

$D \rightarrow [n]:$

$(1 \leq i \leq n)$

$(\exists j)$ $\mess^{\broad}(i,[n],4;L(i,j))=1$

or  $\mess^{\broad}(j,[n],4;L(j,i))=1,$

and $\mess^{\broad}(D,[n],5;p_i(\omega^{j-i})) \not= $

$\mess(D,i,1; q_i(\omega^{i-1}))$

$M(i)=1$ $M(i)=0.$

$i \rightarrow [n]:$

$(1 \leq i \leq n)$

$M'(i) = \left\{
\begin{array}{ll}
0 & \mess(i,[n],6;M(i))=0 \\
(p_i(u),q_i(v)) & \mbox{otherwise}
\end{array}
\right.$

$D \rightarrow [n]:$

$(1 \leq i \leq n)$

$\mess^{\broad}(i,[n],6];M(i)) = 0$ or

$\mess^{\broad}(D,[n],7];(p_i(u),q_i(v)))$ is consistent

$\disqual_i(D)=0$  $\disqual_i(D)=1.$

$i \rightarrow [n]:$

$(1 \leq i \leq n)$

$t+1$ players disqualified $D,$

set $\globdisqual_i(D)=1.$

$Y_i=(0,\rej)$  $Y_i=(p_i(0),\acc).$

Protocol for dealer to verifiably share secret $s.$
See text for more details.

CHAPTER: TOLERATING A MINORITY OF FAULTY PROCESSORS

Democracy is the recurrent suspicion that more than half of the people
are right more than half of the time.

E. B. White, The Wild Flag

The methods of [28, 39] and even the far more efficient methods
we have presented in Chapter <ref> allow faults in at most a third
of the network ($3t<n$).  Perfect privacy is not achievable with higher fault
tolerance for even some simple functions like AND [28] (but see
Chapter <ref> for a characterization of functions computable with
perfect privacy at high, passive fault-tolerance levels).

The natural question to ask, though, is whether higher fault tolerance is
possible if the assurances of security and reliability need not be
absolute.  We show that, allowing for a negligible chance of error, $2t<n$
can be achieved.  That is, as long as only a minority of the processors are
faulty, we can construct protocols to compute any function reliably and
securely.  For larger numbers of faults, it becomes impossible for the
players even to share a secret, which does not immediately imply a negative
result but gives a strong intuition as to why higher fault-tolerance is
generally impossible without making other assumptions about the network

Notice that the major problems with extending the methods of
[28, 39] to $2t<n$ are that verifiable secret sharing fails
and that the specific techniques for the ABC Problem fail.

Rabin [106] made initial and significant
progress in the direction of improving
the fault bounds from $3t<n$ to $2t<n$ by demonstrating a method for
verifiable secret sharing for $2t<n,$ using a broadcast network.
Earlier methods for verifiable secret sharing with a faulty minority
required cryptographic assumptions [42].
The extension to performing computations for $2t<n,$ however,
remained open until this work.

We give a new and efficient method to solve the ABC problem when
secret addition is possible, for $2t<n.$
Our techniques utilize verifiable secret sharing for $2t<n,$ and
allow the field used for secret sharing to be of exponential size.
Ben-Or [107] and Kilian [85] have
independently developed methods to
tolerate a faulty minority, based on standard ideas of boolean circuit
simulation.  Their methods require that the field used for secret sharing
be of
polynomial size, which restricts the efficiency of their solutions.

There exists a protocol    that is $t$-resilient against
against dynamic Byzantine adversaries for $2t \leq n.$

Because we can simulate large-field arithmetic operations quickly and
directly while alternative methods use bit-simulations or small-field
arithmetic, our protocols have the practical advantage of using far fewer
rounds of communication for many natural functions.  Joined with the
techniques of Chapter <ref>, our techniques use tremendously fewer
rounds of interaction.  The bit-simulation techniques of
[107, 85], on the other hand, are incompatible with reducing
rounds through the arithmetic circuit reductions of Chapter <ref>
since they require the added cost of simulating arithmetic operations by
bitwise Boolean operations.

As before, our methods are secure against adversaries with unbounded
resources, while at the same time requiring only polynomial time to

We shall first describe a modification of the solution in [106]
for verifiable secret sharing, show how to add secrets, and then give
our solution to the ABC problem when $2t<n.$  The framework of
[28, 39] can then be applied, using these more resilient
subprotocols to support the share-secrets-create-secrets paradigm.

Assumptions made in this chapter.  The network is complete,
with private lines, broadcast lines, $n$ processors,
and at most $t < \frac{n}{2}$ Byzantine faults, chosen dynamically.
The protocols are information-theoretically secure with high probability,
or in other words, the results are statistically resilient.  No unproven
complexity-theoretic assumptions are made.

§ VERIFIABLE TIME-RELEASE MESSAGES

There is a long history of solutions for VSS under various
unproven assumptions.  We
wish to avoid unproven cryptographic assumptions and to tolerate $2t<n.$ We
shall utilize a method for VSS for $2t<n$ very similar to that given by
[106], but somewhat more convenient and efficient.  Briefly, it uses
Shamir's method for sharing a secret, and requires that each piece be
reshared using a weak form of sharing.  The weaker form of sharing includes
information called “check vectors,” which allow verification of the
pieces.  Our modification of the protocol is a new method for constructing
check vectors.  For completeness, because formal proofs of
[106, 107] have not appeared, and
because we use different subroutines,
we shall present the essential details of [106, 107] but
we refer the reader to that work for a deeper discussion.

The verification property of Rabin's scheme relies on a subprotocol for
what we call Verifiable Time-Release Messages.

We consider three players, a sender S, a receiver R, and an intermediary I.
The sender would like to give a secret bit to the intermediary, who will
pass it on at a later time to the receiver.  The receiver must be able to
detect any tampering on the part of the intermediary.  At the same time,
the intermediary should know whether the information given him will in fact
satisfy the receiver at the appropriate time.  He must therefore be able to
check the behavior of the sender during the initial part of the protocol.

Rabin [106] provides an elegant way to satisfy these properties
in a manner similar to secret sharing with threshold 1.  Her
idea involves generating nonzero random numbers $u$ and $v$ $\mod p$ and
setting $w=b+uv.$ The receiver gets $(v,w)$ while $I$ gets $(b,u).$ When
$I$ passes the value on to R later, he sends $(b,u),$ and R checks that
$w=b+uv.$ In order to convince R of an incorrect value, the intermediary
must change $u$ correctly, which he cannot do with non-negligible
probability.  Checking that the sender is correct uses a cut-and-choose
idea, which we shall use below.

We present a simple alternative with the nice property that
no multiplications are necessary.  In terms of polynomial-time
algorithms, this makes no difference, but in terms of actual
implementations, multiplications over a finite field are
considerably more expensive than additions.
Our approach is derived from work on a
different problem with Feigenbaum and Shoup [16].

If S and R were to share a one-time pad (a private sequence of random
bits), then how may S send a secret bit to R via another player I?  Player
I might change some of the bits.  Our simple solution uses $3k$ bits of the
one-time pad and ensures that tampering is detected with probability
$1-2^{-k}.$  See Figure <ref>.  Intuitively, for I to
change the bit $b$ without detection, it must guess the exact sequence of
bits $\alpha(1),\ldots,\alpha(k),$ which it can do with probability at most

Phase I.

S reads $\set{(\alpha(i),\beta_0(i),\beta_1(i))}_{i=1..k}$
from the one-time pad.

$(1\leq i \leq k)$  S:

$\gamma_0(i) \leftarrow \beta_0(i) + b \cdot \overline{\alpha}(i)$

$\gamma_1(i) \leftarrow \beta_1(i) + b \cdot          {\alpha}(i)$

$M_b \leftarrow \set{(\gamma_0(i),\gamma_1(i))}_{i=1..k}.$

$S \rightarrow I:$

Phase II.

$I \rightarrow R:$

Protocol for S to send a bit $b$ to R via player I.
Note that addition may be either modulo two, if the $\alpha$ and
$\beta$ values on the pad are bits, or it may be addition over
a finite field, if the $\beta$ values are field elements.

We use this verifiable one-time pad to construct a verifiable
time-release scheme
time-release scheme!verifiable
as follows.  Roughly speaking, the sender sends the
one-time pad privately to R, and sends the message $M_b$ to I, who holds
onto it until the time it should be released.  The one-time pad serves
as a check vectorcheck vector,   a sequence
of bits used to check the accuracy of the secret held by I.
The property that the
intermediary is convinced that R will accept the message later on must also
be satisfied, and we now turn our attention to that problem.

As in [106], we use a cut-and-choose method.  Instead of generating
$k$ $(\alpha,\beta_0,\beta_1)$ triples, generate $2k$ of them.  Half of
these will be revealed to I by R so that I can check for misbehavior.  In
order for S to cheat undetected, it must misbehave on exactly that half of
the triples that R does not immediately send to I.  Notice that $I$
learns $b$ upon receiving a single $(\alpha,\beta_0,\beta_1)$ triple.  To
keep $b$ secret from $I,$ the sender simply splits $b$ into two random bits
as $b=b_I \oplus b_R,$ and gives $b_I$ to $I$ and $b_R$ to $R.$

The protocol is detailed in Figure <ref>.  If $M$ is a message
that one party is supposed to send to another, we denote by $M'$ the
message it actually sends.

Intuitively, if S attempts to cheat, it must guess in advance the exact
set of indices $i(1),\ldots,i(k)$ that R selects at random, and it must
behave properly on that list but must cheat on every other row of the
table.  The chances of this are certainly at most $2^{-k}.$

0.5in 0.5in 0.7in 0.5in 0.5in 0.5in 0.5in
Phase I.

$S$ computes:

$b_I \leftarrow \uniform(\set{0,1});$  $b_R \leftarrow b \oplus b_I.$

$S$ computes $(i=1..2k):$
$\{(\alpha(i),\beta_0(i),\beta_1(i))\} \leftarrow \set{0,1}^{3}$

$\gamma_0(i) = \beta_0(i) \oplus b_I \cdot \overline{\alpha}(i)$

$\gamma_1(i) = \beta_1(i) \oplus b_I \cdot          {\alpha}(i)$

$S \rightarrow R:$

$b_R; \set{(\alpha(i),\beta_0(i),\beta_1(i))}_{i=1..2k}.$

$S \rightarrow I:$

$b_I; \set{(\gamma_0(i),\gamma_1(i))}_{i=1..2k}.$

$I$ generates:
$i(1)..i(k) \in_R \set{1,\dots,2k}$ such that

$i(j) \not= i(j')$ for $j \not= j'.$

$I \rightarrow R:$

$R \rightarrow I:$

there exists $j$ such that

$\gamma'_0(i(j)) = \beta''_0(i(j)) \oplus b_I
\cdot \overline{\alpha''}(i(j))$

$\gamma'_1(i(j)) = \beta''_1(i(j)) \oplus b_I
\cdot          {\alpha''}(i(j))$

let $I'=\rej$ let $I'=\acc.$

$I \rightarrow S,R:$

Phase II.

$I \rightarrow R:$

$b_I, \set{(\gamma'_0(i),\gamma'_1(i))}_{i=1..2k}.$

If there exists $i$ such that

$\gamma'_0(i) = \beta''_0(i) + b_I \cdot \overline{\alpha''}(i)$

$\gamma'_1(i) = \beta''_1(i) + b_I \cdot          {\alpha''}(i)$

then let $R=\rej$ else let $R=\acc.$

Protocol for S to send a bit $b$ to R via player I, who holds on to the bit
before passing it on.  If $M$ is a message that the protocol specifies to
send, then $M'$ denotes the message actually sent.
Note that $\oplus$ may denote field addition instead of exclusive or,
in which case the $\beta$ values
are instead selected uniformly at random from the field.
Using field addition is conducive to adding the unreleased
values together without revealing them.

§.§ Simulating the Time-Release Scheme

No formal proof of the techniques used in [106] has appeared to
date, so we must include a proof for completeness.

Protocol $\vertimerel$ is exponentially
$2$-resilient against Byzantine adversaries.

The ideal protocol $\idVTR$ is as follows.  In Phase I,
the sender $S$ sends two bits, $b_I$ and $b_R,$ to the host.
The host sends $b_i$ to $I$ and $b_R$ to $R$ if it indeed received
two bits; otherwise it sends .  Then, $I$ and $R$ send
a 0 to the host to indicate they wish to participate, and the host
passes on either $0$ or   to $I$ and $R$ to indicate whether
they chose to participate.  In Phase II, $I$ again sends 0 to indicate
it wishes to reveal the value, and the host sends $b_i$ to $R,$ or
it sends   if $I$ supplied a nonzero value.

The simulator does the following.  For corruptions before round
(VTR1), it corrupts the corresponding player in $\idealname(VTR)$
and returns the inputs to $A.$  To generate the message from honest
$S$ to corrupt $R,$ the interface generates $6k$ random field elements
and sets $b_R$ by corrupting $R_{id}$ in $\idealname(VTR)$ after it receives
$b_R.$  To generate the message from honest $S$ to corrupt
$I,$ the interface generates $2k$ random field elements
and sets $b_I$ by corrupting $I_{id}$ in $\idealname(VTR)$ after it receives
If both $R$ and $I$ are corrupt, then the interface corrupts them
in $\idealname(VTR)$ to obtain $b_I$ and $b_R,$ calculates
$b=b_I\oplus b_R,$ and performs the computation of $S$ to generate
the $\alpha, \beta, \gamma$ tables.  If $S$ is corrupt, the interface
obtains its two messages, checks to see if they are possible
(by solving for $\gamma_0,\gamma_1$), and if not, causes $S_{id}$ to
output $\Lambda.$  Notice that whereas
$\rvAA(\mess(S,\{I,R\},1) = \rvASB(\mess(S,\{I,R\},1),$
the resulting distribution on final player outputs in $\idealname(VTR)$
will be only exponentially indistinguishable from those in
$\vertimerel,$ because  with probability at most
$2^{-k},$ $S$ will cheat undetected in $\anglebrack{A,\vertimerel}.$
In that case, because the players in $\idealproto(VTR)$ reject $S,$
their outputs are different.  But by Lemma <ref>, we
may use a probabilistic function that differs exponentially little
from the “proper” one, and the net result is exponentially close.

New corruptions are easy to specify by solving the equations
$\gamma_0(i)=\beta_0(i) + b \cdot \overline{\alpha}(i)$ and
$\gamma_1(i)=\beta_1(i) + b \cdot {\alpha}(i)$ using information
from corrupting a player in the ideal protocol or from the variables
sampled already in (VTR1).

If $I$ is nonfaulty whereas $R$ is faulty, then the interface simply generates
$i(1),\ldots,i(k)$ randomly as specified and supplies them to $A.$
If $I$ is faulty and sends an improper list, then the interface specifies
that $I_{id}$ send $\Lambda$ to the trusted host to indicate
lack of participation.  The distributions on outputs of
$R$ and $R_{id}$ will be identical, namely both will indicate .

If $R$ is nonfaulty whereas $I$ is faulty, then the interface does one
of two things.  If $S$ is already corrupted, it uses the values
of $\alpha,\beta_0,\beta_1$ already sent by $A.$  If $S$ is not corrupt,
the interface nevertheless knows $b_I$ and
the values of $\gamma_0$ and $\gamma_1$
held by $I,$ so it generates the $k$ values of $(\alpha,\beta_1,\beta_2)$
by selecting $\alpha$ uniformly at random and solving for $\beta_0$
and $\beta_1.$  It is not hard to see that this is the correct
conditional distribution given the values of $\gamma_0$ and $\gamma_1,$
if $S$ and $R$ are not corrupt.

If $I$ is faulty, the interface does nothing.  Otherwise,
if $I$ is nonfaulty, and $S$ is faulty,
the interface can calculate from the current history
whether $I$ detects if $S$ has cheated, and it sets
$\rvASB(\mu(I,\{S,R\},4),4)$ accordingly.  If $I$ does detect
cheating then the interface requests that $S_{id}$ send $\Lambda$
to the trusted host, in which case the output of nonfaulty players
in $\idealname(VTR)$
will have a distribution exponentially indistinguishable from those
in $\rvAA.$

If $I$ is nonfaulty and $R$ is faulty, then the interface has
a record of what $S$ sent to $R$

In order to demonstrate the resilience of the time-release scheme, we must
demonstrate a simulator.  The task is not difficult but requires
case-by-case analysis.  We consider 8 possibilities corresponding to
whether or not S, I, and R are corrupted (bad or good) respectively.
First let us assume the adversary is static, and later we examine how to
extend our simulator to handle a dynamic adversary.

todo: fill in cases – easy

Case GGG.
Nothing to simulate.

Case GGB.

Case GBG.

Case GBB.

Case BGG.

Case BGB.

Case BBG.

Case BBB.

In the VSS
secret sharing!verifiable
method of [106], all players act both as intermediaries
and recipients for pieces of the secret $u.$ Each piece $\piece_i(u)$ of
$u$ is given to an intermediary $i,$ and check vectors $s_j(\piece_i(u))$
are sent out to every other processor $j.$ At reconstruction time, the
intermediaries $i$ broadcast their check vectors $\vec{s}(\piece_i(u)),$
which include $\piece_i(u).$ Each player, acting as a recipient,
reconstructs $u$ using the pieces he concludes are accurate.

(after T. Rabin [106])
There exists a VSS protocol for $2t<n$ that is $t$-resilient.

expand, list, prove

§ ADDITION OF SECRETS

It is possible though not trivial to extend the VSS method given above
to a method for linearly combining secrets.

Say that $u$ and $v$ were shared using polynomials $f(x)$ and
$g(x),$ respectively.
Let $h(x)=af(x)+bg(x)+c;$ then $h(0)=af(0)+bg(0)+c =w.$
Sums of the pieces are pieces of the sum;
Each player $i$ uses

\[
\piece_i(w) = a \cdot \piece_i(u) + b \cdot \piece_i(v) + c
\]

as his piece of $w.$

In order that $w$ be a verifiable secret according to the VSS protocol,
each $\piece_j(w)$ must be reshared in a weak fashion.  This involves
the use of check vectors for the pieces of $h(j).$
Each player $i$ holds pieces of every other
player's pieces, $\piece_i(\piece_j(u))$  and
He sets

\[
\piece_i(\piece_j(w)) =
a \cdot \piece_i(\piece_j(u)) + b \cdot \piece_i(\piece_j(v)) + c.
\]

The only remaining part of the VSS structure is the set of
check vectors for the pieces $\piece_j(\piece_i(w)).$
Since player $i$ knows $\piece_i(w),$ he creates and distributes new
check vectors for the pieces of this value.  The other players check the
correctness of his vectors using the protocol specified in
the VSS scheme [106].

Compute $w = au+bv+c.$

* Set

\[ \piece_i(w) = a \cdot \piece_i(u) + b \cdot \piece_i(v) + c. \]

* For each $j,$ compute pieces of the pieces:

\[
\piece_i(\piece_j(w)) =
a \cdot \piece_i(\piece_j(u)) + b \cdot \piece_i(\piece_j(v)) + c.
\]

* Choose new check vectors
for $\piece_j(\piece_i(w))$ for all players $j\not = i,$
and participate in their verification,
as per the VSS protocol.

* Receive check vectors for other pieces $\piece_i(\piece_j(w))$
and participate in their verification, as per the VSS protocol.

Protocol for linear combinations of secrets.
(Code for processor $i.$)

The protocol is resilient
because each of its steps is either a non-interactive computation
of a robust and private representation of some secret value,
or an application of a subprotocol for VSS that is itself resilient.
It is clear that players who deviate from the protocol cannot create
convincingly false check vectors with probability
exceeding some $\frac{1}{2^{k_1}},$ as determined by
the security parameter $k_1$ of the VSS protocol.
In this case, an interface would fail to be able to provide a
correct argument, since the adversary would learn information
to which it is not entitled, and the interface would need to
corrupt additional players to obtain that information.
The net weight of these events is exponentially small, however.
In fact, the only undetectable misbehavior is the possible
choice of acceptable check vectors

according to an inappropriate
This is, however, easily dealt with by an interface, which
needs merely record what the adversary specifies;
the interface need not itself generate these distributions.
Note that nonfaulty players' behavior is independent
of how the faulty players generate check vectors, even
acceptable ones.

§ MULTIPLICATION OF SECRETS

The protocol for multiplication of secrets is more complicated;
the key new idea is a method for giving a proof that the
product of two secrets is a third.  In fact, the ability to
prove products of secrets is the basis for achieving high
fault-tolerance in all of the results of this paper.

The protocol we shall present relies on a protocol for addition
of secrets.

Our solution follows a few brief steps (cf. [28]).
As before,
let $u$ and $v$ be shared using $f(x)$and $g(x).$
Each player $i$ secretly shares the value $f(i)g(i)$ and
“proves” that he has in fact shared this value
(see <ref>).
If his proof fails, he is disqualified (see <ref>).
From the collection of secret products determines
the polynomial $h(x)=f(x)g(x),$
of degree $2t$ and free term $uv.$
Using a protocol to add a random polynomial
of degree $t+1$ and free term 0
and then to truncate the polynomial to degree $t$
(see <ref>),
each player $i$ is supplied with
the value $h(i)$ for the resulting polynomial
$h(x)$ of degree $t$ and free term $uv.$
Figure <ref> describes the protocol.

* Secretly share $h(i)=\piece_i(u) \piece_i(v).$

* Run the protocol to prove that player $i$ shared this

* Receive pieces $\piece_i(h(j))$ from each player $j \not= i.$

* Participate in the protocol for $2t<n$ to verify that
player $j$ shared the correct value.

* Run the protocol using $h(i)$ to obtain a
piece $\piece_i(w)$ of a random, degree $t$ polynomial
whose free term is $w.$

Protocol to multiply two secrets.
(Code for processor $i.$)

§.§ Verifiable Multiplication

In order to accomplish the resilient verifiable sharing of $f(i)g(i),$
we must provide a solution to the ABC problem when $2t<n.$
In fact, we describe a new method that shows that, if secret addition
is possible, then multiplication is possible, for $2t<n.$

Given a protocol for the ABC problem, Alice will be able to
prove to the network that the new secret which she shares
is indeed $f(i)g(i).$

(ABC Lemma.)ABC Lemma
If there exists a $t$-resilient protocol for linear combinations
of secrets, then
there exists a $t$-resilient protocol to solve the ABC problem.

The protocol is exhibited in Figure <ref>.
First, an overview:
In the first phase,
Alice shares several triples of secrets $({\cal R},{\cal S},{\cal D})$
satisfying a simple equation
(of the form ${\cal D}=(a+{\cal R})(b+{\cal S})$),
which will be used to ensure that Alice does not misbehave.
In the second phase,
the players select and reveal combinations of some of these triples in order
to confirm that every triple satisfies the simple equation.
Finally, each unrevealed triple of secrets gives rise to
a simple linear combination
of secrets that should equal the desired product $ab.$
The third phase checks that the linear combinations are consistent.

Let ${k_0}$ denote a security parameter; the chance of incorrectness
will be bounded by $\frac{1}{2^{k_0}}.$
For simplicity we take ${k_0}>n$ and ${k_0}$ a power of two.

* Let $a$ and $b$ be verifiably shared.

* Alice verifiably shares $c = ab.$

* Alice shares secrets $r_1,\dots,r_{2{k_0}}$ and $s_1,\dots,s_{2{k_0}}$
chosen uniformly at random over the field $E.$

* For $j = 1,\dots,2{k_0},$ Alice computes $d_j = (a+r_j)(b+s_j),$
and shares $d_j.$

* The network confirms with high probability that each
$d_j = (a+r_j)(b+s_j):$

* For $i = 1,\dots,{k_0},$ the network selects a random index
$j_i$ by having each player select a random secret $\mod (2{k_0}+1-i),$
sharing it (over fields of characteristic $p$ such that
$p \mid 2{k_0}+1-i,$ so that the distribution is uniform), and
then computing the sum.

* Let $Y = \set{j_1,\dots,j_{k_0}}.$

* For all $j \in Y,$ run the protocol on $(a,r_j)$
to obtain the sum $a+r_j.$

* For all $j \in Y,$ run the protocol on $(b,s_j)$
to obtain the sum $b+s_j.$

* For all $j \in Y,$ reconstruct $a+r_j,$ $b+s_j,$ and $d_j.$
Disqualify Alice if any of the $d_j$ are not equal to

* The network confirms that $c$ matches the product $ab.$

* For all $j \not \in Y,$ reconstruct the values $r_j, s_j.$

* For all $j \not \in Y,$ compute

\[  c_j  =  c - d_j + as_j + br_j + rs  \]

* For all $j \not \in Y,$ reconstruct $c_j.$

* If any $c_j \not= 0,$ disqualify Alice.

ABC problem
Protocol to prove that the product of two secrets is a third secret.
(Code for Alice and network.)

Now let us consider the protocol in more depth.
If Alice is honest,
all of the sums $(a+r_j)$ and $(b+s_j)$ are independent of
$a$ and $b,$ since $r_j$ and $s_j$ are uniformly
random field elements.  The products $d_j$ are also independent
of $a$ and $b.$  The choice of ${k_0}$ indices $j_1,\dots,j_{k_0}$ to check
is independent of $a$ and $b,$ given that any one player in the
system is honest and shares uniformly random numbers.
The partial views obtained by faulty players during the addition protocols
are independent of the good players' inputs.

Finally, since Alice is honest, $d_j = (a+r_j)(b+s_j) = c + as_j+br_j+rs,$
so $c_j=0$ always.
Therefore, the set of messages are $t$-wise
independent of $a$ and $b,$
and messages from nonfaulty to faulty players are easily generated
accurately by an interface.

We would like to show that the chance that $c \not = ab$ without
Alice's being detected is smaller than $\frac{1}{k_0}.$
We shall show that she must behave properly on exactly the indices
in $Y$ and she must misbehave on all the others.
Let $X$ be the set of indices $j$ for which Alice shares $d_j$ correctly,
that is, for which Alice shares $d_j$ having the value $(a+r_j)(b+s_j).$
The set $Y$ of indices chosen by the system must be
a subset of $X,$ or else Alice's misbehavior is detected
for some $j \in Y \backslash X.$
The remaining indices $j \not \in Y$ must all satisfy
$c_j = c - d_j + as_j + br_j + rs = 0$
or else Alice is caught.
If $c \not= ab$ (Alice is cheating),
none of the indices $j \not \in Y$ is in $X.$
Hence $X=Y,$ and
since $Y$ is chosen randomly after Alice has shared all her secrets,
the probability that Alice can cheat without being detected
is no more than $\frac{1}{2^{k_0}}.$  An interface fails to
produce a correct output
an exponentially small amount of the time, hence the overall
distributions are exponentially indistinguishable.

§ THE PROTOCOL COMPILER FOR FAULTY MINORITY

At this point we have described all the tools necessary to
create a multiparty protocol to evaluate any circuit $C_F$ for
$F(x_1,\dots,x_n)$ privately, tolerating $t< \frac{n}{2}$ faults.
The protocol is the same as that of protocol (Figure <ref>), with the new and protocols of this
chapter substituted for the ones called by that specification.  The
disqualification procedure is different, as well: after each cycle of
evaluating gates, a recovery procedure is initiated if faults have been

Let $\tau$ be the number of faults.  The $(n-\tau,t-\tau)$ recovery
protocol uses a stripped-down version of the protocol to reduce
the degrees of each polynomial being used by $\tau.$ The remaining players
in fact reconstruct each piece of the various secrets held by the
$\tau$ faulty players, using straightforward linear combinations of
existing pieces, as seen by the following argument.  Without loss of
generality take the set of reliable players to be $1,\ldots,t+1.$ Then the
LaGrange interpolation gives

\[
p(j) = \sum_1^{t+1} L_i(j) p(i),
\]

so that the piece $\piece_j(s) = p(j)$ is easily computed as a weighted sum
of secrets.  That is, each player verifiably reshares his pieces and then
the system computes the given linear combinations.  If more faults occur
then the process is restarted.  Notice that the players do not
reconstruct all the information held by the faulty players; instead, they
reconstruct pieces of secrets held by the faulty processor.  This
bears no relation to the value of that faulty player's input; such
information is not revealed.

Now, each reliable player has learned the pieces held by disqualified
players.  It now adjusts the value of its own pieces through a simple
computation in order to obtain pieces of the original secrets, but shared
with polynomials of degree $t-\tau.$ For concreteness, assume only one
player has been disqualified.  Say that secret $s$ is shared via polynomial
$p(u)=\sum_0^t a_t u^t.$ Player $i$ has $\piece_i(s)=p(\alpha_i).$ The
newly publicized piece of the disqualified player is $p(\alpha_j)=\beta.$
Let $m_1(u)=\prod_{i\not=j} (u-\alpha_i),$ $m_2(u)=(u-\alpha_j),$ and
$M(u)=m_1(u) m_2(u).$ Define $g(u) = f(u) \mod m_1(u);$ then by the Chinese
Remainder Theorem,

\begin{eqnarray*}
M_1(u) & = & [m_2(u)^{-1} (\mod m_1(u))] \cdot m_2(u) \\
M_2(u) & = & [m_1(u)^{-1} (\mod m_2(u))] \cdot m_1(u) \\
f(u) & = & M_1(u) g(u) + M_2(u) \beta   \hspace{0.3in} (\mod M(u))
\end{eqnarray*}

Then player $i$ computes its new piece of $s$ as:

\[
g(\alpha_i) = [f(\alpha_i) - M_2(\alpha_i) \cdot \beta ] / M_1(\alpha_i).
\]

When using or revealing this value, the verification information is easily
adjusted since it verifies the $f(\alpha_i)$ value, which is itself easy
to recover from the $g(\alpha_i)$ value since $M_1,$ $M_2,$ $\alpha_i,$ and
$\beta$ are publicly known.

§ PROOF OF RESILIENCE

CHAPTER: MULTIPARTY ZERO-KNOWLEDGE PROOF SYSTEMS

In this chapter, we generalize the concept of a zero-knowledge proof
systemzero-knowledge proof in two ways.  First, we consider
proofs that some condition holds on secretly shared values.  One player,
the prover , knows the values of a collection of secrets,
and through an
interaction with the rest of the network, it proves that a given predicate
$\scp$ holds on those secrets.  Second, we consider efficient interactive
proofs of general theorems, where secrecy is not the goal.  Rather, the
prover must prove a given theorem (i.e. prove membership in a
language) to one or more verifiers.  Instead of making unproven
cryptographic assumptions to guarantee zero-knowledge, we utilize the
presence of a majority of trusted players.  No single player need be

Assumptions made in this chapter. The network is complete, with
private lines, $n$ processors, and at most $t < \frac{n}{2}$ Byzantine
faults, chosen dynamically.  The protocols are unconditionally secure with
high probability; the results are statistical zero-knowledge (with high
probability no extra information is revealed).  There are two
distinguished parties, a prover, which is either polynomial-time or
polynomial-space bounded, and a verifier, which is either unbounded
or polynomial-time bounded.

§ ZERO-KNOWLEDGE PROOFS ABOUT SECRETS

In Chapter <ref> we considered the ABC Problem: Alice, the prover,
must prove that $c=ab,$ where $a,b,$ and $c$ are secrets.  Here, we extend
Lemma <ref> to demonstrate that a player may prove that a given
predicate $\predicate$ holds on $m$ shared secrets $v_1,\dots,v_m,$
revealing no additional information.  In a sense, this is analogous to the
two-player problem of giving zero-knowledge proofs that a predicate holds
on committed bits [84]. Here, we consider values shared among a
network instead of committed bits, which have slightly different
properties.  For example, though committed bits are secret and
unchangeable, they cannot be added together directly.  Since most secure
multiparty protocols are based on threshold schemes like secret sharing,
proofs about shared values are an important tool.

Let $\predicate$ be a function on $m$ variables over the field $E$ and let
$C_{\predicate}$ be an algebraic circuit over $E$ which computes
$\predicate;$ note that any boolean predicate on boolean inputs is easily
modelled using arithmetic over $E.$

Let $\prover$ and $\verifier$ be distinguished parties in the network.  We
consider $\prover$ or $\verifier$ to be “cheating” if they are corrupted
by an adversary $A.$

Let the prover's input be $x_{\prover}=(v_1,\dots,v_m,w)$
and let all other $x_i=0.$
We define a function whose output is known only to the verifier:
$F_i(x_1,\dots,x_n) = 0$ if $i \not= \verifier,$ and

\[
F_{\verifier}(x_1,\dots,x_n)  =
\left\{
\begin{array}{rl}
1 & \mbox{ if } x_{\prover}=(v_1,\dots,v_m,w) \mbox{ and }
w = \predicate(v_1,\dots,v_m) \\
0 & \mbox{ otherwise. } \\
\end{array}
\right.
\]

Without regard to zero-knowledge, a simple proof system is trivial:
simply reconstruct all the secrets and check if

A protocol $\Pi$ is a $(n,t)$ multiparty zero-knowledge
interactive proof system
!multiparty zero-knowledge
interactive proof system on secrets
zero-knowledge proof
multiparty zero-knowledge
interactive proof system!on secrets
on secrets for $\predicate$ if it
is a $t$-resilient $n$-player protocol for the function $F_{\predicate}$
defined above.

The terms statistical and computational apply according
to whether the protocol is statistically or computationally resilient.
We call such a protocol a , for short.

Theorem <ref>
tells us that there exists a   for any function $\predicate:$
simply compute $F_{\predicate}$ using the protocol.

The purpose of this section, aside from defining the concept of proof
systems with many parties, is to introduce a protocol which allows a direct
proof system which is far more efficient than simulating $C_{\predicate}.$
Simulating a circuit level by level (or even $(\log n)$-slice by slice) is
an expensive undertaking.  We can take advantage here, however, of the fact
that the prover already knows the results of all of the gates.  The prover
shares the results of each and every gate, reducing the task of the
verifier to checking that each shared result is correct.  In other words,
the system does not need to evaluate the circuit layer by layer, but rather
only to verify that the collection of secrets representing the output
values of each gate is correct.  This verification requires only a local
examination of the secret inputs and secret output of each gate, an
operation which can be performed simultaneously for all the gates.
Figure <ref> details the protocol.

$0 \leq l \leq {\tt depth}(C_{\predicate})$
$1 \leq j \leq {\tt width}(C_{\predicate})$ :

shares the output of each gate $g_{lj}$ as a secret, $w_{lj}.$

$0 \leq l \leq {\tt depth}(C_{\predicate})$
$1 \leq j \leq {\tt width}(C_{\predicate})$ :

the network secretly computes $u_{lj}$ as follows:

$g_{lj}=(\times)$ run to compute

$u_{lj} = g_{\inputgates_1(g_{lj})} \cdot g_{\inputgates_2(g_{lj})}.$

$g_{lj}=(+,a_0,\ldots,a_m)$ run to compute

$u_{lj} = a_0 + \sum_{j=1}^m g_{\inputgates_m(g_{lj})}.$

$0 \leq l \leq {\tt depth}(C_{\predicate})$
$1 \leq j \leq {\tt width}(C_{\predicate})$ :

reveal $u_{lj}$ to .

If all $u_{lj}=0,$ outputs accept, else it outputs reject.

Protocol to prove $w = \predicate(v_1,\dots,v_m).$
predicate!proof of

The results of Chapter <ref> give the following:

Let $\predicate$ be a family of predicates and let $F_{\predicate}$ and
$C_{\predicate}$ be as described above.  For $2t<n,$ protocol is
a statistical $(n,t)$-  for $\predicate.$ It runs in constant rounds
and has message complexity polynomial in $(n,m,k,C_{\predicate}).$ of

When $3t<n,$ the results of $[28]$ ensure that the
gatewise verification of $C_{\predicate}$ occurs without error,
so that the simulation is perfect:

Let $\predicate$ be a family of predicates and let $F_{\predicate}$ and
$C_{\predicate}$ be as described above.  For $3t<n,$ protocol is
a perfect $(n,t)$-  for $\predicate.$ It runs in constant rounds and
has messages complexity polynomial in $(n,m,k,C_{\predicate}).$

Protocols whose message complexity is polynomial in $n,$ independently of the circuit complexity of $F_{\predicate},$ are presented
in Chapter <ref>.  They require the machinery of locally
random reductions, and may require the players to compute time-consuming
functions locally.  Though the results of this section require polynomial
local time if the circuit is of polynomial size, verifying huge circuits
requires very little local time per gate but great cumulative local time.
When the goal is to prove predicates regardless of their computational
complexity, then the cost must be paid somewhere; better it be on the local
computation than on the communication lines.  The next section, however,
describes a particular class of intractable functions for which only the
prover itself need perform more than polynomial time computations.

§ ZERO-KNOWLEDGE PROOFS FOR IP

Any language $L \in \ip$interactive proof system!IP
certainly has a circuit $C_L$ which
describes its characteristic function $\chi_L;$ Theorems
<ref> and <ref> imply there is a
for $L$ in the presence of a partly trusted network.  The size of
$C_L,$ however, may be inordinately large, especially because
$\ip=\pspace$interactive proof system!IP=PSPACE
[115].  Protocol would
therefore require a great deal of time and very large messages to compute,
and is unsuitable for proving intractable predicates in a network of
polynomial time machines.

We present a protocol which achieves a zero-knowledge proof system for any
language $L \in \ip,$
interactive proof system!zero-knowledge
zero-knowledge proof!for IP yet uses
only a polynomial number of rounds and polynomial message complexity.  In
particular, zero-knowledge proofs for any language in $\ip$ can be made
without complexity theoretic assumptions, if a partly trusted network of
probabilistic polynomial time Turing machines is available.  In contrast,
when there are only a prover and a verifier, perfect zero-knowledge proofs
for NP-complete languages (which are in IP) are impossible unless the
polynomial hierarchy collapses

The task at hand is distinguished from   in a few ways.  First of
all, there are no secretly shared values a priori.  Second, the
string $x$ and the language $L$ that must be proven to contain it are both
public knowledge, or at least known to both prover and verifier.
Third, the purpose of the network is not to act as a repository for secrets
and committed values but to minimize the information leaked by the proof
system while ensuring that the prover behaves.

We distinguish two members of the network as before, the prover $\prover$
and the verifier $\verifier.$ In a two-party interactive proof system
([74, 4], and <ref>), the prover is a $\pspace$
machine and the verifier is a polynomial-time machine.  The protocol is
such that, if $x \in L$ and the prover is not corrupted, then an
uncorrupted verifier will output accept with high probability.
Otherwise, an uncorrupted verifier will output reject.  Any language
in $\pspace$ admits an interactive proof [115]; the presence of a
network of processors is irrelevant.

For the purpose of restricting information, however, a network of
processors is invaluable.  Zero-knowledge proof systems are often based on
unproven complexity assumptions [74]; perfect zero-knowledge proofs
even for languages in $\np$ cannot be achieved, unless the polynomial
hierarchy collapses [62].  Perfect zero-knowledge proof systems can
be obtained given two provers that are not allowed to communicate
[27, 25].  Here, we allow only one prover, and that prover is
allowed to communicate with all of the participants and to collaborate with
a constant fraction.

The idea of zero-knowledge proofs again corresponds to secure multiparty
protocols.  The protocol must provide the verifier with one of two outputs,
accept and reject.  If the prover and verifier are not
corrupted, then the verifier accepts with high probability if $x \in L,$
and otherwise rejects.  If the verifier is not corrupted and $x \not \in
L,$ then the verifier rejects with high probability.  As in the definition
of two-party zero-knowledge, a cheating verifier must be able to simulate
the conversation.  The definition of multiparty protocol resilience
suffices to provide privacy not only with respect to the verifier but with
respect to the prover as well.

We define a particular function $F_L$ that states whether a string $x$
agreed upon by two players is in a given language $L:$ $F_i(x_1,\dots,x_n)
= 0$ if $i \not= \verifier,$ and

\[
F_{\verifier}(x_1,\dots,x_n)  =
\left\{
\begin{array}{rl}
1 & \mbox{ if } x_{\prover}=x_{\verifier}= x \not= \Lambda \mbox{ and }
x \in L \\
0 & \mbox{ otherwise. } \\
\end{array}
\right.
\]

Note that either player can refuse to participate by failing to supply a
proper input ($x=\Lambda$).  The only way for an honest verifier to be
convinced that $x \in L$ is if the prover decides to participate and $x\in

Let $L$ be a language.
A $(t,n)$ zero-knowledge network proof
system (ZKNPS) for $L$ is a $t$-resilient $n$-player protocol for $F_L.$

As usual, the adjectives perfect, statistical, computational apply.

For $2t<n$ and any $L \in \pspace,$ is a statistical ZKNPS
for $L.$
For $3t<n,$ is a perfect ZKNPS for $L.$

By a result of [75], $L$ admits an interactive proof if and only if
there is an Arthur-MerlinArthur-Merlin protocol [4] for
$L,$ in which the verifier takes the position of Arthur, and simply sends
random coins to Merlin.  Arthur accepts the proof based on a polynomial
time computation using the set of messages sent by Merlin.

Without loss of generality, assume that for some polynomial $p_1(m,k),$ the
AM protocol runs in $p_1(m,k)$ steps, and that at each step, the messages
are of length $p_2(m,k).$ The program of Arthur is simple to specify: at
round $r,$ generate $p_2(m,k)$ random bits, send them to Merlin, receive a
message $M_r$ from Merlin, and repeat $p_1(m,k)$ times; afterwards, compute
a polynomial-time function $V$ on the messages $M_1,\dots,M_{p_1(m,k)}$
from Merlin, and output the result.  Merlin, however, must compute some
presumably complicated function $P_r$ to generate the correct response
$M_r$ at each round.

Thus we may take the interactive proof system to be the hidden composition
of the functions

\[
V \closedcomp P_{p_1(m,k)} \closedcomp V_{p_1(m,k)}
\closedcomp \cdots \closedcomp P_1 \closedcomp V_1.
\]

The result, and only the result, is revealed to .

Because each function $V_r$ is simply a set of random bits, protocol
suffices.  The key is to construct a protocol that computes
each $P_r$ in a $t$-resilient fashion.  In general, the functions $P_r$ may
be too complex to admit small circuits, and hence would be expensive in
terms of interaction.  In fact, however, there is no need to compute $P_r$
through circuit simulation.  Instead, the network reveals $V_r$ to ,
who computes $P_r$ on its own, and shares the result.  Notice that the
functions $V_r$ are private, since they are simply random bit sequences
independent of all input values; hence revealing them to $P_r$ is perfectly

The computation of function $V$ could be performed through circuit
simulation, but at an expense of polynomially many rounds, since there is
no guarantee that $V,$ a polynomial-time calculation, admits sub-polynomial
depth circuits.  Instead, computes $V$ and shares the result, $v.$
Player then provides a zero-knowledge proof on secrets, as per
<ref>, to ensure that $v$ is correct.  By verifying each step
in the computation of $V$ locally yet in parallel, the number of rounds is
kept down to a constant.

Run to generate random secret $b_{uv}.$

Reconstruct $V_r = (b_{r,1},\ldots,b_{r,p_1(m,k)})$ for $\prover.$

computes $M_r=P_r$ and shares it.

computes $v=V(M_{p_1(m,k)},V_r{p_1(m,k)},\ldots,M_1,V_1)$
and shares it.

Run (,;$V$;

output is reject or $v \not=\acc$

outputs reject.

outputs accept.

Protocol for $\prover$ to prove $x \in L$ to $\verifier.$

If $\prover$ is corrupted and fails to share the correct value of $P_r$ for
some $r$ or fails to supply a correct proof at the end, this corresponds to
its choosing, in the ideal protocol, an input $x=\Lambda.$ The prover has
the inevitable right not to participate; but the protocol we present
ensures that lack of participation is reflected properly in the final
results.  Notice that by the definition of two-party interactive proof
systems, function $V$ is robust against incorrect computations of
$P_1,\ldots,P_r,$ so that a corrupt $\prover$ who shares incorrect values
corresponds to a prover in the ideal case who chooses not to participate.

Formally speaking, we perform the composition of the following ideal
protocols.  In the first protocol, each player supplies a sequence of
$p_1(m,k)p_2(m,k)$ random bits, and the trusted host computes a string of
$p_1(m,k)p_2(m,k)$ uniformly random bits by computing the parities of each
group of $n$ bits.  It divides these into $p_1(m,k)$ strings $V_r$ of
length $p_2(m,k)$ and returns a robust and secret representation of them to
the players.  In each protocol $\idealname^{2r},$ the trusted party gives
$V_r$ to $\prover.$ In each protocol $\idealname^{2r+1},$ $\prover$
computes $P_r$ and gives it to the trusted host, who computes a robust and
secret representation of what $\prover$ supplied, and returns pieces to the
players.  In the final protocol $(2p_1(m,k)+2),$ each player provides its
pieces of the robust and private representation of all of the previous
inputs, and the trusted host computes $V$ on the reconstructed values.  It
returns the result to .

The composition of these protocols provides with the closed

\[
V \closedcomp P_{p_1(m,k)} \closedcomp V_{p_1(m,k)}
\closedcomp \cdots \closedcomp P_1 \closedcomp V_1
\]

which reveals only the final result $V,$ as desired.
By Theorems <ref>,
<ref>, <ref>, <ref>, and
<ref>, the results are perfectly (statistically) $t$-resilient
if $3t<n$ ($2t<n$).

CHAPTER: PRIVACY FOR PASSIVE ADVERSARIES

“Notice all the computations, theoretical scribblings, and lab
equipment, Norm....  Yes, curiosity killed these cats.”

Gary Larson

Multiparty computations are generally impossible when the number of
faulty players exceeds half the network, unless additional assumptions
are made.  Chapter <ref> describes how noisy channels allow
computations to proceed correctly and fairly, and
demonstrates how to achieve the same results using a cryptographic
protocol for oblivious transfer.

In order to elucidate the nature of privacy in distributed computations, we
examine protocols which tolerate very large numbers of passive faults.  We
call this the “honest-but-curious” model: each player is honest and never
sends a faulty message, but players may form coalitions and pool their
knowledge to try to obtain extra information to which they are not
entitled.  We may more or less ignore the issues of correctness and
fault-tolerance, focusing only on privacy.

When the bound $t$ on the number of curious parties satisfies
$t <\lceil \frac{n}{2} \rceil,$ any function can be computed privately
in the “honest-but-curious” model (cf. [28, 39] and
Chapters <ref> and <ref>).

When $t \geq\lceil \frac{n}{2} \rceil,$ the class of privately computable
functions is restricted.  Chor and Kushilevitz [43] characterized
the set of boolean functions that can be computed privately for $t
\geq\lceil \frac{n}{2} \rceil$ as those of the form

\[
f(x_1,x_2,\dots,x_n) = f_1(x_1) \oplus f_2(x_2) \oplus \cdots
\]

In other words, for the boolean case, the only functions privately
computable when a majority of the parties are curious are exclusive-or's of
$n$ functions, each depending on one input.

The results of [121, 71, 65, 17] demonstrate that when the
participants are computationally bounded but still only curious, any
function can be privately computed for $t \leq n-1.$ Furthermore, even
functions that have non-boolean outputs are privately computable.  In an
information-theoretic sense, however, coalitions of curious parties do hold
more information than that to which they are entitled.

The complete characterization of privately computable functions when the
participants are not bounded remains an open question:

What general functions (say from $n$ inputs to $n$-bit outputs)
can be computed privately by $n$ parties, allowing
$t \geq\lceil \frac{n}{2} \rceil,$ and maintaining privacy in an
information-theoretic sense?

In this chapter, we take the penultimate step toward a complete
characterization, by solving the following problem:

What general functions
can be computed privately by two parties?

We give a characterization of functions that are privately computable by
two parties, based on a simple property of the table for the functions.
Specifically, any function whose table can be partitioned in a
certain manner can be privately computed by two parties; and any function
that can be privately computed by two parties has a table which can be
partitioned.  (See <ref> for a statement of the main theorem.)

In preliminary papers, Kushilevitz [88] and Beaver [9]
independently obtained this characterization, but the proofs appearing in
those papers contain a subtle flaw.  We present here a different proof,
which uses a different approach (see <ref>).

Our characterization bears on the $n$-party problem in that any $n$-party
protocol that allows $t\geq\lceil \frac{n}{2} \rceil$ can be adapted to a
two-party protocol.  Thus, functions that are privately computable in the
$n$-party case must satisfy certain properties satisfied by functions that
are private in the two-party case.

We also address a different version of the $n$-party problem, in which the
output of the function is not revealed.  Instead, it is maintained in a
distributed form, using an arbitrary threshold scheme. In view of the
recent development of multiparty computation protocols based on threshold
schemes (cf. [28, 39]), as well as the protocols described in the
rest of this dissertation, all of which allow the output to be maintained
in a shared form, a characterization of the functions that can be computed
secretly is needed.  We show a strongly negative result: the only functions
that can be computed secretly, maintaining the result as a secret (for use
in further protocols), are additive functions.  This result fits neatly
with that of [43] showing that privately computable boolean
functions are addition functions ($\mod 2$).

Assumptions made in this chapter.  The network is complete,
with private lines, $2$ or $n$ computationally
unbounded processors.
Protocols are perfectly resilient against passive $t$-adversaries
where $t$ may be greater than $\frac{n}{2}.$

§ DEFINITIONS

For the two-party case, we assume that the two parties communicate
using finite strings and for a finite number of exchanges.  Neither
party is computationally bounded; the privacy of the protocols is
based on information-theoretic bounds.
Because we consider only two parties, without an active adversary,
we can make some simplifying observations.

A party can be described simply by a family of distributions on strings,
parametrized by the input and the current transcript of the protocol.
These distributions are induced by the formal transition functions,
to which we shall not refer again.
Thus, party 1 is a family of distributions
$\set{D^1_{x,t} \mid  x\in X, t \in \Sigma^{\star}},$
where $\Sigma=\set{0,1},$ and each $D^1_{x,t}$ is a distribution
on $\Sigma^{\star}.$  The message that party 1 sends after
round $r$ is a finite string selected at random according to distribution
$D^1_{x,t_r},$ where $x$ is its input and $t_r$ is the transcript
of messages through round $r.$  Party 2 is defined similarly.
We assume that the transcripts are delimited so that the messages
are uniquely decodable from the transcripts.

Let the domain of $f$ be $X \times Y =
\set{1,\dots,\alpha} \times \set{1,\dots,\beta}.$
Let $T$ be a random variable which describes the transcript of
message exchanges between parties 1 and 2.
We say that $f$ is private if there is a protocol
such that, when party 1 holds $x \in X$ and party 2 holds $y \in Y:$

* After any run of the protocol, each party knows $f(x,y).$

* (Privacy for party 1)
private function
For any $x'$ such that $f(x',y)=f(x,y)$ and for any transcript $t:$

\[
\prob{ t \mid x', y} = \prob{ t \mid x, y }.
\]

* (Privacy for party 2)
For any $y'$ such that $f(x,y')=f(x,y)$ and for any transcript $t:$

\[
\prob{ t \mid x, y'} = \prob{ t \mid x, y }.
\]

We shall also denote the prefix of a transcript $t$ after the $i^{th}$
round by $t_i,$ and the corresponding random variable by $T_i.$

§ TWO PARTY PRIVACY FOR PASSIVE ADVERSARIES

§.§ Partitions

For any $x \in X$ and any subset $P \subseteq Y,$
we define the row set for row $x$ and columns in $P$ to be
the range of values that $f$ takes
over that row of its table:

\[
R(x,P) = \set{ f(x,y) \mid y \in P}.
\]

Similarly, we define the column set for
$y \in Y$ and a subset of values $P \subseteq X:$

\[
C(P,y) = \set{ f(x,y) \mid x \in P}.
\]

We say that $f$ is column-partitionable into $f_P$ and $f_Q$ if
if there exists a nontrivial partition of $Y$ into blocks $P$ and $Q$
such that

\[
(\forall x \in X) R(x,P) \hspace{0.1in} \cap R(x,Q) = \emptyset,
\]

and $f_P$ and $f_Q$ are the restriction of $f$ to the sets $P$ and $Q.$
In other words, if we look at a particular row in the table for $f$
and consider the range of values which $f$ takes on
for $y \in P,$ then no such value will appear
as the output of $f$ for $y \in Q.$
Similarly, $f$ is row-partitionable
if there exists a nontrivial partition of $X$ into blocks $P$ and $Q$
such that

\[
(\forall y \in Y) R(P,y) \hspace{0.1in} \cap R(Q,y) = \emptyset,
\]

and $f_P$ and $f_Q$ are the restriction of $f$ to the sets $P$ and $Q.$

Partitionability is recursively defined as follows.
We say that $f$ is partitionable if:

* $f$ is constant; or

* $f$ is column-partitionable or row-partitionable
into $f_P$ and $f_Q,$ each of which are themselves partitionable.

For example, the AND function is not partitionable,
while the function $f(x,y) = x + y \mod 7$ is partitionable.
Functions that are not partitionable need not be based on AND
or OR, as demonstrated by the following table, which cannot
be partitioned by rows or by columns:

( 400, 100)

( 187.2,  58.1)(  35.4,  17.7)
( 223.4,  40.4)(  17.7,  35.4)
( 205.7,  22.7)(  35.4,  17.7)
( 187.2,  22.7)(  17.7,  35.4)

( 160.1,  81.6)$f(x,y)$
( 194.1,  81.6)0
( 212.6,  81.6)1
( 231.2,  81.6)2
( 194.1,  63.6)0
( 212.6,  63.6)0
( 231.2,  63.6)1
( 231.2,  45.9)1
( 231.2,  28.2)2
( 212.6,  28.2)2
( 212.6,  45.9)4
( 194.1,  45.9)3
( 194.1,  28.2)3
( 176.1,  63.6)0
( 176.1,  45.9)1
( 176.1,  28.2)2

It is easy to see that any function that is insensitive to
$x$ or to $y$ is partitionable.

It is also straightforward to determine from an $n \times n$ table
for $f$ whether $f$ is partitionable, by using a transitive-closure algorithm,
which runs in time polynomial in $n$, to determine the columns
or rows that must fall in the same blocks of any allowable partition.

§.§ Two Parties Cannot Compute Unpartitionable Functions

We show the following result:

If $f$ is not partitionable,
then $f$ cannot be computed privately
by two parties.

Before proceeding to the proof, let us expose the flaw in the earlier proofs
of Kushilevitz [88] and Beaver [9].

Without loss of generality,
let party 1 send messages $m_r$ to party 2 during odd-numbered rounds $r;$
let party 2 send messages during even-numbered rounds.
This does not restrict who “speaks” first, since null
or completely random messages are allowed.
We expand the probability of a transcript $t$ given $x$ and $y$
according to its prefixes $t_1,t_2,\dots,$
where $t_i = m_1 \circ m_2 \circ \cdots \circ m_i:$

\begin{eqnarray*}
\prob{t \mid x,y} & = &
\prod_r \prob{t_r \mid x,y,t_{r-1}}  \\
& = &
\prob{t_{2j+1} \mid x,y,t_{2j}} )
\prob{t_{2j} \mid x,y,t_{2j-1}} ) \\
& = & P_1(t,x) P_2(t,y)
\end{eqnarray*}

where $P_1$ and $P_2$ are defined as the parenthesized expressions.
(This notation appears literally as
$P_1(s~\mid~x), P_2(s~\mid~y)$ in [88],
and as $\gamma_t(x),\delta_t(y)$ in [9].)

The faulty proof appearing in [88, 9] runs along the
following lines.  Using the privacy of $f,$ it is shown
by induction that $\prob{t \mid x,y}$ is constant over all $x.$
The induction step fails, however, since it is based on the following
statement, which intends to show that $P_1$ is insensitive to $x:$
If $\prob{t \mid x_1,y} = \prob{t \mid x_2,y}$ then
$P_1(t,x_1) = P_1(t,x_2).$  Unfortunately, if $P_2(t,y) = 0,$
this conclusion does not necessarily hold.

For example, consider the function described by

$f(x,y)$     $y_1$     $y_2$

and the 4-round deterministic protocol where party 1 starts, and each party
sends 1 bit, described by the table of transcripts:

$y_1$     $y_2$

Then $\prob{0000 \mid x_1,y_1} = P_1(0000,x_1) P_2(0000,y_1)
= \prob{0000 \mid x_2,y_1} = P_1(0000,x_2) P_2(0000,y_1),$
and we have $P_2(0000,y_1) = 1$ and $P_1(0000,x_1)=P_1(0000,x_2) = 1.$
The claim that $P_1$ is insensitive to $x$
is satisfied for this particular transcript.
On the other hand,
$\prob{0100 \mid x_1,y_1} = \prob{0100 \mid x_2,y_1} = 0,$
but $P_1(0100,x_1)=1$ while $P_1(0100,x_2) = 0.$
Informally, transcript $0100$ is impossible given $y_1,$
but it may or may not be possible for different $x,$
a fact that cannot be determined simply by looking at the
column corresponding to $y_1.$  The claim that $P_1$ is insensitive
to $x$ fails.

It turns out that $P_1$ is indeed insensitive to $x$ when $f$ cannot be
partitioned into columns, but this is not a trivial observation, and the
proof must use the unpartitionability of $f$ by columns.  The earlier
proofs did not use this property, and thereby fail on a counterexample like the
one presented above (note that $f$ is not partitionable by rows,
but it is partitionable by columns).  Introducing the property of
unpartitionability by columns into the earlier proof techniques
seems to be an unwieldy approach, without an easy fix;
instead, we present an alternative proof.

Proof of Lemma <ref>:
Since $t_{2j+1} = t_{2j} \circ m_{2j+1},$ and $m_{2j+1}$
is selected by party 1 according to distribution
$D^1_{x,t_{2j}},$ we may write:

\[
\prob{t_{2j+1} \mid x,y} =
\prob{ t_{2j+1} \mid x,t_{2j} }
\prob{ t_{2j} \mid x,y }.
\]

\[
\prob{t_{2j} \mid x,y} =
\prob{ t_{2j} \mid y,t_{2j-1} }
\prob{ t_{2j-1} \mid x,y }.
\]

First we shall show that if $f$ is privately computable but
not partitionable, then party 1 “never speaks first.”  In other
words, all conversations are independent of $x$ until party 2 gives
away some information depending on $y.$  Then we shall show that party
2 never speaks first, leading to a contradiction.

In order to formalize the notion of not speaking first, consider the
following notations.
Let $D \subseteq X \times Y,$
and let $\tau(x,y)=\set{t \mid \prob{t \mid x,y} \not= 0}.$
Given a transcript $t$ and two pairs of inputs $(x,y)$ and $(u,v),$
let $\theta(t,x,y,u,v)$ be the value $r$ such that

\[
\prob{t_r \mid x,y} \not= \prob{t_r \mid u,v} \mbox{ and }
(\forall \rho < r)
\prob{t_{\rho} \mid x,y} = \prob{t_{\rho} \mid u,v}.
\]

Clearly, such an $r$ is unique if it exists.  If no such $r$ exists,
let $\theta(t,x,y,u,v) = \infty.$
The earliest round at which the probabilities of conversations on
$(x,y)$ differ from those for some other input $(u,v)$ is denoted

\[
\phi(t,D,x,y) =
\mbox{min}_{(u,v) \in D} \hspace{0.2in} \theta(t,x,y,u,v).
\]

Now let

\[
\psi(D) = \set{ \phi(t,D,x,y) \mid (x,y) \in D, t \in \tau(x,y)}.
\]

We say that party 1 does not speak first on $D$ if
$\psi(D) \subset \set{2j \mid j \in \mbox{\bf N}} \cup \set{\infty},$
that is, if the earliest times at which conversations differ are always
even-numbered rounds, corresponding to party 2 sending a message to
party 1.

First, let us show an easy lemma:

(Row Lemma)
For any $x\in X$ and $y_1,y_2 \in Y,$ and for any possible transcript
$t \in \tau(x,y_1),$ if

\[
\prob{t_r \mid x,y_1} \not= \prob{t_r \mid x,y_2} \mbox{ and }
(\forall \rho < r)
\prob{t_{\rho} \mid x,y_1} = \prob{t_{\rho} \mid x,y_2},
\]

then $r$ is not odd.

If $r$ is odd, party 1 sends the message at round $r:$

\begin{eqnarray*}
\prob{t_r \mid x,y_1}
& = & \prob{t_r \mid x, t_{r-1} } \prob{t_{r-1} \mid x,y_1} \\
& = & \prob{t_r \mid x, t_{r-1} } \prob{t_{r-1} \mid x,y_2} \\
& = &
\prob{t_r \mid x,y_2}
\end{eqnarray*}

which is a contradiction.

The crucial lemma we need is the following:

If $f$ is privately computable but not partitionable, then
party 1 does not speak first on $X \times Y.$

We show by induction that there exist
$P_1 \subset P_2 \subset \cdots \subset P_{\abs{X}} = X$
such that party 2 speaks first on each $P_i \times Y.$

Using lemma <ref>, we see that party 1 does not speak first on
$P_1 \times Y,$ where $P_1 = \set{a_1}$ and $a_1 \in X$ is arbitrary.
Since party 1 only has one argument in $P_1,$ this is intuitively

Assume by way of induction that party 1 does not speak first on $P_i \times Y.$
We must demonstrate a $P_{i+1}$ such that $P_i \subset P_{i+1}$
and party 1 does not speak first on $P_{i+1}.$

Since $f$ is not partitionable, there exist values
$x_1 \in P_i, x_2 \in \overline{P}_i,$ and $y_1 \in Y$ so that
$f(x_1,y_1) = f(x_2,y_1).$  Let $P_{i+1} = P_i \cup \set{x_2}.$
To show that party 2 speaks first on $P_{i+1} \times Y,$
it suffices to show that for each $y \in Y,$
$\phi(t,\set{x_2} \times Y, x_2, y)$ is never odd and
$\phi(t,P_i \times Y, x_2, y)$ is never odd.  In other words,
we consider the earliest times that a meaningful message is sent for
the new inputs in $\set{x_2} \times Y$ relative to the original set
$P_i \times Y$ and relative to the new input set itself.

Lemma <ref> shows that
$\phi(t,\set{x_2} \times Y, x_2, y)$ is never odd.

To obtain the claim that $\phi(t,P_i\times Y,x_2,y)$ is never odd,
let us divide the row $\set{x_2} \times Y$ into three sets,
$A = \set{(x_2,y_1)},$
$B = \set{(x_2,y) \mid (\exists a \in P_i) f(a,y) = f(x_2,y)}\backslash A,$
$C = \set{(x_2,y) \mid (\forall a \in P_i) f(a,y) \not= f(x_2,y)}.$

First, we show that $\phi(t,P_i \times Y, x_2,y_1)$ is even for
any possible transcript $t \in \tau(x_2,y_1).$  If $t \in
\tau(x_2,y_1)$ then by the privacy of $f,$

\[
(\forall r)
\prob{t_r \mid x_1,y_1} = \prob{t_r \mid x_2,y_1}
\]

Then it follows easily that
$\phi(t,P_i \times Y, x_2,y_1) = \phi(t,P_i \times Y, x_1,y_1),$
and our first claim follows.

By a similar argument, $\phi(t, P_i \times Y, x_2, y)$ is never odd
for any $y \in B$.

Thirdly, for any $(x_2,y) \in C,$ we show $\phi(t,P_i \times Y, x_2, y)$
is never odd.  We have two cases to consider: $\theta(t,x_2,y,x_1,y_1)$
is minimal or it is not.  Say it is minimal.  Again, by the privacy of
$f$ we have that

\[
(\forall r)
\prob{t_r \mid x_1,y_1} = \prob{t_r \mid x_2,y_1}
\]

and the smallest $r$ at which
$\prob{t_r \mid x_1,y_1} \not= \prob{t_r \mid x_2,y}$
is identical to that for which
$\prob{t_r \mid x_2,y_1} \not= \prob{t_r \mid x_2,y}.$
Since $(x_2,y_1)$ and $(x_2,y)$ are in the same row,
$r$ must be even.

If $\theta(t,x_2,y,x_1,y_1)$ is not minimal, let
$(u,v)$ be such that
$\theta(t,x_2,y,u,v)$ is minimal.
For a given transcript $t,$ consider the probabilities
$\prob{t_r \mid u,v},$
$\prob{t_r \mid x_1,y_1},$
and $\prob{t_r \mid x_2,y}.$
At some earliest round $r,$ two or three of these differ.
Since $(u,v)$ gave the minimal value with respect to $(x_2,y)$
we see that $\prob{t_r \mid x_2,y} \not= \prob{t_r \mid u,v}.$
Since $(x_1,y_1)$ did not give the minimal value,
$\prob{t_r \mid x_2,y} = \prob{t_r \mid x_1,y_1}.$
$\prob{t_r \mid x_1,y_1} \not= \prob{t_r \mid u,v}.$
By the induction hypothesis, since $(x_1,y_1)$ and $(u,v)$
are in $P_i \times Y,$ we deduce $r$ is even.  $\Box$

A symmetric argument gives the corresponding lemma:

If $f$ is privately computable but not partitionable, then
party 2 does not speak first on $X \times Y.$

Combining lemmas <ref> and <ref>,
we see that neither party speaks first on $X \times Y,$ implying that
$\psi(X \times Y) = \set{\infty}.$
Let $a \in X$ and $b \in Y$
be arbitrary, and let $t \in \tau(a,b).$  Then for every $x \in X$ and
$y \in Y,$ we have
$\theta(t,a,b,x,y) = \infty,$
implying $\prob{t \mid a,b} = \prob{t \mid x,y}.$
Since $f(x,y)$ is determined by the transcript $t,$ $f$ must
be constant and hence partitionable, giving a contradiction.

The proof of lemma <ref>
does not assume that the protocol is deterministic.
In the next section we observe that a deterministic protocol suffices
to compute any partitionable function.  Furthermore, even if the
protocol is only correct with probability exceeding $\half,$
the argument shows that the distributions on transcripts
are identical regardless of the inputs, so that $f$ must be constant,
giving a contradiction.

§.§ Two Parties Can Compute Partitionable Functions

We now show a converse result:

If $f$ is partitionable, then there is a
(deterministic) protocol whereby $f$ can
be computed privately by two parties.

By induction on $\alpha = \abs{X}.$

(Base Case.)
If $X=\set{x_1},$ then party 2 simply announces $f(x_1,y).$
This protocol is trivially private for party 1, and
since for all $y,y' \in Y$ such that $f(x_1,y)=f(x_1,y')$
the transcript consists exactly of $f(x_1,y),$ the protocol
is private for party 2.

(Inductive Hypothesis.)
If $\abs{X} \leq \alpha,$ then
if $f$ is partitionable then there is a deterministic
protocol $\Pi_f$ to compute $f.$

(Inductive Step.)
Let $\abs{X} = \alpha+1.$  Say that $f$ is partitionable.
If $f$ is constant there is a trivial private protocol.
Otherwise, $f$ is row-partitionable or column-partitionable.

If $f$ is row-partitionable into $f_P$ and $f_Q,$ then by the
induction hypothesis there exist private
protocols $\Pi_{f_P}$ and $\Pi_{f_Q}$ for $f_P$ and $f_Q.$
Define the protocol $\Pi_f$ as follows.  If $x \in P,$ party 1
sends a 0; then the parties execute the protocol for $\Pi_{f_P}.$
Otherwise if $x \in Q,$ party 1 sends a 1,
and the parties execute the protocol for $\Pi_{f_Q}.$

Since the protocols are deterministic, let $\Pi(x,y)$ denote
the transcript of protocol $\Pi$ on inputs $x$ and $y.$

Protocol $\Pi_f$ is private with respect to party 1.
If $f(x,y)=f(x',y),$ then either $x,x' \in P$ or
$x,x' \in Q;$ otherwise $f$ would not be row-partitionable.
If $x,x' \in P,$ then

\[
\Pi_f(x,y)= 0 \circ \Pi_{f_P}(x,y)
= 0 \circ \Pi_{f_P}(x',y) = \Pi_f(x',y).
\]

Similarly, if
$x,x' \in Q,$ then
$\Pi_f(x,y)= \Pi_f(x',y).$

Protocol $\Pi_f$ is also private with respect to party 2.
If $f(x,y)=f(x,y'),$ then either $x \in P,$ in which case

\[
\Pi_f(x,y)= 0 \circ \Pi_{f_P}(x,y)
= 0 \circ \Pi_{f_P}(x,y') = \Pi_f(x,y');
\]

or $x \in Q,$ which likewise gives
$\Pi_f(x,y)= \Pi_f(x,y').$

Now, if $f$ is not row-partitionable then it must be
column-partitionable into $P$ and $Q.$  We now prove by
induction on $\beta=\abs{Y}$ that $f$ is private.
Say $\beta=1;$ then $f$ is trivially private.  Now,
assume that the hypothesis holds for $\abs{Y} \leq \beta.$
Consider $\abs{Y} = \beta+1.$  Then $f$ is partitionable
into $f_P$ and $f_Q,$ where $\abs{P},\abs{Q} \leq \beta.$
Hence there exist private protocols $\Pi_{f_P}$ and
$\Pi_{f_Q}$ for $f_P$ and $f_Q.$  The protocol for $f$ is
If $y \in P,$ party 2
sends a 0; then the parties execute the protocol for $\Pi_{f_P}.$
Otherwise if $y \in Q,$ party 2 sends a 1,
and the parties execute the protocol for $\Pi_{f_Q}.$
The proof that this
$\Pi_f$ is private follows the same lines as above.

§.§ Main Result

We can summarize the main result of this chapter in the following theorem:

private function
A finite function $f(x,y)$ is 1-private if and only if
it is partitionable.

Follows from lemmas <ref> and <ref>.

§ MULTIPARTY PRIVACY FOR MODULAR PROTOCOLS

As described in Chapters <ref>, <ref> and <ref>,
Many of the methods for performing arbitrary secret computations follow the
method of constructing a modular library of protocols that can be selected
and combined to construct new protocols.

A general library based on threshold (secret sharing) methods allows the
output of one protocol to be maintained in a secret format suitable for
input to another protocol, so that intermediate computations are not

In this section we consider what functions can be computed given an
arbitrary threshold scheme that allows addition of secrets over the field
used for sharing, when we also require that the output of the function be
retained as a secretly shared value for potential use in further

Let $E$ be a field and let $L_0$ be a set of function families mapping
$E^n$ to $E.$ Let $L$ be the closure of functions that can be written as a
finite composition of functions in $L_0.$ For example, with
$g,f_1,\dots,f_n \in L,$ the following function is in $L.$

\[
\]

A $t$-private library ${\cal L}$ for $L$
is a set of protocols satisfying:

* Each protocol $\Pi \in {\cal L}$ computes a function $f \in L,$ $t$-privately.

* For every $f \in L$ there is a protocol $\Pi \in {\cal L}$
that computes it.

The protocols for multiplication and addition given in [28, 39]
satisfy these properties, and in fact are complete for any finite function
when $t< \lceil \frac{n}{2} \rceil.$ In other words, they form a $\lceil
\frac{n}{2} \rceil$-private library for the class of all finite functions.

For $t \geq\lceil \frac{n}{2} \rceil,$ however, the situation is less
optimistic.  We show that any library sufficiently powerful to compute
affine functions over $E$ can only compute affine functions over the
field $E.$

If ${\cal L}$ is a $t$-private library of protocols that includes all
affine functions over the field $E,$ and if $t \geq\lceil \frac{n}{2}
\rceil,$ then any function $f(x_1,\dots,x_n) \in L$ can be written

\[
f(x_1,\dots,x_n) = f_1(x_1) + f_2(x_2) + \dots + f_n(x_n).
\]

Proof: Let $f(x_1,\dots,x_n)$ be $t$-private for some $t \geq \lceil
\frac{n}{2} \rceil,$ and let $f$ depend on $k$ variables, $1 \leq k \leq
n.$ That is, for some $j_1,\dots,j_k$ and $\hat{f},$

\[
f(x_1,\dots,x_n) = \hat{f}(x_{j_1},\dots,x_{j_k}).
\]

Then we show by induction on $k$ that

\[
(\exists f_1,\dots,f_n,\hat{f}) \hspace{0.1in}
f(x_1,\dots,x_n) = \sum_{i=1}^n f_{i}(x_{i}).
\]

The statement is trivially true for $k=1.$
Assume that it holds for $k.$

Let $f$ be $t$-private and let $f$ depend on $k+1$ variables:

\[
(\exists j_1,\dots,j_{k+1}) \hspace{0.1in}
f(x_1,\dots,x_n) = \hat{f}(x_{j_1},\dots,x_{j_{k+1}}).
\]

Without loss of generality let $j_1=1,j_2=2,\dots,j_{k+1}=k+1.$
Fix arbitrary arguments $a_1,\dots,a_{k+1},$
and let $l = \lceil \frac{k}{2} \rceil.$
Suppose there exist $b_1,\dots,b_{k+1}$ such that

\begin{eqnarray}
\label{eqn-suppose}
\hat{f}(b_1,\dots,b_l,b_{l+1},\dots,b_{k+1})
+ \hat{f}(a_1,\dots,a_l,a_{l+1},\dots,a_{k+1})
& \not= & \\
\nonumber
\hat{f}(a_1,\dots,a_l,b_{l+1},\dots,b_{k+1})
+ \hat{f}(b_1,\dots,b_l,a_{l+1},\dots,a_{k+1}).
& &
\end{eqnarray}

It is not hard to see that there exist $r$ and $s$ with $r \not= s,$
such that $a_r \not= b_r$ and $a_s \not= b_s.$

Define the linear functions $p_r$ and $p_s$ as

\begin{eqnarray*}
p_r(x_1,\dots,x_{k+1}) & = &
(x_r - a_r) (b_r - a_r)^{-1}
( \hat{f}(b_1,\dots,b_l,a_{l+1},\dots,a_{k+1})
\\ & &
- \hat{f}(a_1,\dots,a_l,a_{l+1},\dots,a_{k+1}) )
\\
& &
+ \hat{f}(a_1,\dots,a_l,a_{l+1},\dots,a_{k+1})  \\
p_s(x_1,\dots,x_{k+1}) & = &
(x_s - a_s) (b_s - a_s)^{-1}
( \hat{f}(a_1,\dots,a_l,b_{l+1},\dots,b_{k+1})
\\ & &
- \hat{f}(a_1,\dots,a_l,a_{l+1},\dots,a_{k+1}) )
\\
& &
+ \hat{f}(a_1,\dots,a_l,a_{l+1},\dots,a_{k+1})
\end{eqnarray*}

Using the assumption that the library contains all affine functions,

the function $G$ defined as follows is $t$-private:

\[
G(x_1,\dots,x_n) =
- p_r(x_1,\dots,x_{k+1})
- p_s(x_1,\dots,x_{k+1})
+ \hat{f}(a_1,\dots,a_{k+1}).
\]

\begin{eqnarray*}
G(a_1,\dots,a_l,a_{l+1},\dots,a_{k+1},0,0,\dots,0) & = & 0, \\
G(a_1,\dots,a_l,b_{l+1},\dots,b_{k+1},0,0,\dots,0) & = & 0, \\
G(b_1,\dots,b_l,a_{l+1},\dots,a_{k+1},0,0,\dots,0) & = & 0, \\
G(b_1,\dots,b_l,b_{l+1},\dots,b_{k+1},0,0,\dots,0) & \not= & 0.
\end{eqnarray*}

Let $\Pi_G$ be a $t$-private protocol for $G.$  We use $\Pi_G$
to construct a $1$-private protocol for two parties to compute
AND(x,y), by having party 1 simulate half the parties and
party 2 simulate the other half.
Party 1 holds an input $x \in \set{0,1},$ and party 2 holds an
input $y \in \set{0,1},$ though when they simulate $\Pi_G$ they
will “pretend” to hold general arguments instead.
Let $m = \lfloor \frac{n-k-1}{2} \rfloor.$
Party 1 follows $\Pi_G,$ simulating the parties holding inputs

Party 2 follows $\Pi_G,$ simulating
the parties holding inputs
Notice that neither party 1 nor party 2
simulates more than $t$ parties.

If party 1 holds input $x=0,$ it selects $x_1=a_1,\dots,x_l=a_l.$
If party 1 holds input $x=1,$ it selects $x_1=b_1,\dots,x_l=b_l.$
It sets all other variables to 0.
if party 2 holds input $y=0,$ it selects
If party 2 holds input $y=1,$ it selects
It sets all other variables to 0.

Together, party 1 and party 2 simulate $\Pi_G,$ sending messages to one
another when $\Pi_G$ specifies that a player from the group simulated by
party 1 interact with a player from the group simulated by party 2.
Both party 1 and party 2 learn the value of $G$ from the simulated
protocol.  If $G = 0,$ each outputs AND(x,y)$=0$;
if $G \not= 0,$ each outputs AND(x,y)$=1$.
It is easy to see that their outputs are correct.

Since $\Pi_G$ is $t$-private, where
$t \geq \lceil \frac{n}{2} \rceil,$
this two-party protocol is also $1$-private.
But Theorem <ref> implies that
there is no two-party $1$-private protocol for AND;
hence supposition (<ref>) is false.  Thus,

\begin{eqnarray*}
f(x_1,\dots,x_n) & = &
\\ & &
+ f(x_1,\dots,x_l,a_{l+1},\dots,a_{k+1},0,\dots,0)
\\
& &
- f(a_1,\dots,a_l,a_{l+1},\dots,a_{k+1},0,\dots,0).
\end{eqnarray*}

\begin{eqnarray*}
g(x_1,\dots,x_n) & = &
f(a_1,\dots,a_l,x_{l+1},\dots,x_{k+1},0,\dots,0), \\
h(x_1,\dots,x_n) & = &
\end{eqnarray*}

Since $f$ is $t$-private, so are $g$ and $h.$
But $g$ and $h$ each depend on at most $k$ variables.
By the induction
hypothesis, there are $g_1,\dots,g_n,h_1,\dots,h_n$ such that

\begin{eqnarray*}
g(x_1,\dots,x_n) & = &
g_1(x_1)+ \cdots + g_n(x_n), \\
h(x_1,\dots,x_n) & = &
h_1(x_1)+ \cdots + h_n(x_n).
\end{eqnarray*}

Let $d = f(a_1,\dots,a_l,a_{l+1},\dots,a_{k+1},0,\dots,0).$
Then we have,

\begin{eqnarray*}
f(x_1,\dots,x_n) & = &
g(x_1,\dots,x_n) + h(x_1,\dots,x_n) - d
\\
& = &
g_1(x_1)+ \cdots + g_n(x_n) + h_1(x_1)+ \cdots + h_n(x_n) - d \\
& = &
f_1(x_1) + \cdots + f_n(x_n),
\end{eqnarray*}

where we define $f_1(x_1)=g_1(x_1)+h_1(x_1) - d$
and $f_i(x_i) = g_i(x_i)+h_i(x_i)$ for $i \geq 2.$
This completes the induction step.

Applying the result for $k=n,$ we conclude that
for an arbitrary $t$-private function $f$
there exist $f_1,\dots,f_n$ such that

\[
f(x_1,\dots,x_n) = f_1(x_1)+ \cdots + f_n(x_n),
\]

completing the proof of Theorem <ref>.

CHAPTER: CRYPTOGRAPHIC METHODS TOLERATING A FAULTY MAJORITY

In fact the incontinent person is like a city that votes for all the
right decrees and has good laws, but does not apply them, as in
Anaxandrides' taunt, “The city willed it, that cares nothing for

Aristotle, Nicomachean Ethics

The public-key, complexity-based approach to security
complexity-based cryptography
introduced by Diffie
and Hellman [54] affords a greater range of resilience than the
unconditional, information-theoretic approach discussed thus far.  An
adversary that has bounded resources will not be able to break encryptions
or generate effective malicious messages if the encryptions and the
protocols require tremendous resources to corrupt, even though they might
leak information to an unbounded adversary in the pure, Shannon sense.

We shall consider protocols in which the players and the adversary are
polynomial-time Turing machines.  A tool common to complexity-based
cryptography is the one-way function [120, 37].  A one-way
function is, informally, a function that is easy to compute but hard to
invert.  A wide variety of candidates exist, but none have been proven to
be one-way; this is not surprising in view of the fact that the existence
of a one-way function would imply P$\not=\np.$ For example, exponentiation
modulo a prime $p$ is easy to perform, but no efficient solution is known
for its inverse, the discrete logarithm problem
(Definition <ref>).  One-way trapdoor functions are
functions that are difficult to compute but with a small amount of advice
become easy.  Computing quadratic residuosity modulo a product of two
primes $n=pq$ is a common example; without the factorization of $n,$
computing the residuosity is presumably difficult, whereas with the factors
of $n$ there is a simple polynomial-time algorithm to compute residuosity.

The drawback to complexity-based cryptography is the problem that unproven
assumptions are made.  Security is not unconditional, but conditioned on
cryptographic assumptions.

[It may be observed that assuming the presence of a private
channel is a cryptographic assumption, but the use of the
term cryptographic assumption often
refers to unproven complexity-theoretic conjectures.]

It is therefore essential to keep the assumptions to a minimum.  Rather
than make a particular assumption like the intractability of factoring
large integers, it is desirable to design protocols and encryption
techniques based on the existence of an arbitrary one-way trapdoor
function.  Assuming a one-way function is preferable to assuming a one-way
trapdoor function or a one-way permutation, for example.

without assuming new primitives such as unproven complexity-theoretic
conjectures or measurably noisy communication channels, it is impossible
to achieve general multiparty computations when a majority of players
may be faulty.  Consider intuition, first.  If a minority of players is
able to determine the input of a given player, then certainly a faulty
majority could do so.  Therefore, a protocol cannot allow any minority
the power to determine inputs.  But if the group of nonfaulty players is
a minority, the information it holds will be insufficient to determine
the input of any faulty player (even in some oblivious, shared or
distributed manner that preserves the privacy of the faulty player), and
the joint computation cannot hope to depend on that player's input.
[One cannot in general “penalize” a faulty player
at any stage simply by ignoring its input, since an unfair bias may
result (consider a faulty player that can withdraw its input of “1”
when a parity computation isn't proceeding to its liking).] The old rule
of thumb stating, “The majority rules,” applies even when the majority
is bad.

Even worse, faulty players may withdraw precisely after learning
the output, gaining full benefit
at the expense of honest players.  Notice that when the faulty players hold
only a minority, the majority of nonfaulty players always holds enough
information to determine the result and cannot be denied the answer.

Fairness has been treated in the two-party, cryptographic
setting by Yao [121], and
in the $n$-party case by Galil, Haber, and Yung [65],
primarily through techniques based on exchanging secret keys
Luby, Micali and Rackoff [90] use the Quadratic Residuosity Assumption
to design a biased coin that two parties compute jointly;
using this biased coin, the two parties exchange secret keys
All of these results rely on strong and specific complexity theoretic
Cleve [45] examines impossibility results independent of
complexity theoretic assumptions.

This chapter presents techniques to attain fair, secure, and reliable
computations even though the majority of processors may be malicious.
Based on certain cryptographic assumptions, however,
a minority of honest processors
can restrict the power of a faulty majority to the ability only to
withdraw; a faulty majority cannot cause the honest processors to adopt
incorrect values.

We discuss different and stronger definitions for fairness
in the $n$-party scenario,
and present a learning-based approach for which fairness and secret
computation are in fact achievable.
Our solution uses a technique called
gradual disclosure,
in which each party learns the result slowly, so
that if the procedure halts, each player has gained roughly equal knowledge.
This technique has similarities to the methods of [90] for secret
exchange, but does not use strong assumptions.

For clarity, our exposition starts with a weakened adversary, who can
corrupt $t > n/2$ players but who is allowed only fail-stop corruptions.
(Chapter <ref> discusses an even weaker, completely passive
No incorrect messages may be sent.  Our solution
assumes two-player oblivious circuit evaluation, which we shall later
replace by assuming either the presence of noisy (“oblivious transfer”)
channels or by assuming that a cryptographic protocol for
two-party oblivious transfer exists.
A result of Impagliazzo and Rudich [82] implies that
weaker complexity theoretic
assumptions are difficult to make without proving P$\not=\np.$

Finally, to investigate a fully Byzantine adversary that can corrupt a
majority, we present methods that restrict the powers of the Byzantine
adversary to those of a fail-stop adversary.  Through zero-knowledge proofs
using either noisy channels or one-way functions, we essentially compile
our fail-stop protocol (in the sense of [71]) into one resilient
(with certain limitations)
against Byzantine adversaries.  That is, faced with a
possibly cheating Byzantine adversary, nonfaulty players can detect
cheating and disqualify faulty players, thus limiting the power of the
Byzantine adversary.  The use of noisy channels for this purpose is novel.

Assumptions made in this chapter. The network has private channels, a
broadcast channel, $n$ processors, and any number $t$ of Byzantine
faults, chosen statically.
We assume that a protocol for oblivious transfer
exists, and consider the goal of computing Boolean functions.
We ultimately remove the assumptions of private
The protocols are computationally resilient.

§ FAIRNESS

For $2t \geq n,$ full resilience cannot be achieved, but we can measure
how far each player progresses toward an answer in order to show that
parity is maintained.  As earlier, we would like a standard: a fair,
ideal protocol, and we would like a means to compare an arbitrary
protocol to it.  For the latter we shall continue to use relative

The fair, ideal protocol should allow a stronger adversary, restricted
to the ideal $t$-fault-classideal fault class
but given the ability to corrupt player $(n+1)$ (the trusted host)
in a fail-stop manner.
We call this an extended $t$-adversary class.
adversary class!extended
Thus, an adversary can see rushed messages in a
given round and prevent the host from completing the round.

To measure how much each player learns in a protocol, consider the chance
that a player guesses a particular output, for any value $y$ and state $q:$

\begin{eqnarray*}
p_i(y,q_i) & = & \prob{\outfn_i(q_i) = y_i} \\
p_A(y,q_A) & = & \prob{\outfn_A(q_A) = y_A}.
\end{eqnarray*}

The initial probability of player $i$ is $p_i(y,x_i \circ a_i).$
Motivated by definitions of likelihood and weight of evidence
frequently used in learning theory,
we define

\[
\odds(p) = \frac{p}{1-p}. \index{odds}
\]

The increase in odds that a player or adversary outputs the correct
result serves as a measure of how much that party learns from a

A fair, ideal protocol computes some function $f$ while maintaining
parity in knowledge as it reveals the result.  In measuring the increase
in knowledge of adversaries, we make two assumptions.  The first is that
the adversary is static.  Defining fairness with respect to dynamic
adversaries is more involved and fraught with subtleties.  For example,
it is hard to define an adversary's initial information,
since a dynamic adversary may (intentionally) start off ignorant
but later gain huge amounts of information, completely disparate
with the minor gains of nonfaulty players, by obtaining the inputs
of newly corrupted players.  These difficulties suggest that
a proper formulation of fairness for dynamic adversaries is
an attractive open problem.  Because our protocols are designed to withstand
static adversaries, we need not treat it in this chapter.

The second assumption we make is that an adversary maximizes its
initial chances to guess the result.  As mentioned, an adversary might
intentionally compute wrongly when given only the initial information,
in order that a quantitative measure of fairness be broken.  Here,
it is not a question of ignorance, but of programming, since the adversary
knows all the corrupt inputs at the start.  Given an adversary class
$\advclass,$ we define the
maximal initial probability of coalition $T$:
maximal initial probability

\[
p_T(y,\vec{x}_T \circ \vec{a}_T \circ a) =
\mbox{max } \{
\prob{\outfn_A(\vec{x}_T \circ \vec{a}_T \circ a) = y_A} \mid
A\in \advclass, T=T(A)
\}
\]

fairideal protocol!fair
A $(\delta,t)$-fair, ideal protocol for $\computef$
is a protocol with the following properties, for any adversary $A$
from an extended, ideal, static $t$-adversary class:

The host must collect all inputs in the first round and compute
$F(\vec{x}'),$ where $\vec{x}'$ is the vector of inputs it collects;

For any $\protoIn,$
for any execution,
for all $r \leq R,$
for all $i \not \in T=T(q_A),$
and for all $\vec{x}'$ such that $\vec{x}_T = \vec{x}_T',$

\[
\frac{\odds(p_A(\computef(\vec{x}'),q_A^r))}%
\leq
(1+\delta) \cdot
\frac{\odds(p_T(\computef(\vec{x}'),
\vec{x}_T \circ\vec{a}_T \circ a))}%
{\odds(p_i(\computef(\vec{x}'),x_i \circ a_i))},
\]

\[
\odds(p_A(\computef(\vec{x}'),q_A^r)) = \infty
\mbox{\hspace{0.3in} and \hspace{0.3in}}
\odds(p_i(\computef(\vec{x}'),q_i^r)) \geq \frac{1}{\delta};
\]

The host must return $\computef(\vec{x}')$ in round $R.$

We say $\delta$-fair, ideal when $t$ is clear
from context.

Condition (3) seems pointless because the adversary ought to stop
the host before this step, always learning $\computef(\vec{x}')$ while
preventing nonfaulty players from learning $\computef(\vec{x}')$ with
certainty.  Condition (2), however, ensures that the nonfaulty
players nevertheless have a very good idea of the output.
Our protocols will satisfy an additional constraint, that
in order to stop the trusted host,
the adversary must identifiably corrupt
at least $n-t$ players.
In a litigious society, this is a high price to pay.  At the very
least, it prevents further infractions.

The ideal standard for fairness allows us to define fairness for
a general protocol:

A protocol $\protoname$ computes $F$ $t$-fairly if,
for some $c>0,$
there exists a $O(k^{-c})$-fair ideal protocol $\idfairname(\computef)$
for $F$ such that

\[
\protoname \resilasFaS \idfairname(\computef).
\]

We shall make use of protocols that would be resilient if the
adversary could not halt the protocol entirely.  Specifically,
a semi-ideal protocolprotocol!semi-ideal
$\seminame(F)$ for $F$
is one that accommodates an
extended adversary, but if the adversary halts the host at some round $r,$
then all nonfaulty players output $\outfn(q_i^r)=(\cheating,y_i),$
where $y_i$ indicates a “best guess” for the output.
Otherwise, as in the
ideal protocol, each nonfaulty player receives the value of

A protocol $\protoname$ is $t$-semi-resilient for $F$ if
there exists a semi-ideal protocol $\seminame(F)$ such that,
with respect to an extended ideal $t$-adversary class,

\[
\protoname \resilasFa \seminame(F)
\]

§.§ Comparison to Previous Work

Galil, Haber, and Yung  extended Yao's two-party protocol
to an $n$-party protocol that is fair under a different, weaker
definition [65, 121].  Their definition allows nonfaulty
players to run a recovery protocol based on the programs
of faulty players.  This is unrealistic in two ways.  First,
it requires that adversaries have less computational power.
Second, the adversaries' programs cannot depend in any way on
the nonfaulty players' programs.

Their solution involves encrypting the result using a trapdoor function
and revealing the trapdoor bit by bit.  At any point, it would seem
that no player is more than one bit ahead of another.  Unfortunately,
if an adversary is a powerful investment firm with a supercomputer
that is a thousand times faster than the personal computer of a
small investor, the firm can always quit once it has enough of the
trapdoor, leaving the small investor in the dust.

We make no such restrictions and allow a full range of adversaries
that know the programs of nonfaulty players (though not, of course,
their inputs).

Our protocols use a near optimal number of rounds relative to
a two-party lower bound of Cleve [46] that generalizes
to the $n$-party, $2t \geq n$ case.  If $p$ and $q$ are the
a priori probabilities of each player
to guess the result, there is a quitting strategy for one player allowing
him to predict $\computef$ with probability
$\frac{\mbox{\scriptsize min}(1-p,1-q)}{2k}$
better than the other, where $k$ is the number of rounds.  A certain
number of rounds are required to attain fairness.

§ GRADUAL DISCLOSURE: FAIL-STOP FROM PASSIVE

We begin our analysis with a method to achieve fairness against
fail-stop adversaries, given protocols to compute functions
resiliently against passive adversaries.  The fundamental idea
is that the result should be revealed slowly; the particular method
we employ uses a series of coin flips biased slightly toward the
answer ( [90]), each computed using a
semi-resilient multiparty protocol.

The ideal coin-flip protocol
coin!ideal protocol
ideal!coin flip protocol
is described in Figure <ref>.
We show:

Protocol is a $(4k^{-1},t)$-fair, ideal protocol.

0.5in 0.7in 1.0in 0.5in 0.5in 0.5in 0.5in (IC1)
$(1 \leq i \leq n)$
$i \rightarrow n+1:$

$F \leftarrow F(x_1,\ldots,x_n)$

$c_i \leftarrow \bias(\frac{1}{k})$

$n+1 \rightarrow [n]:$
$F \oplus c_i$

Ideal coin protocol to evaluate $F(x_1,\dots,x_n),$
against an extended fail-stop adversary.
For $O(k^{-c})$-fairness, replace $k$ by $k^{c}.$

$\odds(p_T(\computef(\vec{x}'),\vec{x}_T \circ\vec{a}_T \circ a))
= \infty,$
there is nothing to prove.
Otherwise, the adversary's odds become infinite only in
the final round, when $F(\vec{x}')$ is revealed,
but at that point the odds of nonfaulty players exceeds $k.$
This can be seen from bounds on the tail of the binomial distribution
proven by Chernoff and Angluin and Valiant [41, 2].
A binomial random variable $X_{N,P}$ measures the number of
successes in $N$ independent Bernoulli trials, where the probability
of success is $P.$

(Chernoff, Angluin, Valiant)
If $X_{N,P}$ is a binomial random variable, then

\[
\prob{X \leq (1-\epsilon) NP} \leq
\exp({-\half\epsilon^2 NP}).
\]

Let $X$ represent the number of coins of value $F(\vec{x}'),$
$N=k^3,$ and $P=(\half + \frac{1}{k}).$  Then

\[
\prob{X \leq \half k^3}
\leq
\exp({-\half \left(\frac{2}{k+2}\right)^2 (\half k^3 + k^2)})
\exp({-\frac{k^2}{k+2}})
\leq
\exp({-\frac{k}{2}}),
\]

for $k \geq 2.$

\[
\odds(p_i(\computef(\vec{x}'),q_i^R))
\geq
\frac{1-\exp({-\frac{k}{2}})}{\exp({-\frac{k}{2}})}
= \exp({\half k})-1 > k,
\]

for $k \geq 3.$  If the adversary allows a nonfaulty player to see
the $(k+1)^{st}$ coin flip, the odds are clearly better.

Thus it suffices to show that the ratio of odds
increases by a factor of no more than $(1+4k^{-1})$ in each round.
First let us show that the best adversarial strategy for guessing the output
is simple (choose the majority,   the best Bayesian guess) and achievable.
Let $A$ be an adversary that, for some sequence $\rho$ of coin flips
for which $\prob{F=0 \mid \rho} > \half,$ but $A$ outputs $1$
with probability $\alpha > 0.$  Let $B$ be $A$ modified to output
$1$ always in this case.  Then $B$ is more successful in guessing
the output when the sequence $\rho$ comes up:

0.3in 2.1in  $ (\prob{B=0,F=0 \mid \rho}  + \prob{B=1,F=1 \mid \rho})$

$ - (\prob{A=0,F=0 \mid \rho} + \prob{A=1,F=1 \mid \rho})$

$ = $
$ \prob{B=0\mid\rho} \prob{F=0\mid\rho} + \prob{B=1\mid\rho} \prob{F=1\mid\rho}$

$ - \prob{A=0\mid\rho} \prob{F=0\mid\rho} - \prob{A=1\mid\rho} \prob{F=1\mid\rho}$

$ = $
$ (1-(1-\alpha))\prob{F=0\mid\rho}  - \alpha\prob{F=1\mid\rho}$

$ = $
$ \alpha ( \prob{F=0\mid\rho} - \prob{F=1\mid\rho} )$

$ > $
$ 0.$

Given the best possible adversary, we now show that the amount it
learns from a round of the ideal coin protocol increases its odds
by no more than a factor of $(1+4k^{-1}).$
$b=\frac{1}{k},$ $\gamma_0=(\half+b),$
and $\gamma_1=(\half-b).$
Clearly, if $p$ is the number of $0$'s in $\rho,$ and $q=\abs{\rho}-p,$

\[
\prob{\rho \mid F = d} = (\gamma_d)^p (\gamma_{\overline{d}})^q.
\]

\begin{eqnarray*}
\prob{F=d \mid \rho} & = &
\prob{\rho \mid F=d}\prob{F=d} \\
& &
\cdot {\left(\prob{\rho \mid F=0} \prob{F=0} +
\prob{\rho \mid F=1} \prob{F=1} \right)}^{-1}.
\end{eqnarray*}

Consider what happens when the next coin toss is a $0.$  We must consider
the odds of a correct guess given the sequence ${\rho}{0}.$  It suffices to
show that the ratio $\Delta$ of these odds to those of the adversary when
given only $\rho$ is no more than $(1+4k^{-1}).$

\begin{eqnarray*}
\Delta & = &
\frac%
\\
& = &
\frac%
{\prob{F=0\mid {\rho}0}}
{1 - \prob{F=0\mid {\rho}0}}
\cdot
\left(
\frac%
{\prob{F=0\mid \rho}}
\right)^{-1}
\end{eqnarray*}

With a bit of manipulation, letting $L=\gamma_0 \gamma_1^{-1}$
and $G=\prob{F=0}(\prob{F=1})^{-1},$

\[
\Delta =
\frac%
{1+ L^{q-p} G^{-1}}
{1+ L^{q-p-1} G^{-1}}
\cdot
\frac%
{1+ L^{p+1-q} G}
{1+ L^{p-q} G}
\]

The extremal cases occur when $p \approx q$ and $G \approx 1;$

\begin{eqnarray*}
\Delta & < & \frac{1+L}{1+L^{-1}} = L  \\
& &
(\frac{1}{2} + \frac{1}{k})
(\frac{1}{2} - \frac{1}{k})^{-1}
\leq 1+4k^{-1}.
\end{eqnarray*}

Let $\idfairname(\computef)$ be a $\delta$-fair, ideal protocol for
$\computef$ having $R(n,m)$ steps.  If $\protoname=\set{\protoname(i)}$ is
a family of protocols such that $\protoname(i)$ statistically
$t$-semi-resiliently computes the $i^{th}$ step of
$\idfairname(\computef),$ then the protocol $\hat{\protoname}$ defined as
$\protoname(R(n,m)) \circ \cdots \circ \protoname(1)$ is a
$t$-semi-resilient and $\delta$-fair protocol for $\computef.$

We write $\computef$ as a composition of functions $\hat{\computef}=
\hat{\computef}^{R(n,m)} \circ \cdots \circ \hat{\computef}^1,$ where each
can also take an input of the form $x_i=(\cheating,g),$ in which case it
outputs $y_i=(\cheating,g).$  By Theorem <ref>,
$\hat{\protoname} \resilasFaS \protoconc_1^{R(n,m)}
\seminame(\hat{\computef}^i) \resilasFa \idfairname(\computef).$

For any protocol $\protoname,$ define protocol
$\fs(\protoname)$ by modifying each player
to broadcast $\cheating$ if it fails to
receive an expected message, receives an improper message (according to
some local computation it can make), or receives a broadcast $\cheating$
message.  If any of these occasions occur, it halts in the next round,
producing and output of the form $(\cheating,y).$

If $\protoname$ is $t$-resilient leaking $\computef$ against passive
adversaries, then $\fs(\protoname)$ is $t$-semi-resilient leaking
$\computef$ against fail-stop adversaries.

Let $\interface'$ be an interface for passive adversaries, from
$\protoname$ to $\idealname(\computef).$ Define interface $\interface$ for
fail-stop adversaries from $\fs(\protoname)$ to $\seminame(\computef)$ as
follows.  Interface $\interface$ runs $\interface'$ until adversary $A$
requests the failure of some subset of processors, by specifying they send
no messages to some set $U$ of nonfaulty players.  Interface $\interface$
halts the host in $\seminame(\computef),$ causing all players to halt and
output , just as in $\fs(\protoname).$  The interface also
supplies $A$ with messages of $\cheating$ from players in $U,$ uses
$\interface'$ to generate the outgoing messages from the remaining
nonfaulty players in the current round of $\fs(\protoname),$ and in the
next round reports $\cheating$ from all nonfaulty players that did not
already broadcast $\cheating.$

If $A$ never causes a failure, then $\interface$ runs $\interface'$ to the
end, never halting the trusted host.  The distribution (conditioned on no
halting) on outputs in $\anglebrack{A,\fs(\protoname)}$ is the same as in
$\anglebrack{A,\protoname},$ which in turn is the same as in
$\anglebrack{A,\interface',\idealname(\computef)},$ which (conditioned on
no halting) matches that in $\anglebrack{A,\interface,\seminame(\computef)}.$

The semi-resilient general protocol, even though unfair,
is easily utilized to accomplish what the ideal, fair protocol
accomplishes.  Figure <ref> describes a
$O(k^{-c})$-fair, semi-resilient protocol for any function $F.$
The protocol is a concatenation of protocols that
compute the result of each round of the ideal coin-flip protocol,
namely a random coin biased toward the result, $F(x_1,\ldots,x_n),$
with probability $\half+\frac{1}{k}.$  Clearly, $k$ can
be replaced by $k^c$ for any $c>0,$ providing greater
fairness if desired.

Let $t \leq n.$ If for any $G$ there exists a protocol for
$G$ that is $t$-resilient against passive adversaries, then for any
$\computef$ and $c$ there exists a $(k^{-c},t)$-fair protocol for $\computef$ that is resilient against fail-stop adversaries.  If
$\computef$ is described by a circuit family $C_{\computef^{n,m}},$ the
protocol requires $O(\size(C_{\computef^{n,m}})^{c_0})$ bits and
$O(\depth(C_{\computef^{n,m}})^{c_0})$ rounds of interaction
for some fixed $c_0.$

If any player halts, broadcast .

If any player broadcasts , halt and output .

Run to supply each player $i$
with $\piece_i(F(x_1,\ldots,x_n)).$

Run to compute $\piece_i(c_j)$ for player $i,$

where $c_j \leftarrow \bias(\frac{1}{k}).$

Run on $\{\piece_i(F),\piece_i(c_j)\}_{i\in [n]}$

to compute and reveal $F \oplus c_j.$

Protocol to evaluate $F(x_1,\dots,x_n),$
against a fail-stop adversary.
For $O(k^{-c})$-fairness, replace $k$ by $k^{c}.$
Biased coins $c_1,\ldots,c_{k^3+1}$ may also be computed beforehand
and masked with $F$ all at once, so that the bulk of the protocol (Step
(EF2)) becomes simply a gradual disclosure of $F,$ secret by secret.

Let $\computef$ and $c$ be arbitrary.  Lemma <ref> states
that there exists a $(k^{-c},t)$-fair protocol $\idcoin$ for $\computef.$
The condition of the theorem states that there exist protocols
$\protoname(1),\ldots,\protoname(R(n,m))$ for each step of $\idcoin$ that
are $t$-resilient against passive adversaries.  By Lemma <ref>,
protocols $\fs(\protoname(1)),\ldots,\fs(\protoname(R(n,m)))$ are
$t$-semi-resilient against fail-stop adversaries, and
Lemma <ref> concludes that their composition is
$(k^{-c},t)$-fair and resilient against fail-stop adversaries.

§ DEGREE REDUCTION: PASSIVE FROM TWO-PARTY PROTOCOLS

Let us assume either that a black box for two-party function evaluation
exists (i.e., in the formal model for protocol execution, two players
write values on a special tape, and in the next round the result of a
particular function $f(x_1,x_2)$ is written on another tape for them to
read) or that some such protocol exists (i.e., a 2-resilient protocol
admitting an appropriate interface).  Based on two-party
function evaluation, we show how $n$ parties can achieve the same result:
general function computation.

We consider secret sharing with a threshold of $n-1.$  In this case, $n$
players are needed to determine a secret, and sharing reduces essentially to
a form we call sum-sharing,
secret sharing!sum
sum sharing
which can be regarded as a
generalization of parity-sharing (sum modulo 2) originally developed by
Haber [78], and applied to improve message complexity
and to protect information of faulty players in [65].
In particular, a secret is represented as a sum of all
pieces, where the pieces arise by selecting $n$ random field elements
subject to their sum being the secret.
[We leave it to the
interested reader to identify the simple correspondence between
polynomial secret sharing having threshold $n-1$ and sum sharing.]
Addition remains easy (add pieces individually), but multiplication is again
somewhat more difficult.  Our solution, independently derived, generalizes
the parity-based method of Haber and Micali.

Protocols for sum sharing and secret addition are listed in Figures
<ref> and <ref>.
For multiplication of secrets $a$ and $b,$ each
player must receive a piece $\piece_i(ab).$  Noting that

\[
ab =
(\sum_{i=1}^n \piece_i(a)) (\sum_{j=1}^n \piece_j(b))
\]

we see that for every combination of $i$ and $j,$ player $i$'s piece of $a$
must be multiplied by player $j$'s piece of $b;$ the sum of these products
is $ab.$  It would not do for player $i$ to know
$\piece_i(a)\cdot\piece_j(b),$ for then it could easily calculate
$\piece_j(b).$  In fact, we use a two-party protocol for player $i$ and
player $j$ to calculate the values $(\piece_i(a)\piece_j(b) + r_{ij})$ and
$(-r_{ij}),$ where $r_{ij}$ is a uniformly random field element.
Each receives
one of these values.  No information is revealed, however, since each value
by itself is uniformly random.  On the other hand, the sum of the two values
is the desired contribution to the final result, namely the pairwise product
$\piece_i(a)\piece_j(b).$  Summing over all results of all two-party
combinations gives the desired result, $ab;$ thus the sum of each player's
individual results represents a sum share of $ab.$  That is, the newly
constructed pieces $\piece_i(ab)$ are such that any $n-1$ of them are
distributed uniformly at random, while all $n$ pieces sum to $ab.$  The
protocol is given in Figure <ref>.

0.5in 0.5in 0.7in 0.5in 0.5in 0.5in Phase I (Share):

$(\piece_1(s),\ldots,\piece_n(s)) \leftarrow $

$\uniform(\vec{p} \in E^n \mid \sum p_i = s \}$

$(1 \leq i \leq n)$
$D \rightarrow i:$

Phase II (Reconstruct for $R$):

$(1 \leq i \leq n)$
$\piece_i(s) \rightarrow R.$

Protocol to sum-share a secret, $s.$
Resilient against passive adversaries for any $t.$

$(1 \leq i \leq n)$
$\piece_i(a+b) \leftarrow \piece_i(a) + \piece_i(b).$

protocol to add two secrets shared using the sum representation.