IIT Madras, Chennai India 600036

arpita@cse.iitm.ernet.in, ashishc@cse.iitm.ernet.in, rangan@iitm.ernet.in

Abstract. In this paper, we design URMT and USMT protocols which

are communication optimal in amortized sense and ¬rst of their kind.

Keywords: Error Probability, Information Theoretic Security.

1 Introduction

Consider the following problem: a sender S and a receiver R are a part of di-

rected synchronous network and are connected by uni-directional vertex disjoint

paths/channels (also called as wires), which are directed either from S to R

or vice-versa. An adversary At having unbounded computing power controls at

most t wires in Byzantine fashion. S intends to communicate a message M S

containing ≥ 1 ¬eld elements from a ¬nite ¬eld F to R. The challenge is to

design a protocol such that after interacting in phases1 as per the protocol, R

should output M R where M R = M S with probability at least 1 ’ poly(κ)2’κ

and κ is the error parameter. This problem is called unconditionally reliable mes-

sage transmission (URMT)[6,4]. The problem of unconditionally secure message

transmission (USMT)[6,4] has an additional restriction that At should get no

information about M S in information theoretic sense. If S and R are directly

connected by a private channel, as assumed in generic secure multiparty compu-

tation protocols [2,13,3,9], then reliable and secure communication between them

is guaranteed. However when S and R are not adjacent then URMT/USMT pro-

tocols help to simulate a virtual reliable/secure link with very high probability.

Existing Literature: The problem of URMT and USMT in directed networks

was ¬rst studied by Desmedt et al. [4]. Modeling the underlying network as a

directed graph is well motivated because in practice not every communication

channel admits bi-directional communication. For instance, a base-station may

communicate to even a far-o¬ hand-held device but the other way round com-

munication may not be possible. Following the approach of Dolev et al.[5], the

authors in [4] have abstracted the underlying directed network in the form of

directed vertex disjoint paths/wires, which are directed either from S to R or

Financial Support from Infosys Technology India Acknowledged.

Work Supported by Project No. CSE/05-06/076/DITX/CPAN on Protocols for Se-

cure Communication and Computation Sponsored by Department of Information

Technology, Government of India.

1

A phase is a send from S to R or vice-versa.

R. Ostrovsky, R. De Prisco, and I. Visconti (Eds.): SCN 2008, LNCS 5229, pp. 309“326, 2008.

c Springer-Verlag Berlin Heidelberg 2008

310 A. Patra, A. Choudhary, and C.P. Rangan

vice-versa. Under such settings, Desmedt et al. have shown that URMT/USMT

tolerating At is possible i¬ there are total 2t + 1 wires between S and R, of

which at least t + 1 should be directed from S to R [4]. Recently, Shankar et

al. [10] have studied URMT in arbitrary directed networks, where they have

given the complete characterization of URMT tolerating At by considering the

underling directed network as a whole. Their characterization shows that it is

inappropriate to model an underlying directed network in the form of directed

wires between S and R. However, it is likely to take exponential time to verify

whether a given directed network and At satis¬es the conditions given in [10]

for the possibility of URMT. Moreover, as a part of their su¬ciency condition,

the authors in [10] have given an exponential time URMT protocol. These two

shortcomings motivate us to relook at the wire based of Desmedt et al..

Network Model and De¬nitions: We follow the model of Desmedt et al. [4]

and abstract the network in the form of a directed graph G = (V, E), where

S and R are two special honest nodes in V . We assume that there are n di-

rected wires f1 , f2 , . . . , fn from S to R, called as top band and u directed wires

b1 , b2 , . . . , bu from R to S, called as bottom band. Moreover, we assume that the

wires in the top band are disjoint from the wires in the bottom band. Our results

can be easily generalized for the case when these wires are not disjoint. A central-

ized adversary At with unbounded computing power actively controls at most t

wires between S and R, including the top and bottom band in a colluded fashion.

The adversary is adaptive and its choice of corrupting a wire depends upon the

data seen so far. A wire once under the control of At , will remain so for the rest

of the protocol. A wire under the control of At may behave arbitrarily and the

communication over such wires is fully known and dictated by At . We say that

a wire is corrupted, if the value(s) sent over the wire is changed arbitrarily by

At . A wire which is not under the control of At is called honest. We assume that

n = max(t + 1, 2t ’ u + 1) and n + u = 2t + 1, which is the minimum number of

wires needed for the existence of URMT/USMT tolerating At [4]. The network

is synchronous and a protocol is executed in phases. Our protocols provide un-

conditional security; i.e., information theoretic security with an error probability

of at most poly(κ)2’κ in reliability, where κ is the error parameter. For this, all

our computations are performed over a ¬nite ¬eld F with |F| = GF(poly(κ)2κ ).

