Phase I: R to S: Corresponding to each wire bj , 1 ¤ j ¤ u in the bottom band, R

selects a random non-zero n2 + 1 tuple (y1,j , y2,j , . . . , yn2 +1,j ) and sends it to S.

R R R

Phase II: S to R:

S S S

1. Let S receives (y1,j , y2,j , . . . , yn2 +1,j ) along wire bj . Corresponding to each wire

bj , 1 ¤ j ¤ u, S selects a random non-zero hash key rj from F and computes the

set β S = {(rj , γi ) : 1 ¤ j ¤ u}, where γj = hash(rj ; y1,j , y2,j , . . . , yn2 +1,j ).

S S S S S S S

2. S associates a random non-zero n2 + t tuple (xS , xS , . . . , xS2 +t,j ) with wire

1,j 2,j n

fj , 1 ¤ j ¤ n in the top band. Moreover, in order to hash the tuple, S selects n

S

random non-zero keys from F denotes by keyi,j , for 1 ¤ i ¤ n.

3. For each 1 ¤ j ¤ n, S sends the set β S and the (n2 +t) tuple (xS , xS , . . . , xS2 +t,j

1,j 2,j n

S S

to R along wire fj and the 2-tuple (keyi,j , ±i,j ) to R along wire fi , 1 ¤ i ¤ n,

where ±S = hash(keyi,j ; xS , xS , . . . , xS2 +t,j ).

S

i,j 1,j 2,j n

Computation by R at the end of Phase II:

1. For each 1 ¤ j ¤ n, R receives the set βj and the (n2 + t) tuple

R

(xR , xR , . . . , xR2 +t,j ) along wire fj and the 2-tuple (keyi,j , ±R ) along wire

R

1,j 2,j i,j

n

fi , 1 ¤ i ¤ n.

2. R divides the top band {f1 , f2 , . . . , fn } into subsets F1 , F2 , . . . , Fk , where k ¤

t + 1, such that for any l, m, p with 1 ¤ l ¤ k, 1 ¤ m, p ¤ n and fm , fp ∈ Fl , we

have: (a) βm = βp ; (b) ±R = hash(keym,p ; xR , xR , . . . , xR2 +t,p ); (c) ±R =

R R R

m,p 1,p 2,p p,m

n

hash(keyp,m ; xR , xR , . . . , xR2 +t,m ).

R

1,m 2,m n

R R R

3. For Fl , let fm ∈ Fl and βm = {(rj,l , γj,l ) : 1 ¤ j ¤ u}. R computes the set

R R R R S

Bl = {j : γj,l = hash(rj,l ; y1,j , y2,j , . . . , yn2 +1,j ), 1 ¤ j ¤ u}

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

In the worst case, in R™s view, there can be at most t + 1 acceptable sets

because the adversary can control at most t wires in the top band. So there can

be t acceptable sets, corresponding to t corrupted wires and one acceptable set

corresponding to all the honest wires in the top band. The remaining phases of

the protocol is shown in Table 6.

Theorem 4. If the entire bottom band is corrupted then Π P ad securely estab-

lishes a random non-zero pad of size ˜(n2 κ) bits between S and R with very

high probability. Otherwise, it establishes a random non-zero pad of size ˜(n3 κ)

bits between S and R with very high probability. In either case, the protocol

terminates in six phases and communicates O(n3 κ) bits.

Unconditionally Reliable and Secure Message Transmission 319

Table 6. Remaining phases in Protocol Π P ad

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

following:

1. R concatenates the ¬rst n2 elements from (n2 + 1) and (n2 + t) tuples, which it

had sent and received over the wires in Bl and Fl respectively. Let VlR denotes

the resultant vector.

2. Corresponding to vector VlR , R selects a random non-zero hash key Kl from F.

R

R then computes the 2-tuple (Kl , γl = hash(Kl ; VlR )). R then sends Bl , Fl and

R R R

R R

the 2-tuple (Kl , γl ) to S through all the wires in Bl .

Computation by S at the end of Phase III: Now using the hash value(s) re-

ceived from R, S tries to ¬nd whether there exists at least one uncorrupted wire

in the bottom band. For this, S does the following:

S S S S

1. Let S receives index set Fj,l and Bj,l and 2-tuple (Kj,l , γj,l ) along wire bj , 1 ¤ j ¤

S S

u for 1 ¤ l ¤ t + 1. If for some j ¤ u and some l ¤ t + 1, |Fj,l | + |Bj,l | ¤ t, then S

concludes that wire bj is corrupted and neglects all the values received along bj .

S S S S

2. If Fj,l , Bj,l and the tuple (Kj,l , γj,l ) is not neglected in the previous step (i.e.,

S S

bj is not discarded), then after knowing the index of the wires in Fj,l and Bj,l ,

S S

S computes his version of the vector Vj,l . Here Vj,l denotes the concatenation of

¬rst n2 values from the (n2 + 1) and (n2 + t) tuples, which S had received and sent

S?

S S S S

over the wires in Bj,l and Fj,l respectively. S now checks γj,l = hash(Kj,l ; Vj,l ).

3. If the test in the last step succeeds for some l ¤ t + 1 and j ¤ u, then S concludes

S S

that the tuples that are exchanged along the wires in Bj,l and Fj,l are correctly

S

established between S and R. S now applies EXTRAND to Vj,l to generate

a vector P1 of size tn2 . Finally S terminates the protocol by sending a special

S

prede¬ned ”success” value from F, along with the index of the wires in the set

existing

S S

Bj,l and Fj,l to R by executing the protocol Πmodif ied . R securely (and hence

correctly) receives these indexes with very high probability and computes his

existing

R

version of P1 and terminates. Since Πmodif ied takes three phases, the protocol

will terminate at the end of Phase VI.

4. If the test in step 3 fails for all l and j, then S concludes that entire bottom

band is corrupted. In this case, S sends a special ”failure” value from F to R

existing

by executing the three phase Πmodif ied protocol. Parallely, S establishes a secure

pad P2 of size ˜(n2 u) with R by executing single phase Protocol Π. At the end

S

existing

of Πmodif ied , R will know that the entire bottom band is corrupted. Parallely

R

at the end of Π, R will output P2 , with which very high probability is same as

existing

S

P2 . Since Πmodif ied takes three phases, the protocol will terminate at the end of

Phase VI.

4 URMT with Constant Factor Overhead

Let u ¤ t and n = max(2t ’ u + 1, t + 1). Then we present an URMT protocol

called Π URMT which sends a message mS containing ¬eld elements by commu-

nicating O( ) ¬eld elements with very high probability, where = (t’ u +1)n2 =

2

˜(n3 ). The total communication complexity of the protocol is O(n3 ) ¬eld ele-

ments and the protocol terminates in O(u) phases. The principle behind the

protocol is to create a win-win situation as follows: if the adversary corrupts at

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

most t ’ u wires in the top band, then R recovers the message from the infor-

2

mation which it receives from the honest wires in the top band. On the other

hand, if more than t ’ u wires are corrupted in the top band, then majority

2

wires in the bottom band will be honest and so both S and R comes to know

about the identity of corrupted wires in the top band by using the honest wires

in the bottom band. Now using this information, S can re-send mS so that R

can recover it correctly.