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