received the original Y R over more that u + 1 wires during Phase I, and if yes, then

2

the corresponding LSault . For this, R does the following:

f

?

1. For each 1 ¤ j ¤ n, R checks Yj = Y R and |LRaultj | ≥ (t ’ u + 1). In any of the

R

f 2

test fails, then R neglects all the values received along fj . Otherwise, R applies

the U Rauth function to each element of LRaultj by using the same keys from K,

f

which were used by S to authenticate LSault and computes the set LfR j,auth .

f ault

?

R then checks LfR j,auth = LRaultj,auth . If the test fails then again R discards

ault f

the values received along fj .

2. If as a result of previous step, R has discarded the values along all the wires in

the top band, then R concludes that S has not received original Y R over more

that u + 1 wires during Phase I, which further implies that at most t ’ u ’ 1

2 2

wires were corrupted in the top band during Phase I. So R recovers mR by using

the polynomials received over the ¬rst t ’ u + 1 wires in P R during Phase I.

2

Moreover, by selecting next two ”unused” elements k1 , k2 from K as authenti-

cation keys, R computes response1 = U Rauth(”terminate”; k1 , k2 ) where ”ter-

minate” is an unique pre-de¬ned special element from F. R then send the tuple

(”terminate”, response1 ) to S through the bottom band and terminates.

3. If during step 1, there exists a j ∈ {1, 2, . . . , n} such that Yj = Y R , |LRaultj | ≥

R

f

(t ’ u + 1) and LfR j,auth = LRaultj,auth , then R concludes that S has cor-

ault f

2

R

rectly received original Y over more that u + 1 wires during Phase I and

2

LRaultj is the corresponding Lf ault sent by S. So R removes the wires in LRaultj

f f

from his view for further computation and communication. Note that if there

are more than one such j (whose probability is negligible), then R arbitrarily se-

lects one. Now by selecting k1 , k2 from K as authentication keys, R computes

response2 = U Rauth(”continue”; k1 , k2 ) where ”continue” is an unique pre-

de¬ned special element from F. R then send the tuple (”continue”, response2 ) to

S through the bottom band.

Computation by S at the end of Phase IV: S checks whether it is getting any

2-tuple identically over at least u + 1 wires. If not, then S concludes that R has

2

recovered mR and terminates. On the other hand, if S receives a 2-tuple say (xS , y1 )

S

1

?

over u + 1 wires, then S veri¬es y1 = U Rauth(xS ; k1 , k2 ). If the test fails, then S

S

1

2

again concludes that R has recovered mR and terminates. On the other hand, if the

?

test succeeds then S further checks xS = ”terminate”. If yes, then S again concludes

1

that R has recovered mR and terminates. If no then S concludes that Y S was indeed

sent by R.

Unconditionally Reliable and Secure Message Transmission 323

Lemma 5. If |LSault | ≥ (t ’ u + 1), then at the end of Phase III in Table 8

f 2

one of the following will happen:

1. If S has ”not” received the original Y R over more that u + 1 wires during

2

Phase I, then with very high probability R will be able to detect this. More-

over R will be able to correctly recover mR by using the polynomials received

over the wires in P R with very high probability.

2. If S has received the original Y R over more that u + 1 wires during Phase

2

I, then R will be able to detect this. Moreover, with very high probability, R

will correctly receive LSault , from which it will come to know the identity of

f

at least |LSault | corrupted wires in the top band.

f

Table 9. Execution of Π U RM T to re-send mS

|mS |

S divides mS into blocks B1 , B2 , . . . , B S , each of size

S S

. Moreover S and R ini-

u u

2 2

tializes variables wcS = 1, bcS = 1 and wcR = 1, bcR = 1 respectively. S and R now

executes the following steps:

1. While (wcS ¤ u ’ 1) and (all the blocks of mS are not sent) do

2

S

(a) S sends the block BbcS to R only over wire fwcS in the top band.

R

(b) Let R receives BbcR along wire fwcR . Now by selecting kbc from the set K as

hash key, R computes xR = hash(kbc ; BbcR ) and sends xR to S through the

R

bc bc

bottom band.

(c) S correctly receives xR through at least u + 1 wires (recall that in this case

bc 2

?

majority wires in bottom band are honest) and veri¬es xR = hash(kbc ; BbcS ).

S

bc

S

If the test fails then S concludes that wire fwcS has delivered incorrect BbcS

to R. So S increments wcS by one. Moreover, S authenticates an unique pre-

de¬ned special ”increment-wire” element from F by using two keys from the

set K and sends it to R through the top band. R correctly receives the signal

with very high probability and accordingly increments wcR by one.

On the other hand, if the test succeeds then S concludes that wire fwcS

has delivered correct BbcS to R. So S increments bcS by one. Moreover, S

S

authenticates an unique pre-de¬ned special ”increment-block” value from F

by using two keys from the set K and sends it to R through the top band.

R correctly receives the signal with very high probability and accordingly

increments bcR by one.

2. If all the blocks of mS are sent then both S and R terminates. Otherwise S

concatenates all the remaining blocks of mS and sends to R through wire f u and

2

terminates. R correctly receives these blocks and terminates.

If at the end of Phase IV in Table 8, S recovers ”continue” signal from R

then S removes the wires in LSault from his view. S now knows that in both

f

S and R™s view, there are n ’ |LSault | wires in the top band, of which at most

f

t ’ |Lf ault | could be corrupted. Since |LSault | ≥ (t ’ u + 1), in S and R™s view,

S

f 2

there are at most t ’ u wires in the top band, of which at most u ’ 1 could be

2 2

corrupted. Moreover, both S and R now knows that there exists at least u + 1 2

honest wires in the bottom band. S now proceeds to re-send mS . For this, out of

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

the t ’ u in their view, both S and R considers only the ¬rst u wires. Without

2 2