So each element is represented by O(κ) bits. MS denotes the message, which is

a sequence of ≥ 1 elements from F, that S intends to send to R.

Our Contributions: One of the key parameters of any URMT/USMT protocol

is its communication complexity. Though the USMT protocol of [4] is e¬cient,

it is not optimal in terms of communication complexity. In this paper, we prove

the lower bound on the communication complexity of multiphase URMT/USMT

protocols2 . Moreover, we show that our bounds are tight by giving e¬cient, poly-

2

Any single phase URMT/USMT protocol in directed network is no di¬erent from

a single phase URMT(USMT) protocol in undirected networks. So the connectiv-

ity requirement and lower bound on the communication complexity of single phase

URMT and USMT in undirected networks [8] holds for directed networks also.

Unconditionally Reliable and Secure Message Transmission 311

nomial time communication optimal URMT/USMT protocols which are ¬rst of

their kind. Speci¬cally, we show that (a) There exists an O(u) phase URMT pro-

tocol, which reliably sends κ bits by communicating O( κ) bits for su¬ciently

large . (b) If at least one wire in the bottom band is un-corrupted, then there

exists an O(u) phase USMT protocol which securely sends κ bits by commu-

nicating O( κ) bits for su¬ciently large . Thus in (a) and (b), we can achieve

reliability and security respectively, with constant factor overhead in commu-

nication complexity in amortized sense. It is easy to see that the protocols in

(a) and (b) are communication optimal. (c) If full bottom band is corrupted by

At , then any multiphase USMT protocol needs to communicate © n κ bits to

u

securely sends ( κ) bits. Moreover, we show that the bound is tight.

Tools Used: 1. Unconditionally Reliable Authentication [9,4]: It is used

to send a message M over a wire such that if the wire is uncorrupted, then R

correctly gets M and if the wire is corrupted, then R does not get M but is able

to detect the corruption with very high probability. This is done as follows: Let

a non-zero (a, b) ∈R F2 is securely established between S and R in advance. S

computes x = U Rauth(M ; a, b) = aM + b and sends (M, x) to R over the wire.

?

Let R receives (M , x ) along the wire. R veri¬es x = U Rauth(M ; a, b). If the

test fails then R concludes that M = M , otherwise M = M . The tuple (a, b)

is called authentication key. The probability that M = M , but still R fails to

1

detect it is at most |F| , which is negligible in our context.

2. Unconditionally Secure Authentication [4]: Its goal is similar to

U Rauth, except that M should be secure. This is done as follows: Let (a, b, c) ∈R

F3 ’{(0, 0, 0)}, which is securely established between S and R in advance. S com-

putes (x, y) = U Sauth(M ; a, b, c) = (M + a, b(M + a) + c) and sends (x, y) to R

?

over the wire. Let R receives (x , y ) along the wire. R veri¬es y = bx + c. If the

test fails then R concludes that wire is corrupted, else R recovers x ’ a. It is

easy to see that M is information theoretic secure. Moreover, if (x , y ) = (x, y),

then R will detect it with probability ≥ (1 ’ |F| ).

1

3. Unconditional Hashing [1]: Let (v1 , v2 , . . . , v ) ∈ F and k ∈ F ’ {0}. Then

we de¬ne hash(k; v1 , v2 , . . . , v ) = v1 + v2 k + v3 k 2 + . . . + v k ’1 . Here k is called

the hash key. The probability that two di¬erent vectors map to the same hash

value for an uniformly chosen hash key is at most |F| . If At knows only k and

hash(k; v1 , v2 , . . . , v ), then ¬rst ’ 1 elements in the vector will be secure.

4. Extracting Randomness [11]: Suppose S and R by some means agree on

x = [x1 x2 . . . xn ] ∈ Fn such that At knows n ’ f components of x, but

has no information about the other f components of x. However S and R do

not know which values are known to At . The goal of S and R is to agree on

[y1 y2 . . . yf ] ∈ Ff , such that At has no information about [y1 y2 . . . yf ]. This

is done as follows:

Algorithm EXTRANDn,f (x): Let V be a publicly known n — f Vandermonde ma-

trix with members in F. S and R locally computes [y1 y2 . . . yf ] = [x1 x2 . . . xn ]V .

312 A. Patra, A. Choudhary, and C.P. Rangan

2 Three Phase USMT Protocol of Desmedt et al. [4,12]

We brie¬‚y recall the three phase USMT protocol of [4] to send a message mS ∈ F.

We call the protocol as Π Existing . We recall the protocol to highlight few tech-

niques which are also used in our URMT and USMT protocols. In the protocol,

there are two cases: (a) There exists t + 1 non-faulty wires in the top band; (b)

There exists less than t + 1 non-faulty wires in the top band. During Phase I, S