<<

. 18
( 19)



>>

(asymptotically) optimum in for Our protocol has a phase
complexity of


1 Introduction
Consider a synchronous network represented by an undirected graph
where denotes the set of players (nodes) in
* Financial support from Infosys Technologies Limited, India, is acknowledged.
1
A phase is a send from S to R or from R to S or both simultaneously.

M. Franklin (Ed.): CRYPTO 2004, LNCS 3152, pp. 545“561, 2004.
© International Association for Cryptologic Research 2004
TEAM LinG
546 K. Srinathan, Arvind Narayanan, and C. Pandu Rangan

the network that are connected by 2-way communication links as defined by
The players S and R do not trust the network connecting them.
Nevertheless, the sender S wishes to securely send a message to the receiver R
through the network. Security here means that R should receive exactly what
S sent to him while other players should have no information about it, even
if up to of the players (excluding S and R) collude and behave maliciously.
This problem, known as perfectly secure message transmission (PSMT), was first
proposed and solved by Dolev et al.[3]. In essence, it is proved in [3] that PSMT
tolerating a static2 adversary that corrupts
from S to R across the network
up to players (nodes), is possible if and only if is at least
3
. We use the approach of [3] and abstract away the network entirely
and concentrate on solving the PSMT problem for a single pair of synchronized
processors, the Sender S and the Receiver R, connected by some number of
wires denoted by We may think of these wires as a collection of
vertex-disjoint paths between S and R in the underlying network4.
The PSMT problem is important in its own right as well as a very useful
primitive in various secure distributed protocols. Note that if S and R are con-
nected directly via a private and authenticated link (like what is assumed in
generic secure multiparty protocols [15,6,1,12]), secure communication is triv-
ially guaranteed. However, in reality, it is not economical to directly connect
every two players in the network. Therefore, such a complete network can only
be (virtually) realized by simulating the missing links using SMT protocols as
primitives.
In this paper, we shall use the simple and standard model of a synchronous
network wherein any communication protocol evolves as a series of phases, during
which the players (S or R) send messages, receive them and perform (polynomial
time) local computations according to the protocol.
There are three basic aspects contributing to the quality of an algorithm for
PSMT: the maximum tolerable number of faulty wires, the number of phases
and the total number of bits sent The optima for the above quality parameters
are as follows: The lower bound for is proved in this
work to be bits when for any
In the last few years, there have been some attempts toward improving the
quality of protocols. All protocols proposed so far, securely communicate an
element of a finite field extending this to securely communicate field elements
would result in a proportional increase of communication complexity. Dolev et
al. [3] proposed three protocols: the first one with
field elements, the second one with field elements
2
By static adversary, we mean an adversary that decides on the set of players to
corrupt before the start of the protocol.
3
We say that a network is if the deletion of no or less
nodes from disconnects and
4
The approach of abstracting the network as a collection of wires is justified using
Monger™s theorem [8] which states that a graph is if and only if
S and R are connected by at least vertex-disjoint paths.

TEAM LinG
Optimal Perfectly Secure Message Transmission 547

and the third one with and not polynomial in This was
substantially improved by the protocol of [13], that has and
field elements. The protocol of [14] has and
field elements.
However, no known protocol is simultaneously optimal in both and In
this paper, we present (in Section 4.1) an (asymptotically) optimal protocol to
perfectly securely transmit a message consisting of field elements, viz., our
protocol has and field elements, if Since
we require the field size to be at least this means that the message size is

Unfortunately, due to the stringent requirements of privacy and reliability,
(even optimal) PSMT protocols are not always as efficient as we would like them
to be in practice. Therefore, one often relaxes either the reliability or the privacy
requirement, or both, and tries to achieve statistical reliability/privacy.
Thus, we look for protocols in which the probability that R will receive the
correct message is and the probability that the adversary will learn the
message is for arbitrarily small and Of course, PSMT is the case
broadcast satisfies and so on. In [5], a with
and field elements was presented to securely communicate one
field element. For an extensive discussion of protocols see [5].
In this paper we introduce a new way of relaxing the requirements. We study
the average case efficiency of SMT protocols, rather than the worst case. We do
not require that the worst case complexity be polynomially bounded, or even
finite; we feel that nonterminating protocols that nevertheless complete quickly
with high probability and have perfect security and reliability are very useful
constructions.
In Section 5 we present an optimally fault-tolerant protocol that terminates
in a single with high probability, and having field elements. We note that
the significance of a single phase protocol is more than merely a gain in efficiency
(in terms of network latency): S and R are not required to be on the network
at the same time for executing a single phase protocol, and therefore they are
applicable in a much bigger set of scenarios than are multi-phase protocols.
Most of the results in the literature model the sender™s distrust in the network
via a centralized static adversary that can corrupt up to of the wires and
assume the worst-case that the adversary can completely control the behavior
of the corrupted wires [3,13]. In line with this, we assume up to section 6 that
the adversary is static, i.e., he (a) decides on the set of wires to corrupt before
the start of the protocol and (b) a wire once corrupted remains so subsequently.
However, in practice the bound on the number of corrupted wires may depend
on the total time of the protocol execution. Thus motivated, in section 6 we model
the faults via a mobile adversary, in line with [10]. In this model, the adversary
can corrupt any set of wires in the lifetime of the protocol but is constrained to
corrupt at most wires in any single phase of the protocol.
We show that our ideas in the case of static adversaries can be extended
to withstand mobile adversaries. We prove that the lower bound of

TEAM LinG
548 K. Srinathan, Arvind Narayanan, and C. Pandu Rangan

for reliable message transmission holds for mobile adversaries irrespective of the
number of rounds. We also give a bit-optimal protocol when

2 Preliminaries
Notation. Throughout the paper, we use M to denote the message that S wishes
to securely communicate to R. The message is assumed to be a sequence of
elements from the finite field The only constraint on is that its size must be
no less than the number of wires Since we measure the size of the message in
terms of the number of field elements, we must also measure the communication
complexity in units of field elements; we follow this convention in the rest of
the paper. We assume that there exists a publicly specified one-to-one mapping
For convenience, we use to denote
We say that a wire is faulty if it is controlled by the adversary; all other
wires are called honest. A faulty wire is corrupted in a specific phase if the value
sent along that wire was changed. When the context makes clear which phase
is being referred to, we simply say that a wire is corrupted. Observe that a wire
may be faulty but not corrupted in a particular phase.

2.1 Efficient Single Phase Reliable Communication
To reliably communicate a message m, a sequence of field elements, to R,
one simple way is for S to send m along each wire “ i.e, broadcast. However,
when where out of wires are corrupted, broadcast, requiring
O(nk) field elements, is not the most efficient method of (single phase) reliable
communication. Instead, it is possible to use an error-correcting code to improve
the communication complexity of reliable communication to field elements.
A block error correcting code encoding a message of field elements to a codeword
of symbols is an injective mapping The encoding function
is used in conjunction with a decoding function with the property
that if its input differs from a valid codeword in at most field elements, then
outputs the message corresponding to that codeword. We say that the code
corrects errors. Clearly, such a decoding function will always exist if any two
valid codewords differ in at least symbols, that is, the distance of the code

The efficiency of an error correcting code is subject to the Singleton bound:
Lemma 1. Let C be a block code which reliably transmits field elements by
communicating a total of field elements and has a distance of Then

We observe that for a correcting code, the distance (which is the
minimum Hamming distance between any two codewords) is at least Thus
we have
Corollary 1. Let C be a correcting block code as in lemma 1. Then


TEAM LinG
Optimal Perfectly Secure Message Transmission 549

