wire in the top band. In order to authenticate the share associated with a wire,

S selects n pair of random authentication keys. S then sends to R the share

associated with a wire, authenticated with all the n keys. Parallely, S sends the

authentication keys to R, one over each wire. In addition, S associates a random

three tuple with each wire and sends it to R. If there are t + 1 non-faulty wires

in the top band, then at the end of Phase I, R will get at least t + 1 correct

shares with which he can recover mR .

If R cannot recover mR at the end of Phase I, then it implies that there

is at least one honest wire in the bottom band. So using the bottom band,

S and R tries to correctly and securely agree on a shared authentication key

and encryption key to securely communicate mS . For this, R uses the 3-tuples

(aR , bR , cR ) received from S. Now R sends a random non-zero 2-tuple (dR , eR ) to

i i i i i

S on each wire in bottom band. In addition, each such 2-tuple is authenticated

by u random non-zero keys. Now according to the values received from R, S

divides the bottom band into sub-sets B1 , B2 , . . . , Bk , where k ¤ u, such that for

each 1 ¤ l ¤ k, all the wires in Bl behave in a ”consistent” way. In particular,

there exists at least one path set Bl that behave honestly during Phase II.

Though S cannot determine which path set was honest, S will try to use each

of them in a separate way and let R to determine which path set is honest. In

Phase II, . . . denotes a function used in [4], which maps a variable size (the

variable size is bounded by a pre-de¬ned bound) ordered subset of F to an image

element in a ¬eld extension F— . The Phase II is as follows:

Table 1. Phase I of USMT Protocol Π Existing [4]

1. S selects a random polynomial p(x) of degree t over F such that p(0) = mS and

computes the secret shares (sS , sS , . . . , sS ), where sS = p(i), 1 ¤ i ¤ n. In order to

1 2 n i

authenticate each sS , S selects n random non-zero authentication keys (aS , bS ) ∈ F2 ,

i i,j i,j

1 ¤ j ¤ n. In addition, corresponding to each wire fi in top band, S selects a random

non-zero three tuple (aS , bS , cS ) ∈ F3 .

i i i

2. S sends {sS , dS , dS , . . . , dS } and the three tuple (aS , bS , cS ) to R through wire fi

i i,1 i,2 i,n i i i

S S S

where di,j = U Rauth(si ; ai,j , bi,j ), 1 ¤ j ¤ n. In addition, S sends the authentication

key (aS , bS ) to R through wire fj , for 1 ¤ j ¤ n.

i,j i,j

Computation by R at the end of Phase I:

1. Let R receives {sR , dR , dR , . . . , dR } and (aR , bR , cR ) along wire fi and keys

i i,1 i,2 i,n i i i

(aR , bR ) along wire fj . R computes Supporti = |{j : dR = U Rauth(sR ; aR , bR )}|.

i,j i,j i,j i i,j i,j

If Supporti ≥ t + 1, then R concludes that sR is a valid share. Otherwise, it is an

i

invalid share. If R receives t + 1 valid shares then R recovers the secret mR from these

valid shares and terminates. Otherwise, R proceeds to execute Phase II.

Unconditionally Reliable and Secure Message Transmission 313

1. For 1 ¤ i ¤ n, R chooses a random non-zero ri ∈ F and computes β R =

R

{(r1 , γ1 ), (r2 , γ2 ), . . . , (rn , γn )}, where γj = hash(rj ; aR , bR , cR ), 1 ¤ j ¤ n. For

R R R R R R R R

j j j

each 1 ¤ i ¤ u, R selects a random non-zero 2-tuple (dR , eR ) ∈ F2 . In order to au-

i i

thenticate (dR , eR ), R selects u random non-zero keys {(vi,j , wi,j ) ∈ F2 : 1 ¤ j ¤ u}.

R R

i i

2. For each 1 ¤ i ¤ u, R sends β R , (dR , eR ) and {±R : 1 ¤ j ¤ n}, where

i i i,j

±R = U Rauth( dR , eR ; vi,j , wi,j ) : 1 ¤ j ¤ u} to S via wire bi and the keys

R R

i,j i i

R R

(vi,j , wi,j ) to S via wire bj for each 1 ¤ j ¤ u.

Computation by S at the end of Phase II: 1. Let S receives βi , (dS , eS ) and

S

i i

S S S

{±i,j : 1 ¤ j ¤ u} from R via wire bi and (vi,j , wi,j ) from R via wire bj for each

1 ¤ j ¤ u. S divides the bottom band {b1 , b2 , . . . , bu } into subsets B1 , B2 , . . . , Bk ,

where k ¤ u, such that for any l, m, p with 1 ¤ l ¤ k, 1 ¤ m, p ¤ u and

bm , bp ∈ Bl , we have: (a) βm = βp ; (b) ±S = U Rauth( dS , eS ; vm,p , wm,p ); (c)

S S S S

m,p mm

±S = U Rauth( dS , eS ; vp,m , wp,m ).

S S

p,m p p

S S S

2. For Bl , let bm ∈ Bl and βm = {(ri,l , γi,l ) : 1 ¤ i ¤ n}. S computes the set

Fl = {i : γi,l = hash(ri,l ; aS , bS , cS ), 1 ¤ i ¤ n}

S S

i i i

If |Bl | + |Fl | ¤ t then S decides that Bl is unacceptable set, otherwise Bl is acceptable.

From the properties of U Rauth and hash, it is easy to check that the following

holds: (a) If bi is an honest wire in the bottom band and bi ∈ Bl , then with very

high probability, the random 2-tuples that S has received along the wires in Bl

are not modi¬ed; (b) If bi is an honest wire in the bottom band and bi ∈ Bl ,

then Bl is an acceptable set. However, all acceptable sets may look same to S

and S may not determine whether an acceptable set contains all honest wires.

In the worst case, At can control the bottom band in such a way that there are

u Bl ™s, with one wire from the bottom band in each Bl .

Table 2. Phase III and Secret Recovery in Protocol Π Existing

Phase III: S to R: For each acceptable set Bl and the corresponding set Fl , S does

È

the following:

È È È

“ From the wires in Fl and Bl , S computes his version of the keys Cl = fi ∈Fl aS +

S

i

S S S S S S

bi ∈Bl di and Dl = fi ∈Fl bi + bi ∈Bl ei . S then sends (ψl , »l ) to R over all

the wires in Fl , where ψl = Bl , Fl , mS + Cl and »S = U Rauth(ψl ; Cl , Dl ).

S S S S S

l

Message Recovery by R: R knows that in the worst case, S could have sent u

2-tuples over each wire in the top band, corresponding to the case when there are u

acceptable sets. Let R receives (ψi,l , »R ) over wire fi for 1 ¤ i ¤ n and 1 ¤ l ¤ u.

R

i,l

È È

R R R R

1. For each 1 ¤ i ¤ n, R computes Bi,l , Fi,l , „i,l = ψi,l (that is, R decomposes

È È

ψi,l ). R then computes his version of the keys Ci,l = fj ∈Fi,l aR + bj ∈Bi,l dR

R R

j j

R

bR + eR .

and Di,l = j j

fj ∈Fi,l bj ∈Bi,l

?

2. For 1 ¤ i ¤ n, R checks whether »R = U Rauth(ψi,l ; Ci,l , Di,l ). If the equation

R R R

i,l

holds then R computes the secret mR = „i,l ’ Ci,l and terminates.

R R

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

S continues the protocol by assuming that each acceptable set is correct. In

other words, assuming that all the wires in an acceptable set Bl are non-faulty,

S determines which of the random 3-tuples (aS , bS , cS ), have been correctly re-