which S had received over the wires in Bl during Phase II. By using them, S

È È È È

computes his version of n authentication keys C1,l = fj ∈Fl xS + bj ∈Bl y1,j ,

S S

1,j

S

xS + S S

xS + S

C2,l = y2,j , . . ., Cn,l = yn,j .

2,j n,j

fj ∈Fl bj ∈Bl fj ∈Fl bj ∈Bl

2. For each element of m (recall that |mS | = n ), S takes three elements from the

S

3

keys computed in the previous step and computes the set SlS = {(cS , dS ) : 1 ¤

i,l i,l

i ¤ n } where (cS , dS ) = U Sauth(mS ; C3i’2 , C3i’1 , C3i ), 1 ¤ i ¤ n .

S S S

i

i,l i,l

3 3

3. S sends the set Fl , Bl and SlS to R over all the wires in the set Fl and terminates.

R R R

Message Recovery by R: Let R receives the sets Fj,l , Bj,l and Sj,l along wire

fj , 1 ¤ j ¤ n, for 1 ¤ l ¤ u. R then does the following:

R R

1. If for some j ∈ {1, 2, . . . , n} and some l ∈ {1, 2, . . . , u}, |Fj,l | + |Bj,l | ¤ t, then R

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

R R R

2. If fj is not neglected, then for each Fj,l , Bj,l and Sj,l received along fj , R

does the following: let Sj,l = {(cR , dR ) : 1 ¤ i ¤ n }. By using the in-

R

j,i,l j,i,l 3

R R

dex of the wires in Fj,l and Bj,l , R computes his version of authentication keys

R R R

Cj,1,l , Cj,2,l , . . . , Cj,n,l . Then for each 1 ¤ i ¤ n , R applies the veri¬cation process

3

of U Sauth on cR , dR , C3i’2 , C3i’1 and C3i . If the veri¬cation is successful for

R R R

j,i,l j,i,l

all 1 ¤ i ¤ n , then R recovers mR from cR , 1 ¤ j ¤ n . Finally, R concatenates

i j,i,l

3 3

mR , mR , . . . , mR to reconstruct the secret mR and terminates.

1 2 n

3

existing

Theorem 2. Protocol Πmodif ied is a three phase USMT protocol which securely

sends ˜(nκ) bits by communicating O(n3 κ) bits with very high probability.

Proof: For complete proof, see [7]. 2

3 Unconditionally Secure Pad Establishment Protocol

We now propose a six phase protocol called Π P ad , which securely establishes

a random non-zero one time pad between S and R with very high probability

by communicating O(n3 ) ¬eld elements. If the entire bottom band is corrupted,

then the size of the pad is ˜(n2 u). Otherwise the size of the pad is ˜(n3 ). We

¬rst design a sub-protocol Π which is used in Π P ad .

Protocol Π: Suppose S and R in advance know that full bottom band is cor-

rupted. This implies that at most t ’ u and at least t + 1 wires in the top band

are corrupted and honest respectively. Under this assumption, we design a sub-

protocol Π, which securely establishes an information theoretic secure non-zero

random one time pad of size ˜(n2 u) between S and R by communicating O(n3 )

¬eld elements, with very high probability.

Unconditionally Reliable and Secure Message Transmission 317

Let c = n2 +t’u. S selects (t+1)—c random non-zero elements from F, denoted

S S S S S S S S S

by k1,1 , k1,2 , . . . , k1,c , k2,1 , k2,2 , . . . , k2,c , . . . , kt+1,1 , kt+1,2 , . . . , kt+1,c . Now using

these elements, S constructs an (t+1)—c matrix AS , where the j th , 1 ¤ j ¤ t+1

row of AS is [kj,1 kj,2 . . . kj,i . . . kj,c ]. Now consider the ith , 1 ¤ i ¤ c column

S S S S

S S S

of A containing the elements [k1,i k2,i . . . kt+1,i ]T . S forms a t degree polynomial

S S S

qi (x) passing through the t + 1 points [(1, k1,i ), (2, k2,i ), . . . , (t + 1, kt+1,i )] and

S S S

evaluates qi (x) at x = t + 2, t + 3, . . . , n to get yt+2,i , yt+3,i , . . . , yn,i respectively.

Finally, S constructs the matrix B S of size n — c, where the ith , 1 ¤ i ¤ c column

of B S is [k1,i k2,i . . . kt+1,i yt+2,i yt+3,i . . . yn,i ]T , the n points on qi (x).

S S S S S S

Now using the j th , 1 ¤ j ¤ n row of B S , S forms a n2 + t ’ u ’ 1 degree

polynomial FjS (x) = kj,1 + kj,2 x1 + kj,3 x2 + . . . + kj,c xc’1 . S also selects n

S S S S

random and non-zero distinct elements from F, denoted by ±S , ±S , . . . , ±S . Now n

1 2

the protocol Π is formally expressed in Table 4.

Table 4. Protocol Π

Computation and Communication by S: Along wire fj , 1 ¤ j ¤ n, S sends to

R the polynomial FjS (x), the random value ±S and n tuple [v1j v2j . . . vnj ] where

S S S

j

S S S S

vij = Fi (±j ), 1 ¤ i ¤ n. Let V denotes the concatenation of the elements in the

¬rst t + 1 rows of B S . S computes P S = EXTRAND|V S |,(u+1)n2 (V S ). The vector

P S denotes the information theoretically secure random pad of size ˜(n2 u) which

will be correctly established with R with very high probability.

Computation by R:

1. Let R receives FjR (x), the random value ±R and the n tuple [v1j v2j . . . vnj ]

R R R

j

along wire fj , 1 ¤ j ¤ n.

2. For 1 ¤ j ¤ n, R computes Supportj = |{i : FjR (±R ) = vji }|. If Supportj ≥ t + 1,

R

i

then R concludes that FjR (x) is a valid polynomial. Otherwise, R concludes that

FjR (x) is an invalid polynomial.

3. Since there are at least t + 1 honest wires in the top band, R will get at least t + 1

valid polynomials. Now using t + 1 valid polynomials, R will construct array B R .

From B R , R computes V R , from which it ¬nally computes P R and terminates.

With very high probability, P R = P S (see Lemma 3).

Theorem 3. If full bottom band is corrupted, then protocol Π securely estab-

lishes a random non-zero pad of ˜(n2 uκ) bits by communicating O(n3 κ) bits.

Proof: For complete proof see [7]. 2

Six Phase Protocol Π P ad : We now present the protocol Π P ad which uses

Existing

protocols Π and Πmodif ied as black-box. The ¬rst two phases of the protocol are

given in Table 5. Before proceeding further, we make the following claim.

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

R R

Then at the end of Phase II, at least n2 elements in the tuple (y1,j , y2,j , . . . ,

yn2 +1,j ) and (xS , xS , . . . , xS2 +t,i ) are information theoretically secure.

R

1,i 2,i n

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

existing

As in protocol Πmodif ied , from the properties of hash function, it is straightfor-

ward to check that the following holds: (a) If fi is an honest wire in the top band

and fi ∈ Fl , then with very high probability, the random (n2 + t)-tuples that R

has received along the wires in Fl are not modi¬ed; (b) If fi is an honest wire

in the top band and fi ∈ Fl , then Fl is an acceptable set.

Table 5. First two phases of Protocol Π P ad