We now consider a special class of error correcting codes called Reed-Solomon
codes (RS codes).
Definition 1. Let be a finite field and be a collection of distinct
elements of Given and a block the encod-
ing function for the Reed-Solomon code is defined as
where is the polynomial
Theorem 1 ([7]). The Reed-Solomon code meets the Singleton bound.
The following special property of the RS-code will be of use in our subsequent
discussion:
Lemma 2. Let be an of B. Then
for any any subsequence of of length
forms a valid of B.
Proof: Easy observation.
Constructing message transmission protocols using error correcting codes is a
typical application, for example see [2,11]. We now describe
a protocol for reliable communication obtained by using the corresponding Reed-
Solomon code will be used as a sub-protocol later on.




We note that the resulting protocol is a single phase protocol. The reverse
process is equally valid - given a single phase reliable communication protocol, we
can convert it into a block error correcting code. Thus, the maximum attainable
efficiency for single phase reliable communication is also subject to the Singleton
bound.
Remark: This conversion to an error correcting code is straightforward if the
messages sent along each wire in the protocol are of the same length. Suppose,
however, that there is exists a protocol that does not have this symmetry
property and beats the Singleton bound. Then consider the protocol which
consists of sequential executions of protocol with the identities or numbers
of the wires being “rotated” by a distance of in the execution. Clearly, this
protocol achieves the symmetry property by “spreading the load”; further its
message expansion factor is equal to that of It therefore beats the Singleton
bound as well, which is a contradiction.
TEAM LinG
550 K. Srinathan, Arvind Narayanan, and C. Pandu Rangan

Lemma 3. Suppose that the receiver R knows faults among the wires, and
be the number of faulty wires apart from those Then
works if

Proof: Since R knows faults, he simply ignores those wires; and by lemma 2,
this converts the code into an RS code with parameters and The result
now follows from lemma 1 and theorem 1.

2.2 Extracting Randomness
In several of our protocols we have the following situation: S and R by some
means agree on a sequence of numbers such that
The adversary knows of the components of x
The adversary has no information about the other components of x
S and R do not necessarily know which values are known to the adversary.
The goal is for S and R to agree on a sequence of numbers
such that the adversary has no information about This is achieved
by the following algorithm:




Lemma 4. The adversary has no information about in algorithm
EXTRAND.
Proof. We need to show that there is a bijective mapping between the tuple
of values that are not known to the adversary and the tuple But
this is a direct consequence of the fact that every in an
Vandermonde matrix is nonzero.

3 Lower Bound on Communication Complexity
Theorem 2. Any 2-phase perfectly reliable message transmission (PRMT) of
bits requires communicating

We first observe that a probabilistic polynomial time (PPT) protocol for PRMT
with a worst-case communication complexity of bits exists if and only if there is
a deterministic protocol with the same communication complexity. Since perfect
reliability is required, the algorithm must succeed for every possible choice of
coin tosses; in particular, it must succeed when all the random bits of S and R
are zeroes. Thus we convert any PPT protocol into a deterministic protocol by
fixing the sequence of coin-tosses to all zeros. Hence, we assume that S and R
are deterministic polynomial time algorithms.
TEAM LinG
Optimal Perfectly Secure Message Transmission 551

We recall that in a phase, both S and R may simultaneously send messages
to the other player. If this happens we call it a bidirectional phase. On the other
hand, if only one of the players sends a message, we call it a unidirectional phase.
Without loss of generality we assume that in the first phase communication
is from R to S and in the second phase it is from S to R. (Clearly there is no
point in communication from R to S in the second phase; similarly if S sends
any messages to R in the first phase we can consider these to be part of the
second phase as well.) In the rest of the paper we assume that communication
in each phase is unidirectional.
We prove the stronger statement that any 2-phase PRMT of bits requires
communicating t least bits even against a weaker adversary, namely, one
that is passive in the first phase.
Thus, let be a two phase protocol in which is the totality of messages
sent by R to S in phase I and the totality of messages sent by S to R in
phase 2. The steps of are as follows:

1. R computes and sends it to S.
2. S, using and the message computes and sends it to R.
3. R recovers the message using

