ceived by R. Using these ”correctly-received-by-R” 3-tuples and the random

2-tuples received by S via the wires in Bl , S computes the authentication key

and encryption key to securely send the messages to R. If the assumption that

Bl contains only non-faulty wires is valid, then R would be able to compute

the same authentication and encryption key. Since at least one of the acceptable

path set is non-faulty, R will be able to decrypt the secret message correctly.

The Phase III is shown in Table 2. It is easy to check that with very high prob-

ability, mR = mS . Since, for an acceptable set Bl , |Fl | + |Bl | > t, the adversary

learns no information about ClS or Dl and hence about mS .

S

Modi¬ed Version of Desmedt™s USMT Protocol: We now present a mod-

Existing

i¬ed version of protocol Π Existing , called Πmodif ied , where all the computation

Existing

and communication is done in F. The purpose of presenting Πmodif ied is to

introduce certain new techniques, which we have also used in our later proto-

Existing

cols. Protocol Πmodif ied will be used as a sub-protocol in our communication

optimal URMT and USMT protocols. The protocol securely sends a message

mS = {mS mS . . . mS } containing n = ˜(n) elements from F by communi-

n

1 2 3

3

cating O(n ) elements from F. During Phase I, S selects a random polynomial

3

M S (x) over F of degree n ’ 1 + t such that the lower order n coe¬cients of

3

M S (x) are elements of mS . S then computes M S (1), M S (2), . . . , M S (n + t). S

S S S

selects n + t random polynomials f1 (x), f2 (x), . . . , fn+t (x) over F, each of de-

gree t, such that fiS (0) = M S (i), 1 ¤ i ¤ n + t. S then evaluates each fiS (x)

at x = 1, 2, . . . , n to form an n tuple fiS = [fiS (1) fiS (2) . . . fiS (n)]. S now

constructs an (n) — (n + t) matrix T where ith column of T contains the n tuple

fiS , 1 ¤ i ¤ n + t. Let FjS = [f1 (j) f2 (j) . . . fn+t (j)] denotes the j th , 1 ¤ j ¤ n

S S S

row of T . Now Phase I is as follows:

Phase I: S to R: Along wire fj , 1 ¤ j ¤ n, S sends the following to R: (a) The vector

FjS , a random non-zero hash key ±S and the n tuple [v1j v2j . . . vnj ], where vij =

S S S S

j

hash(±S ; FiS ), 1 ¤ i ¤ n; (b) A random non-zero (n + 1) tuple (xS , xS , . . . , xS

n+1,j ),

j 1,j 2,j

S

which is independent of Fj .

Computation by R at the end of Phase I: Let R receives the vector FjR , hash

key ±R , the n tuple [v1j v2j . . . vnj ] and the n + 1 tuple (xR , xR , . . . , xR

RR R

n+1,j ) along

j 1,j 2,j

wire fj , 1 ¤ j ¤ n.

1. For 1 ¤ j ¤ n, R computes Supportj = |{fi : vji = hash(±R ; FjR )}|. If Supportj ≥

R

i

t + 1, then R concludes that FjR is a valid row of T . Otherwise, R concludes that FjR

is an invalid row of T .

2. If R has received t + 1 valid rows, then R reconstructs the secret mR from them

and terminates protocol (see Theorem 1). Otherwise, R proceeds to execute Phase

II.

Lemma 1. If FjR is a valid row, then with overwhelming probability FjR = FjS .

Lemma 2. During Phase I, at least n coe¬cients of M S (x) are information

theoretically secure.

Unconditionally Reliable and Secure Message Transmission 315

Theorem 1. If R gets t + 1 valid rows then R can securely recover mS with

very high probability.

For complete proof of Lemma 1, Lemma 2 and Theorem 1, please see the full

2

version of the paper [7].

If R does not get t + 1 valid rows, then R concludes that at least one wire in

the bottom band is honest. So R proceeds to execute Phase II as shown in

Table 3. Phase II is similar to the Phase II of protocol Π Existing , except that

β R contains the hashed value of each n + 1 tuple received from S. Moreover,

along each wire in the bottom band, R now sends an (n + u) tuple and hash it

with u random keys. Now as in protocol Π Existing , depending upon the values

received along the wires in the bottom band, S divides the bottom band into

di¬erent subsets. As in the previous protocol, it is straightforward 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 (n + u)-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.

Existing

Table 3. Phase II and computation by S at the end of Phase II in Πmodif ied

Phase II: R to S (if R has not recovered the secret at the end of Phase I)

R

1. For each 1 ¤ j ¤ n, R chooses a random non-zero hash key rj ∈ F and computes

the set β R = {(rj , γj ) : 1 ¤ j ¤ n}, where γj = hash(rj ; xR , xR , . . . , xR

R R R R

n+1,j ).

1,j 2,j

2. For each 1 ¤ j ¤ u, R selects a random non-zero n + u tuple

(y1,j , y2,j , . . . , yn+u,j ) ∈ Fn+u . In order to hash each such n tuple, R selects u

R R R

R

random non-zero keys {keyi,j : 1 ¤ i ¤ u} from F.

3. For each 1 ¤ j ¤ u, R sends β R and the n + u-tuple (y1,j , y2,j , . . . , yn+u,j ) to

R R R

S over wire bj and the 2-tuple (keyi,j , ±R ) to S over wire bi , 1 ¤ i ¤ u, where

R

i,j

±R = hash(keyi,j ; y1,j , y2,j , . . . , yn+u,j ).

R R R R

i,j

S

Computation by S at the end of Phase II: For 1 ¤ j ¤ u, S receives βj and

the n + u-tuple (y1,j , y2,j , . . . , yn+u,j ) over wire bj and the pair (keyi,j , ±S ) over

S S S S

i,j

bi , 1 ¤ i ¤ u. S then does the following:

1. 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 = hash(keym,p ; y1,p , y2,p , . . . , yn,p ); (c) ±S =

S S S S S S

m,p p,m

S S S S

hash(keyp,m ; y1,m , y2,m , . . . , yp,m ).

S S S

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

FlS = {j : γj,l = hash(rj,l ; xS , xS , . . . , xS

S S

n+1,j ), 1 ¤ j ¤ n}

1,j 2,j

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

Before proceeding further, we make the following important claim.

Claim. Let fi and bj be two honest wire in top and bottom band respectively.

Then at the end of Phase II, at least n elements in (xS , xS , . . . , xS n+1,i ) and

1,i 2,i

R R R

(y1,j , y2,j , . . . , yn+u,j ) are information theoretically secure.

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

The Phase III of the protocol is as follows:

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

following:

1. S considers the ¬rst n elements from the n + 1 tuples which it had sent over

the wires in Fl during Phase I and the ¬rst n elements from the (n + u) tuples