In the above protocol, we see that step 1 is “useless”: consider the protocol
in which step 1 is replaced with the following step:
S and R both locally compute by simulating R™s execution in step 1 of
(Since the adversary is passive, is guaranteed to have been received by S
in the first phase of
It is clear that succeeds whenever succeeds.
being a single phase protocol, can also be viewed as an error correcting
code. That is, the concatenation of the data sent along all the wires forms the
codeword. Let be the set of possible values of the data sent along the wire
Thus, each codeword is of length at least consisting of elements
one from each Now, the removal of any elements from each
of the codewords should result in shortened codewords that are all distinct.
For if any two were identical, the original codewords could have differed only
among at most elements implying that there exist two original codewords
and and an adversarial strategy such that the receiver™s view is the same on
the receipt of either or In more detail, without loss of generality assume
that and differ only in their last elements. That is, and
where denotes concatenation and elements. Let
denote the first elements of while be the last elements. That is, let
Similarly, let
Now, consider the two cases: (a) is sent and the adversary corrupts it to (by
corrupting the last wires and changing to and (b) is sent
and the adversary corrupts it to (by corrupting the penultimate set of wires
and changing to Thus, the receiver cannot distinguish between
the receipt of and which violates the reliable communication property.
Therefore, all shortened codewords are distinct and there are as many shortened
TEAM LinG
552 K. Srinathan, Arvind Narayanan, and C. Pandu Rangan

codewords as original codewords. But the number of shortened codewords is at
most the minimum among all sized subsets
of Thus we may sort the in a non-decreasing order and multiply
the first values to obtain the number of original codewords denoted by C.
Thus, reliable communication of bits incurs a communication cost of
at least bits. But Thus, in the best case all the
domains are of equal size and is thus subject to the Singleton bound. By corollary
to lemma 1, reliable communication of bits incurs a communication
cost of bits. Since communicates an bit message, it follows that has a
communication complexity of bits.
Corollary 2. Any 2-phase perfectly reliable message transmission (PRMT) of
field elements requires communicating field elements.
The above corollary follows from the fact that a field element can be repre-
sented as a string of bits.

4 An Optimal Protocol for PSMT
4.1 The PSMT Protocol
In this section, we present our 2-phase protocol for PSMT for any message that
is a sequence of field elements, with and field elements,
for a sufficiently large It turns out that we require
Suppose that there exists a protocol that securely transmits a message con-
sisting of field elements with and field elements.
It is evident that for any integer t j field elements can be sent in
field elements whilst maintaining and this is because we can
run the sub-protocols in parallel. Setting we obtain a protocol that
communicates field elements by sending field elements. Thus, our goal
now reduces to the design of a protocol that achieves secure transmission of
field elements over a network of wires, in two rounds by communi-
cating field elements. We now present one such protocol. Specifically,
our protocol sends field elements by sending O(nt) field elements.
In our protocol, the first phase is a send from R to S and the second phase is
from S to R. We denote the set of wires by We assume
that S wishes to communicate a block, denoted by m, that consists of field
elements from
Phase I (R to S)
The receiver R selects at random polynomials over each of
degree
Next, through each wire R sends the following to S:
The polynomial 5.
For each the value of (which we denote by where
are arbitrary distinct publicly specified members of
5
We assume that the polynomial is sent by sending a of field elements.
TEAM LinG
Optimal Perfectly Secure Message Transmission 553

Phase II (S to R)
S begins this phase after receiving what R has sent in the first phase. Let S
receive the polynomial and the values along the wire In this phase, S
must locate all the corruptions that occurred in the previous phase, communicate
the corruptions and send the message securely. A naive and straightforward way
of doing this is as follows: communicate the list of contradictions (we say
that wire contradicts wire if among the wires (in the worst case).
However, there are two problem with this approach: (a) the method requires
communicating field elements, and (b) such an approach necessitates more
than two phases.
We solve the former problem by using a two step technique to communicate
the list of contradictions. In the first step we broadcast a selected set of contra-
dictions; this will enable the players to find sufficiently many faults to facilitate
sending the remaining contradictions in field elements using the REL-
SEND protocol in the second step. The second problem is solved using some
new techniques described in the sequel.

S™s computation.

S initializes his fault-list, denoted by to
S constructs a directed graph where arc if

Let be the undirected graph based on G; that is,
if or
For each such that the degree of node in the graph H
constructed above is greater than (i.e., S adds to

Let be the induced subgraph of H on the vertex set

Next, S finds a maximum matching6 of the graph this can be
done efficiently using the algorithms of [4, 9].
For each arc in G that does not belong to M, S associates the four-
tuple Let be the arcs in G that are not
in M. Replacing each arc with its associated 4-tuple, S gets a set of 4N field
elements,
Let Next, S creates the message-carrying polynomial
as follows: let




6
A subset M of the edges of H, is called a matching in H if no two of the edges in
M are adjacent. A matching M is called maximum if H has no matching with a
greater number of edges than M has.

TEAM LinG
554 K. Srinathan, Arvind Narayanan, and C. Pandu Rangan

S initializes the set Y as follows:



Finally, the sender S selects at random polynomials over
each of degree such that the values lie on a polynomial of degree

S computes
For each let denote the value of With each of the
arcs in the graph G, S associates the four-tuple and
He initiates the set Z in similar lines as X to contain field
elements.

S™s communication.

S sends the following to R through all the wires:

1. The blinded message
2. The set
3. For each edge the following four field elements: and


Along each wire S sends the following as specified by the REL-SEND(·, ·)
Algorithm:

1.
2.
3.

Again, through each wire S sends the following to R:

The polynomial
For each the value of

Message recovery by R.
R receives what S sent in the second phase and locally deciphers the message
m as follows:

1. R reliably receives and knows that the wires in this set are faulty. He
initializes
2. For each arc reliably receives and He
locally verifies: and If the former check fails (that
is the values are unequal), then R adds to If the latter check fails,
then R adds to (note that both and may be identified as
faulty; in any case, at least one of them is guaranteed to be found faulty).
Thus, at least new faults are caught in this step.
TEAM LinG
Optimal Perfectly Secure Message Transmission 555

3. From Lemma 5, it is clear that R receives the set X reliably. Again R locally
verifies for each arc™s (say 4-tuple: and
If the former check fails (that is the values are unequal), then R adds
to If the latter check fails, then R adds to At the end of
this step, all the faults that occurred during transmission in Phase I are
guaranteed to have been identified (see Lemma 6).
4. We know from Lemma 5 that the R receives the set Y correctly. If the
number of faults (which are not in that occurred in Phase I was
then in the polynomial R has unknowns and equations
(which are bound to be consistent whatever the number of unknowns may
be, since all faults have been eliminated). Thus, in this case, R obtains the
message m.
5. Similarly, from Lemma 5, we know that R receives the set Z correctly. If
the number of faults (which are not in that occurred in Phase I was
then from Lemma 9, we know that R can obtain the message using
the polynomials and Z. Thus, in this case too, R obtains the message
m.

Lemma 5. R is guaranteed to receive the sets X, Y and Z correctly.

Proof: From lemma 3, the protocol succeeds provided that
here, and Therefore,
REL-SEND succeeds if or if,
Since, R is guaranteed to have identified at least
faulty wires at this stage, the lemma follows.

Lemma 6. If the set X was received correctly, then R can find all the corrup-
tions that occurred during Phase I.

Proof: Suppose wire was corrupted in Phase I, i.e, Then the two
polynomials can intersect in at most points. Since there are honest wires,
there is guaranteed to be at least one honest wire which contradicts Since
the correct values corresponding to every contradiction have been received by
R, R can find all the corruptions.

Lemma 7. If the number of corruptions that occurred in Phase I was R
obtains the polynomial correctly.

Proof: To find the message R must find the polynomial To find R
must find for Of these R does not yet know for
and does not know of the a total of at most
field elements. But the set Y gives R values of which yield linear
equations on the coefficients, and using these values R can determine all

Lemma 8. For some if the wire was corrupted in Phase I then R can
correct any corruption of the corresponding in Phase II.
TEAM LinG
556 K. Srinathan, Arvind Narayanan, and C. Pandu Rangan

Proof: Let the in-degree of in G be Then there must have been at least
corruptions in Phase I (since the number of honest wires is
Thus in the second phase, there are at most legitimate
wires. The maximum number of faults that R needs to correct in this phase is
We verify that these parameters satisfy the constraint in
lemma 3, and therefore R will be able to correct all corruptions of
Lemma 9. If the set Z was received correctly and if the number of faults that
occurred in Phase I was then R can obtain the message m.
Proof: By lemma 8, R can correct all except a maximum of of the The
degree of the polynomial that they lie on is since these parameters satisfy
the constraints of lemma 3, it follows from the correctness of the REL-SEND
protocol that R can obtain all the and hence m.
Theorem 3. The protocol presented in Section 4.1 achieves perfect reliability.
Proof: Perfect reliability is a consequence of lemmas 7 and 9.
Lemma 10. For every honest wire the adversary has no information about
and

Proof: Obvious. is a random polynomial of degree but the adversary has
seen only points on it. The same argument holds for as well.
Theorem 4. The protocol presented in Section 4.1 achieves perfect security.
Proof (sketch): First we prove that the adversary has no information about the
coefficients of the polynomial There are at least values
of which are not known to the adversary. The adversary obtains linear
equations on the coefficients by knowing the values of
which are sent reliably by S. Thus the adversary has linear equations on
unknowns, which implies that he has no information about any
of them.
Next we observe that among the values of the adversary knows
at most and hence by the security of the EXTRAND algorithm (lemma 4) it
follows that the adversary gets no information about m.

4.2 Performance
Theorem 5. Given an undirected graph H = (V, E), with a maximum degree of
and a maximum matching M, the number of edges is less than or equal
to
Proof: We first fix a representation of the maximum matching M as a set of
ordered pairs of vertices as described below.
We say that a vertex belongs to vertex-set of the matching, denoted by
Vertex(M), if there exists another vertex such that the edge
TEAM LinG
Optimal Perfectly Secure Message Transmission 557

vertex is called the match-vertex if the degree of in the subgraph
induced by H over the vertices is
Given a maximum matching M, a match-vertex may have at most one
incident edge in We call the edge as a match-edge (correspond-
ing to the match-vertex We now define X to be the set of all match-edges
(corresponding to each of the match-vertices in M).
Claim. Every edge has at least one match-vertex.
Proof: On the contrary, if neither nor was a match-vertex, then, both and
are adjacent to at least two vertices in (V \ Vertex(M)). Let be adjacent to
vertices and in (V\Vertex(M)) and let be adjacent to a vertex in
(V \ Vertex(M)). Now, removing the edge from M and adding the edges
and to M gives rise to a new matching in H of size which
contradicts the maximality of the matching M. Hence the claim holds.
Hereafter, we represent every edge in as if and only if is a
match-vertex; in case of both and being match-vertices, is the one with the
lower number of corresponding match-edges (ties broken by random choice). We
fix one such representation of the edges in To avoid confusion between
the unordered pair and the ordered pair used in the representation of an
edge in hereafter, we denote the ordered pair as A vertex belonging
to Vertex(M) is called a left-vertex if, in the representation of M that we fixed
earlier, there exists a vertex such that We call all the non-left-
vertices belonging to M as right-vertices.
Note that the number of left-vertices is equal to the number of right-vertices
is equal to Also note that by definition, every left-vertex is a match-vertex.
Now, it is easy to place an upper bound on as follows: the maximum
number of edges among the vertices in Vertex(M) is Again,
the maximum number of edges from the left-vertices to is
since each left vertex is a match-vertex (having at most one edge to
and there are left vertices. Furthermore, each right vertex can
have at most edges to (by the definition of Thus,

Theorem 6. The PSMT protocol presented in Section 4.1 communicates
field elements in order to securely transmit field elements.
Proof: We have already proved that the protocol securely transmits field ele-
ments. From the description of the protocol, it is easy to verify that all steps ex-
cept possibly the invocations of REL-SEND(X,.) and REL-SEND(Z,.) in Phase
II have a communication cost of field elements. Since the maximum degree
of a node in is at most and is also at most from theorem 5 it
follows that (and hence also is Since the efficiency
of is the theorem follows.
The main result now follows from the discussion at the beginning of Section 4.1:
Corollary 3. There exists a 2-round PSMT protocol that securely communicates
a message consisting field elements and has a communication complexity of
field elements when if
TEAM LinG
K. Srinathan, Arvind Narayanan, and C. Pandu Rangan
558

5 A Las Vegas Single Phase Protocol
In this section we present an optimally tolerant PSMT pro-
tocol which terminates in a single phase with (arbitrarily) high probability.
We represent the block of field elements m that S wishes to send to R as




Let be a bound on the probability that the protocol does not terminate
in a single phase. We require that the size of the field be for some
polynomial but this is of course acceptable since the complexity of the
protocol increases logarithmically with field size. We now discuss the correctness
of the protocol.
Lemma 11. R will never output an incorrect value.
Proof. Since any corruption involves changing the polynomial corresponding to
that wire, it is clear that no corrupted wire can escape contradiction by at least
one other wire. If and agree on points (corresponding to the
honest wires) then and must be equal. Therefore, at the start of step 7, all
the wires which were used in calculation of the output could not have corrupted
their values. This guarantees that R™s output in step 8 is correct.
Lemma 12. The protocol terminates in a single phase with high probability.
TEAM LinG
Optimal Perfectly Secure Message Transmission 559

Proof. Since no uncorrupted wire changes the value sent on the wire, it follows
that no honest wire can contradict another honest wire. Thus, if wire contra-
dicts wire then either wire or wire is faulty. From this it is easy to see that
an honest wire can be contradicted by at most other wires, and therefore any
wire that is contradicted or more wires has to be faulty. Hence R can be
sure that all the wires removed by him are indeed faulty.
We need to show that if a wire is corrupted, then it will be contradicted by
all the honest players with high probability. Let be the probability that the
corrupted wire will not be contradicted by This means that the adversary
can ensure that with a probability of Since there are only
points at which these two polynomials intersect, this allows the adversary to
guess the value of with a probability of at least But since was selected
uniformly in the probability of guessing it is at most Therefore we have
for each Thus the total probability that the adversary can find
such that corrupted wire will not be contradicted by is at most
Since is chosen such that it follows that the protocol terminates
in a single phase with probability if we set
Lemma 13. The adversary gains no information about the message.
Proof: We observe that the adversary has no information about for each
honest wire This is because is a random polynomial of degree and the
adversary has seen only points on it (one corresponding to each faulty wire.)
The proof now follows from lemma 4.


6 Mobile Adversaries
6.1 Lower Bound on Bit Complexity
The lower bound on the bit complexity of perfectly reliable message transmission
proved in section 3 holds for mobile adversaries with no restriction on the number
of phases. We give below a brief sketch of the proof.
Since the adversary can corrupt a different set of wires in each phase, the
protocol cannot adapt as it finds corrupted wires; thus it can be considered to be
memoryless. Therefore the total number of bits transmitted reliably is no more
than the sum of the number of bits transmitted reliably in each phase; we have
already shown in section 3 that the Singleton bound implies a lower bound of
for a single phase; therefore this bound holds for multiple phase protocols
as well.

6.2 An Optimal Protocol
The protocol with optimal fault tolerance and optimal communication complex-
ity is presented below. Let m be a block of field elements that S wishes to
communicate securely to R.
TEAM LinG
560 K. Srinathan, Arvind Narayanan, and C. Pandu Rangan




Theorem 7. The adversary gains no information about the message.
Proof: First we note that at the end of the first phase, the adversary has no
information about for each honest wire This is because is a random
polynomial of degree and the adversary has seen only points on it (one
corresponding to each faulty wire.) Furthermore, the adversary gains no new
information in step 2. This can be seen as follows: each phase in step 2 involves
broadcast of the 4-tuple Since either wire or wire is faulty,
this information is already known to the adversary. The other information that
is broadcasted is which of wire and wire is faulty, which is also known to
the adversary. The theorem follows.

6.3 Complexity
The first phase of the protocol involves communication of field elements.
In step 2, each phase of communication results in the elimination of one wire.
Therefore the number of phases in this step is Since each phase involves
the broadcast of field elements, step 2 has a communication complexity
of field elements. The final phase involves broadcast a string of length
field elements. Therefore the entire protocol has communication complex-
ity field elements. Thus the protocol for a message M consisting of an
arbitrary number of field elements obtained by executing this protocol in par-
allel times has a communication complexity of field elements, which
is optimal when
TEAM LinG
Optimal Perfectly Secure Message Transmission 561

7 Conclusion
In this paper we have contributed significantly to the progress of the state of the
art in the problem of Perfectly Secure Message Transmission. The protocol of
section 4.1 constitutes a major improvement over existing protocols tolerating
static adversaries; in fact we have achieved the optimal communication complex-
ity when and The protocol can be extended to achieve the
optimal communication complexity when as well, though we have
not presented it here. It would be interesting to see if the lower bound we have
proved in section 3 holds when as well (for PSMT); we conjecture that it
does.
Perhaps our most interesting result is the average case single phase PSMT
protocol. It is in fact surprising that such a protocol even exists; in addition our
protocol is also very efficient in terms of communication complexity.

References
1. M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-
cryptographic fault-tolerant distributed computation. In 20th ACM STOC, pages
1“10, 1988.
2. Y. Desmedt and Y. Wang. Perfectly secure message transmission revisited. In EU-
ROCRYPT ™02, volume 2332 of LNCS, pages 502“517. Springer-Verlag, 2002.
3. D. Dolev, C. Dwork, O. Waarts, and M. Yung. Perfectly secure message transmis-
sion. JACM, 40(l):17“47, January 1993.
4. J. Edmonds. Paths, trees and flowers. Canadian Jl. of Math., 17:449“467, 1965.
5. M. Franklin and R.N. Wright. Secure communication in minimal connectivity mod-
els. Journal of Cryptology, 13(1):9“30, 2000.
6. O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In 19th
ACM STOC, pages 218“229, 1987.
7. F. J. MacWilliams and N. J. A. Sloane. The Theory of Error Correcting Codes.
North Holland Publishing Company, 1978.
8. K. Menger. Zur allgemeinen kurventheorie. Fundamenta Mathematicae, 10:96“115,
1927.
S. Micali and V. Vazirani. An algorithm for maximum matching in
9.
general graphs. In 21st IEEE FOCS, pages 17“27, 1980.
10. R. Ostrovsky and M. Yung. How to withstand mobile virus attacks. In 10th ACM
PODC, pages 51“61, 1991.
11. M.O. Rabin. Efficient dispersal of information for security, load balancing, and
fault tolerance. JACM, 36:335“348, 1989.
12. T. Rabin and M. Ben-Or. Verifiable secret sharing and multiparty protocols with
honest majority. In 21st ACM STOC, pages 73“85, May 1989.
13. H. Sayeed and H. Abu-Amara. Efficient perfectly secure message transmission in
synchronous networks. Information and Computation, 126(1):53“61, 1996.
14. K. Srinathan, V. Vinod, and C. Pandu Rangan. Brief announcement: Efficient
perfectly secure communication over synchronous networks. In 22nd ACM PODC,
page 252, 2003.
15. A. C. Yao. Protocols for secure computations. In 23rd IEEE FOCS, pages 160“164,
1982.


TEAM LinG
Pseudo-signatures, Broadcast, and Multi-party
Computation from Correlated Randomness

Matthias Fitzi1, Stefan Wolf2, and Jürg Wullschleger2
1
Department of Computer Science
University of California, Davis, USA
fitzi@cs.ucdavis.edu
2
D©partement d™Informatique et R.O.
Universit© de Montr©al, Canada
{wolf,wullschj}@iro.umontreal.ca




Abstract. Unconditionally secure multi-party computations in general,
and broadcast in particular, are impossible if any third of the players can
be actively corrupted and if no additional information-theoretic primitive
is given. In this paper, we relativize this pessimistic result by showing
that such a primitive can be as simple as noisy communication channels
between the players or weakly correlated pieces of information. We con-
sider the scenario where three players have access to random variables
X, Y, and Z, respectively, and give the exact condition on the joint dis-
tribution under which unconditional broadcast is possible. More
precisely, we show that this condition characterizes the possibility of real-
izing so-called pseudo-signatures between the players. As a consequence
of our results, we can give conditions for the possibility of achieving un-
conditional broadcast between players and any minority of cheaters
and, hence, general multi-party computation under the same condition.
Keywords: Unconditional security, pseudo-signatures, broadcast, multi-
party computation, information theory.


1 Motivation and Preliminaries
1.1 Introduction
Digital signatures [11,19] are a powerful tool not only in the context of digital
contract signing, but also as a basic primitive for cryptographic protocols such
as electronic voting or secure multi-party computation. Much less known are
so-called pseudo-signature schemes, which guarantee unconditional security”in
contrast to classical digital-signature schemes. The inherent price for their higher
security, however, is the signatures™ limited transferability: Whereas classical
signatures can be arbitrarily transfered without losing conclusiveness, pseudo-
signatures only remain secure for a fixed number transferability”of trans-
fers among different parties. Since the necessary number of signature transfers
in a protocol is typically bounded by the number of involved parties, pseudo-
signatures are, nevertheless, useful and offer a provably higher security level than

M. Franklin (Ed.): CRYPTO 2004, LNCS 3152, pp. 562“578, 2004.
© International Association for Cryptologic Research 2004
TEAM LinG
Pseudo-signatures, Broadcast, and Multi-party Computation 563

traditional signature schemes. For example, the authenticated broadcast proto-
col in [13] can be based on pseudo-signatures and then guarantees unconditional
(instead of computational) security against any number of corrupted players [25].
A pseudo-signature scheme among a number of players can either be set up
by a mutually trusted party, by a protocol among the players when given global
broadcast channels, or”as we will show”by exploiting an information source
that provides the players with certain correlated pieces of information”a similar
model has been considered in [21] in the context of secret-key agreement.
In this paper, we consider the general case of an information source that pro-
vides a set of players with pieces of information distributed according to some
given joint probability distribution. For the case of three players, we completely
characterize when such an information source allows for setting up a pseudo-
signature scheme. This result can be used for deriving a complete characteriza-
tion of when unconditionally secure three-party computation”or broadcast, in
particular”is achievable in the presence of an actively corrupted player. Fur-
thermore, we give, in the same model, a sufficient condition for the achievability
of unconditionally secure multi-party computation for any number of players
secure against actively corrupted players.

1.2 Context and Previous Work
Pseudo-signature schemes (PSS). The first pseudo-signature-like scheme was
given in form of an information-checking protocol among three players [26]. In
contrast to real pseudo-signatures, however, the signer is required to commit to
her input value already during the setup of the scheme.
The first PSS was introduced in [7] with the restriction to be secure only
with respect to a correct signer. In [25], finally, a complete PSS was proposed
for any transferability and any number of corrupted players.

Setting up a PSS. It was shown in [25] how to set up a PSS using global broadcast
channels, where the dining-cryptographers protocol [5,4] was used. Obtaining a
PSS from a common random source was considered in [15,16], but only with
respect to three players and one particular probability distribution.

Broadcast. The broadcast problem was introduced in [20]. It was proven that,
in the standard model with secure channels between all pairs of players, but
without the use of a signature scheme, broadcast is achievable if and only if
the number of cheaters satisfies Furthermore, it was shown that
when additionally a signature scheme is given among the players, then com-
putationally secure broadcast is achievable for any number of corrupted players.
The first efficient such protocol was given in [12]. In [25], an efficient protocol
was given with unconditional security based on a pseudo-signature scheme with
transferability

Multi-party computation (MPC). Broadcast”or the availability of signatures
with sufficiently high transferability”is a limiting factor for general multi-party
TEAM LinG
564 Matthias Fitzi, Stefan Wolf, and Jürg Wullschleger

computation introduced in [27]. A complete solution with respect to computa-
tional security was given in [18]. In [2,6], it was shown that in a model with
only pairwise secure channels, MPC unconditionally secure against an active
adversary is achievable if and only if players are corrupted. As shown
in [1,26], is achievable when global broadcast channels are additionally
given”and this bound was shown tight. A protocol more efficient than those
in [1,26] was given in [10].

1.3 Our Results
We first consider a set of three players, connected in pairs by secure channels,
where an additional information source provides the players with correlated
pieces of information. We give a necessary and sufficient condition on the joint
probability distribution of this side information for when a pseudo-signature
scheme can be set up among the three players with a designated signer. Fur-
thermore, we show that the tight condition for the achievability of broadcast or
multi-party computation among three players unconditionally secure against one
actively corrupted player is exactly the same as the one for a pseudo-signature
scheme with respect to an arbitrary. The derived condition shows that pseudo-
signature schemes and broadcast among three players are possible under much
weaker conditions than previously known.
We further consider the general case of players, connected in pairs by
secure channels, where, again, an additional information source provides the
players with side information. For this model, and under the assumption that
an active adversary can corrupt up to players, we show that MPC is
possible under much weaker conditions than previously known.

1.4 Model and Definitions
We consider a set of players that are connected by a com-
plete, synchronous network of pairwise secure channels”in the presence of an
active adversary who can select up to players and corrupt them in an arbitrary
way. Furthermore, we assume this adversary to be computationally unbounded.
A player which does not get corrupted by the adversary is called correct.

Pseudo-signatures. We follow the definition of pseudo-signature schemes as
given in [25].

Definition 1. A pseudo-signature scheme (PSS) with transferability among
the players where is the signer, satisfies the following properties.
Correctness. If player is correct and signs a message, then a correct player
accepts this message from except with small probability.
Unforgeability. A correct player rejects any message that has not been signed
by except with small probability.

TEAM LinG
Pseudo-signatures, Broadcast, and Multi-party Computation 565

Transferability. A message signed by the correct player can be transfered
times, e.g., via

such that we have for each and correct players and that if
accepts a message then accepts the same message except with
small probability.
If the path can be arbitrary, we call the scheme a PSS with arbitrary
transfer paths, if the transfer is restricted to a specific path we call
it a PSS with transfer path
The choice will be sufficient in our case since any such PSS allows for
broadcast for corrupted players [17].

Broadcast and Multi-party Computation. Broadcast is the problem of
having a (possibly corrupted) sender distribute a value to every player such that
all correct players are guaranteed to receive the same value.
Definition 2. A protocol among players where is the sender
and holds input and where every player computes an output achieves
broadcast if it satisfies the following conditions.
Validity. If the sender is correct, then every correct player computes the
output
Consistency. All correct players and compute the same output value, i.e.,
holds.
Broadcast is a special case of the more general problem of multi-party com-
putation (MPC), where the players want to evaluate in a distributed way some
given function of their inputs and hereby guarantee privacy of these inputs as
well as correctness of the computed result. From a qualitative point of view,
the security of multi-party computation is often broken down to the conditions
privacy, correctness, robustness, and fairness. In [8], it was shown that all these
conditions can only be satisfied simultaneously if holds”the case to
which we restrict our considerations in this paper.

2 Dependent Parts and Simulation of Random Variables
In this section we introduce the notion of the dependent part of a random variable
with respect to another, and a certain simulatability condition, defined for a
triple of random variables. The dependent part of X from Y isolates the part of
X that is dependent on Y. Note that we always assume that the joint distribution
is known to all the players.
Definition 3. Let X and Y be two random variables, and let
The dependent part of X from Y is defined as
TEAM LinG
566 Matthias Fitzi, Stefan Wolf, and Jürg Wullschleger

The random variable is a function of X and takes on the value of the
conditional probability distribution

Lemma 1. For all X and Y, we have i.e., the
is a Markov chain1.
sequence

Proof. Let For all range of X”and
we have and, hence,

We will now show that is the part of X that a player who knows
Y can verify to be correct. Lemma 2 shows that every a player knowing X
can construct that has the same joint distribution with Y as the actual K must
indeed be identical with K. Lemma 3 shows that from K, a random variable
can be constructed which has the same joint distribution with Y as X. Hence,
K is the largest part of X that someone knowing Y can verify to be correct.

Lemma 2. Let X, K, and Y be random variables such that
and hold. Then we have

Proof. We have and
Let us have a look at a value for which cannot be expressed as a
linear combination of for with (It is easy to see
that such a must exist.) Let S be the set of all with In order to
achieve no not in S can be mapped to by Since
holds, must map all values from S to
We remove the elements of S from repeat the same argument for the next
and continue this process until is empty. Hence, maps all to
and holds.


Lemma 3. Let X and Y be random variables, and let There
exists a channel is equal to that holds,
where

Proof. Using Lemma 1, we get



The simulatability condition, which allows for determining the possibility of
secret-key agreement over unauthenticated channels, was defined in [22] and
further analyzed in [24]. It defines whether given Z, it is possible to simulate X
in such a way that someone who only knows Y cannot distinguish the simulation
of X from the true X.
1
A sequence of three random variables A, B, C forms a Markov chain, denoted by
if holds or, equivalently, if we have
for all

TEAM LinG
Pseudo-signatures, Broadcast, and Multi-party Computation 567

Definition 4. Let X, Y, and Z be random variables. Then X is simulatable by
Z with respect to Y, denoted by



if there exists a conditional distribution such that holds,
where

Lemma 4. For all we have if and only if



Proof. Let K is a function of X and can be simulated whenever
the same holds for X. On the other hand, let be a channel that simulates
K. It follows from Lemma 3 that there exists a channel is equal
to that the channel simulates X.


Lemma 5. For all we have if and only if


Proof. Suppose first that we have There must exist a channel
such that holds, where Let
and Because of and
we have and It follows from Lemma 2 that
holds. From Lemma 1 follows that We also have
Now,




holds and, hence,
It follows that

Suppose now that we have It follows Let
We get




TEAM LinG
568 Matthias Fitzi, Stefan Wolf, and Jürg Wullschleger

3 Pseudo-signature Schemes
3.1 The Case of Three Players
We will state the exact condition under which a PSS can be set up from correlated
pieces of information. We need the following lemma.
Lemma 6. Let be the probability distribution of three random variables
X, Y, and Z. Then the following three conditions are equivalent:
1. There exist two channels and such that and
hold, where
and
2.
3.
Proof. Lemma 5 implies that 2. and 3. are equivalent. In the following we will
prove that 1. and 2. are equivalent.
Assume that 1. is true. We have for some with
and Let and We have
and From Lemma 2, it follows Since
is a function of we get
Assume now that 2. is true. Hence, there exists a channel such that
holds for Lemma 3 implies that there exists a
channel is equal to that holds. We set
and to get




Our pseudo-signature protocol makes use of typical sequences. Intuitively, a
sequence of independent realizations of a random variable is typical if the actual
rate of occurrences of every specific outcome symbol in the sequence is close to
the probability of this symbol.
Definition 5. [3,9] Let X be a random variable with distribution and range
let be an integer, and let A sequence
TEAM LinG
Pseudo-signatures, Broadcast, and Multi-party Computation 569

is called (strongly) if, for all the actual number of
appearances of in satisfies




It is a consequence of the law of large numbers that for every suf-
ficiently long sequences of independent realizations of a random variable are
with overwhelming probability.

Theorem 1. [3,9] Let be a sequence of independent real-
izations of the random variable X with distribution and range and let
Then



The following protocol allows for signing a bit along the transfer path


Protocol 1 Let be such that does not hold. Let
and Lemma 4 implies that there must exist
such that for all channels the statistical distance between the distributions
and is at least
Let be an even integer, and let be triples
distributed independently according to Let be a security parameter
and be large enough. Let and know and
respectively. Let, finally, be the value wants to sign.

calculates and sends to

checks whether the received and the corresponding are a
sequence with respect to If so, he accepts, calculates
and sends to
checks whether the received and the corresponding are a
sequence with respect to If so, he accepts.

Theorem 2. Let be triples distributed indepen-
dently according to Let and know the values and
respectively. Let be able to send messages to and to
If does not hold and is large enough, then Proto-
col 1 achieves PSS for the three players with the transfer path

Proof. We prove that Protocol 1 implements a PSS. First of all, it follows from
Theorem 1 that the value from a correct sender is accepted by except
with exponentially small probability. If is correct and accepts a value and if
is small enough, Lemma 2 implies that must indeed have sent an arbitrarily
large fraction (for sufficiently large N) of correct values to
TEAM LinG
570 Matthias Fitzi, Stefan Wolf, and Jürg Wullschleger

(Note that the knowledge of the values for do not help to cheat
since they are independent of and
Therefore, also an arbitrarily large fraction of the values
are correct and”if is will accept the values sent to him by
(except with exponentially small probability).
however, cannot (except with exponentially small probability) send any
other value than the one sent by Indeed, his ability to do so would imply
the existence of a channel such that and are identical (see the
proof of Lemma 6 in [23]); such a channel, however, does not exist because of
the assumption stated at the beginning of the protocol.
We now show that the condition of Theorem 2 for the achievability of a
PSS among three players is tight, in other words, that
and imply that no PSS with signer is possible. In
order to demonstrate impossibility, we use a similar technique as in [14]. There,
the impossibility of broadcast among three players secure against one corrupted
player was shown by analyzing a related system obtained by copying some of
the players and rearranging the original players together with their copies in a
specific way.
Theorem 3. Let be triples distributed indepen-
dently according to Let and know the values and
respectively. Let the players be connected by pairwise secure channels.
If and hold, then there does
not exist”for any PSS for the three players with any transfer path and
with as the signer.
and
Proof. Let us assume that there exists a protocol among the players
that achieves a PSS for the three players with transfer path
From Lemma 6, it follows that there exist channels and such that
hold, and such that
and and
hold.
and
Let be an identical copy of We now rearrange the four players
and in the following way to form a new system. The analysis of that
system then reveals that no PSS among the three original players is possible.
Note that, in the new system, no player is corrupted: It is rather the arrangement
of this new system that simulates corruption in the original system towards the
players in the new system.
is still connected to as originally, but disconnected from i.e., all
messages would send to are discarded and no message would send
to is ever received by
is still connected to and as in the original system.
is still connected to as originally, but disconnected from Instead,
is connected to All messages that would send to are delivered
to instead, and all messages would send to are indeed delivered to

is connected to as originally, but disconnected from

TEAM LinG
Pseudo-signatures, Broadcast, and Multi-party Computation 571

Furthermore, instead of let have input and have input Let
them execute their local programs defined by the PSS protocol, where signs
the message and signs the message

Since holds, the joint view among and is indistinguishable
from their view in the original system where holds input and is
corrupted in the following way: cuts off communication to simulates
using the channel to produce the values and and acts
towards as if communicating with instead of (indistinguishability
follows from Hence, by the correctness property, must
accept as signed by
The joint view of and is indistinguishable from their view in the original
system where is corrupted in the following way: simulates player
uses the channel for his own and the channel for input, and
acts towards as Thus, by the transferability property, must accept
the transfered message from
Since holds, the joint view of and is indistinguishable
2
from their view in the original system where holds input and is
corrupted in the following way: cuts off communication to simulates
using the channel to produce the values and and acts towards
as if communicating with instead of (indistinguishability follows
from Hence, by the unforgeability property, must reject
the signature transferred to him by

However, this is impossible since cannot accept and reject at the same
time. The proof for the transfer path is analogous. Hence, there
does not exist a PSS for any transfer path.


If the condition of Theorem 3 does not hold, then there exists a transfer
path”namely either or which Theorem 2
can be applied. Therefore, the bound of Theorem 3 is tight, and we can state
the exact condition under which a PSS for three players and a designated signer
exists.

Theorem 4. Let be triples distributed indepen-
dently according to Let and know the values and
respectively. Let the players pairwisely be connected by secure channels.
There exists a PSS for the three players with transfer path
for large enough if and only if either or
does not hold.

Application of Lemma 5 leads to the following corollary.
2
For simplicity, we assume the original system to consist of the players
for this case.

TEAM LinG
572 Matthias Fitzi, Stefan Wolf, and Jürg Wullschleger

Corollary 1. Let be triples distributed indepen-
dently according to Let and know the values and
respectively. Let the players pairwisely be connected by secure channels.
There exists a PSS for the three players with transfer path
for large enough if and only if either or
does not hold.
We will now present a special case of noisy channels among three players
for which our PSS works. This special case is related to the “satellite scenario”
of [21] for secret-key agreement.
Corollary 2. Let R be a binary random variable and let X, Y, and Z be random
variables resulting from the transmission of R over three binary symmetric chan-
nels with error probabilities and respectively, such that
and hold. Let be
triples generated independently this way. Let and be three players and
assume that they know and respectively. Let, finally, the players pair-
wisely be connected by secure channels. Then, for large enough there exists a
PSS for the three players with arbitrary transfer path.
Proof. We have that and X are”up to renaming”equal, and
neither nor holds.

Corollary 3. Let the players and be connected by a noisy broadcast
channel. This is a channel for which has an input bit X, and and
get output bits Y and Z, respectively, which result from sending X over two
independent noisy channels with error probabilities and
Then a PSS for the three players with arbitrary transfer path can be realized.
Proof. Let the transfer path be sends random bits over the
channel. Both and check whether the received values are indeed random,
that is, whether they are and The values and are chosen
such that even if cheats, does not accept if does not either”except
with small probability. The resulting joint distribution satisfies the condition of
Corollary 2.


3.2 The Case of More Than Three Players
Theorem 2 can be generalized to players in a natural way. Assume
that players want to implement a PSS along the transfer path
Let be lists distributed inde-
pendently according to Let player know the values
As in the protocol for three players, player sends together with his
signature where to is
able to check whether sent the correct values or not, and he only accepts
the signature if almost all values were correct.

TEAM LinG
573
Pseudo-signatures, Broadcast, and Multi-party Computation

Now we let sign the value himself, using the random variable
(Since he only received half of the values he is able to sign but not
He sends where to
Now can check the signature and, if he accepts, sign the value himself,
and so forth. Note that the security parameter for every signature must be less
restrictive than the previous one, because some of the received may have
been faulty. Nevertheless, the error probability remains exponentially small in
Player is not able to forge a signature if


does not hold. Hence, we get the following theorem.
Theorem 5. Let be lists distributed indepen-
dently according to Let be players, and let know all the
Assume that for all player can send messages to in a secure way
(where Let and for

Then, for large enough there exists a PSS for players with the transfer
path and tolerating one corrupted player if there does not exist
with



4 Broadcast and Multi-party Computation
4.1 The Case of Three Players
We will now apply the results of Section 3 and state the exact condition under
which broadcast is possible for three players.
Theorem 6. Let be triples distributed indepen-
dently according to Assume that and know the values
and respectively. Let all players pairwisely be connected by secure channels.
If is large enough and or
does not hold, then there exists a broadcast protocol for three players with sender

Proof. If either or does not hold,
it is possible to set up a PSS with either the transfer path or
It was shown in [16] that this is sufficient to construct a broad-
cast protocol for three players.

Theorem 7. Let be triples distributed indepen-
dently according to Assume that and know the values
and respectively. Let all players pairwisely be connected by secure channels.
If both and hold, then there
exists no broadcast protocol (for any for three players with sender
TEAM LinG
574 Matthias Fitzi, Stefan Wolf, and Jürg Wullschleger

Proof. From Lemma 6, it follows that there exist channels and such
that and hold, as well as and such
that and hold.
As in the proof of Theorem 3, we duplicate the sender and rearrange the
four resulting players in the following way: We disconnect and but connect
to instead, whereas stays connected as originally.
gets input constructed by applying the channel on gets
input constructed by applying the channel on gets input
and gets input
We give and two different inputs and and let them all execute
the protocol; they all output a value. We now consider three scenarios of an
original system involving some of the players and of the new
system obtained by interconnecting all four players as described above.
Let and be correct and be corrupted. Using his variables
can produce and such that cannot distinguish them from and
Furthermore, cannot distinguish which he receives from from
simulates giving him the values as input, and using the values
himself.
Let and be correct and be corrupted. Using his variables
can produce and such that cannot distinguish them from and
Furthermore, cannot distinguish which he receives from from
simulates giving him the values as input, and using the values
himself.
Let and be correct and be corrupted. Using his variables
can produce and He can simulate player with as input and
use for himself.
The joint view of the players and in the new system is indistinguishable
from their view in the first scenario, and they must thus output The joint
view of the players and in the new system is indistinguishable from their
joint view in the second scenario, and they, therefore, output But also the
joint view of players and in the new system is indistinguishable from their
view in the third scenario, and thus they must agree on their output value, which
contradicts what we derived above. Therefore, no broadcast protocol can exist.

Using Theorems 6 and 7 we can now state the exact condition under which
broadcast and MPC among three players are possible.
Theorem 8. Let be triples distributed indepen-
dently according to Let and know the values and
respectively. Let all players pairwisely be connected by secure channels. Broadcast
with sender is possible if and only if


holds.

TEAM LinG
Pseudo-signatures, Broadcast, and Multi-party Computation 575

Corollary 4. Let be triples distributed indepen-
dently according to Let and know the values and
respectively. Let all players pairwisely be connected by secure channels.
Broadcast with sender is possible if and only if


holds.
Lemma 7. Given three players and connected pairwisely by secure
channels and additionally by broadcast channels from to and from
to (but no other primitive such as a PSS among the players). Then
broadcast from to is impossible.
Proof. This follows from a generalization of the proof in [14], where only pair-
wise channels are assumed.

Theorem 9. Let be triples distributed indepen-
dently according to Let and know the values and
respectively. Let all players pairwisely be connected by secure channels.
Broadcast with arbitrary sender as well as general multi-party computation
secure against one corrupted player are possible if and only if




holds.
Proof. The condition is sufficient for the possibility of broadcast because of The-
orem 8 and Lemma 7. The achievability of multi-party computation then follows
from [1,26,10]. Furthermore, since broadcast is a special case of multi-party
computation, the impossibility of broadcast immediately implies the impossibil-
ity of MPC.

Corollary 5. Let be triples distributed indepen-
dently according to Let and know the values and
respectively. Let all players pairwisely be connected by secure channels.
Broadcast with arbitrary sender as well as general multi-party computation
secure against one corrupted player are possible if and only if




holds.
TEAM LinG
Matthias Fitzi, Stefan Wolf, and Jürg Wullschleger
576

4.2 The Case of More than Three Players
Corollary 6. Let be players. Let all players pairwisely be con-
nected by secure channels. Furthermore, let every triple of players
have enough independent realizations of and respectively, such that
either or does not
hold. Then broadcast and multi-party computation unconditionally secure against
corrupted players are achievable.
Proof. From Theorem 9, it follows that any triple of players can execute a broad-
cast protocol. Using the protocol from [17], broadcast for players tolerating
corrupted players can be achieved. Using [1,26,10], a protocol for uncon-
ditional MPC can be constructed that can tolerate corrupted players.


5 Concluding Remarks
In the model of unconditional security, we have completely characterized the
possibility of pseudo-signatures, broadcast, and secure multi-party computation
among three players having access to certain correlated pieces of information.
Interestingly, this condition is closely related to a property called (non-) simu-
latability previously studied in an entirely different context, namely information-
theoretic secret-key agreement.
As a consequence of this result, we gave a new, weaker condition for the
possibility of achieving unconditional broadcast between players and any mi-
nority of cheaters and, hence, general multi-party computation under the same
conditions.

Acknowledgment s
The first author was supported by the Packard Foundation and the second and
the third author by Canada™s NSERC.

References
1. Donald Beaver. Multiparty protocols tolerating half faulty processors. In Advances
in Cryptology: CRYPTO ™89, volume 435 of Lecture Notes in Computer Science,
pages 560“572. Springer-Verlag, 1989.
2. Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems
for non-cryptographic fault-tolerant distributed computation. In Proceedings of the
20th Annual ACM Symposium on Theory of Computing (STOC ™88), pages 1“10.
Springer-Verlag, 1988.
3. Richard E. Blahut. Principles and practice of information theory. Addison-Wesley,
Reading, MA, 1988.
4. Jurjen Bos and Bert den Boer. Detection of disrupters in the DC protocol. In Ad-
vances in Cryptology: EUROCRYPT ™89, volume 434 of Lecture Notes in Computer
Science, pages 320“327. Springer-Verlag, 1990.

TEAM LinG
Pseudo-signatures, Broadcast, and Multi-party Computation 577

5. David Chaum. The Dining Cryptographers Problem: Unconditional sender and
recipient untraceability. Journal of Cryptology, 1(1):65“75, 1988.
6. David Chaum, Claude Cr©peau, and Ivan Damgård. Multiparty unconditionally
secure protocols (extended abstract). In Proceedings of the 20th Annual ACM
Symposium on Theory of Computing (STOC ™88), pages 11“19. ACM Press, 1988.
7. David Chaum and Sandra Roijakkers. Unconditionally-secure digital signatures. In
Advances in Cryptology: CRYPTO ™90, volume 537 of Lecture Notes in Computer
Science, pages 206“214. Springer-Verlag, 1990.
8. Richard Cleve. Limits on the security of coin flips when half the processors are
faulty. In ACM Symposium on Theory of Computing (STOC ™86), pages 364“369,
ACM Press, 1986.
9. Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley-
Interscience, New York, USA, 1991.
10. Ronald Cramer, Ivan Damgård, Stefan Dziembowski, Martin Hirt, and Tal Ra-
bin. Efficient multiparty computations secure against an adaptive adversary. In
Advances in Cryptology: EUROCRYPT ™99, volume 1592 of Lecture Notes in Com-
puter Science, pages 311“326. Springer-Verlag, 1999.
11. Whitfield Diffie and Martin Hellman. New directions in cryptography. IEEE
Transactions on Information Theory, IT-22(6):644“654, 1976.
12. Danny Dolev and H. Raymond Strong. Polynomial algorithms for multiple pro-
cessor agreement. In Proceedings of the 14th Annual ACM Symposium on Theory
of Computing (STOC ™82), pages 401“407, 1982.
13. Danny Dolev and H. Raymond Strong. Authenticated algorithms for Byzantine
agreement. SIAM Journal on Computing, 12(4):656“666, 1983.
14. Michael J. Fischer, Nancy A. Lynch, and Michael Merritt. Easy impossibility
proofs for distributed consensus problems. Distributed Computing, 1:26“39, 1986.
15. Matthias Fitzi, Nicolas Gisin, and Ueli Maurer. Quantum solution to the Byzantine
agreement problem. Physical Review Letters, 87(21):7901“1“7901“4, 2001.
16. Matthias Fitzi, Nicolas Gisin, Ueli Maurer, and Oliver von Rotz. Unconditional
Byzantine agreement and multi-party computation secure against dishonest mi-
norities from scratch. In Advances in Cryptology: EUROCRYPT ™02, volume 2332
of Lecture Notes in Computer Science, pages 482“501. Springer-Verlag, 2002.
17. Matthias Fitzi and Ueli Maurer. From partial consistency to global broadcast.
In 32nd Annual Symposium on Theory of Computing, STOC ™00, pages 494“503.
ACM, 2000.
18. Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game.
In Proceedings of the 19th Annual ACM Symposium on Theory of Computing
(STOC ™87), pages 218“229. ACM Press, 1987.
19. Leslie Lamport. Constructing digital signatures from a one-way function. Technical
Report SRI-CSL-98, SRI International Computer Science Laboratory, 1979.
20. Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals
problem. ACM Transactions on Programming Languages and Systems, 4(3):382“
401, 1982.
21. Ueli Maurer. Secret key agreement by public discussion. IEEE Transaction on
Information Theory, 39(3):733“742, 1993.
22. Ueli Maurer. Information-theoretically secure secret-key agreement by NOT au-
thenticated public discussion. In Advances in Cryptology: EUROCRYPT ™97, vol-
ume 49 of Lecture Notes in Computer Science, pages 209“225. Springer-Verlag,
1997.

TEAM LinG
Matthias Fitzi, Stefan Wolf, and Jürg Wullschleger
578

23. Ueli M. Maurer and Stefan Wolf. Secret-key agreement over unauthenticated public
channels”Part I: Definitions and a completeness result. IEEE Transactions on
Information Theory, 49:822“831, 2003.
24. Ueli M. Maurer and Stefan Wolf. Secret-key agreement over unauthenticated public
channels”Part II: The simulatability condition. IEEE Transactions on Informa-
tion Theory, 49:832“838, 2003.
25. Birgit Pfitzmann and Michael Waidner. Information-theoretic pseudosignatures
and Byzantine agreement for Technical Report RZ 2882 (#90830),
IBM Research, 1996.
26. Tal Rabin and Michael Ben-Or. Verifiable secret sharing and multiparty protocols
with honest majority. In Proceedings of the 21st Annual ACM Symposium on
Theory of Computing (STOC ™89), pages 73“85, 1989.
27. Andrew C. Yao. Protocols for secure computations. In Proceedings of the 23rd
Annual IEEE Symposium on Foundations of Computer Science (FOCS ™82), pages
160“164, 1982.




TEAM LinG
Author Index


<<

. 18
( 19)



>>