non-zero elements from F with each other in advance with very high probability

existing

by executing the three phase protocol Πmodif ied . Let the set of these elements be

denoted by K. The elements in K will be used by S and R as authentication and

hash keys to reliably exchange the outcome of certain steps during the execution

of the protocol Π URMT . Note that elements in K need not be distinct, but

they are randomly selected from F. We assume that initially all the elements

in K are marked as ”unused”. Each time S (R) needs a key(s) for hashing or

authentication, then the ¬rst ”unused” element(s) from K is/are selected as

key(s). In order to do the veri¬cation, R (S) also uses the same element(s) from

K as keys. Once the veri¬cation is done, the element(s) is/are marked as ”used”

Thus we can view K as a global set, which is parallely used by both S and R.

Let mS = [mS mS . . . mS 2 mS mS . . . mS 2 . . . mS u +1,1 mS u +1,2

1,1 1,2 2,1 2,2 t’ 2 t’ 2

1,n 2,n

. . . mt’ u +1,n2 ] be the message. S constructs array B of size n — n from mS in

S S 2

2

same way as in protocol Π with following modi¬cations: S ¬rst constructs the

array AS of size (t ’ u + 1) — n2 from mS , where the j th , 1 ¤ j ¤ (t ’ u + 1)

2 2

row of AS is [mS mS . . . mS 2 ]. By considering the elements in individual

j,1 j,2 j,n

columns as distinct points, S interpolates the unique (t ’ u ) degree polynomial

2

passing through them. S then further evaluates the interpolated polynomials at

additional (t ’ u ) values of x and gets the array B S . Now by considering the

2

elements along j th , 1 ¤ j ¤ n row of B S as coe¬cients, S constructs FjS (x) of

degree n2 ’ 1. First two phases of Π URMT are as follows:

Phase I: S to R: Along wire fj , 1 ¤ j ¤ n, S sends to R the polynomial FjS (x), a

random non-zero value ±S and n tuple [v1j v2j . . . vnj ] where vij = FiS (±S ), 1 ¤ i ¤ n.

S S S S

j j

Phase II: R to S

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

RR R

j

fj , 1 ¤ j ¤ n.

2. For 1 ¤ j ¤ n, R computes Supportj = |{i : FjR (±R ) = vji }|. Let P R denotes

R

i

the set of wires fj , such that Supportj ≥ (t ’ u + 1). In addition, R constructs a

2

directed graph G R = (V R , E R ), called con¬‚ict graph, where V R = {f1 , f2 , . . . , fn }

and arc (fi , fj ) ∈ E R if FiR (±R ) = vij .

R

j

3. Corresponding to graph G R , R constructs a con¬‚ict list Y R of ¬ve tuples where

for each arc (fi , fj ) ∈ E R , there exists a ¬ve tuple (fi , fj , ±R , FiR (±R ), vij ) in Y R .

R

j j

R sends Y R to S through bottom band.

Unconditionally Reliable and Secure Message Transmission 321

Before proceeding further, we make the following claim.

Claim. Let fi be a wire which has delivered incorrect FiR (x) = FiS (x) to R and

fj be an honest wire. Then with very high probability (fi , fj ) ∈ E R .

Proof: For complete proof see [7]. 2

Now S considers the con¬‚ict list which it receives identically through at least

u

2 + 1 wires. If S does not receives any con¬‚ict list identically through at least

u u

2 + 1 wires, then S concludes that at least 2 + 1 wires are corrupted in the

bottom band, which further implies that at most t ’ u ’ 1 wires are corrupted

2

in the top band. In this case, the protocol proceeds as shown in Table 7.

Table 7. Execution of Π U RM T if S does not receives u

+ 1 identical con¬‚ict lists

2

Phase III: S to R: By selecting two elements from K as authentication keys, S

authenticates an unique special predetermined signal ”terminate” and sends to R. R

receives the signal correctly with very high probability and concludes that at most

t’ u wires have delivered incorrect values during Phase I. So by using the polynomials

2

received along the ¬rst t ’ u + 1 wires in P R during Phase I, R constructs the array

2

B R . From B R , R recovers mR and terminates.

Lemma 3. If S does not receives the same con¬‚ict list through at least u + 1

2

wires then with very high probability, R correctly recovers mS from the polyno-

mials delivered by the wires in P R .

Proof: For complete proof see [7]. 2

If at the end of Phase III, S receives the same con¬‚ict list, say Y S through at

least u + 1 wires, then S does the following: let the ¬ve tuples in Y S be of the

2

?

form (fi , fj , ±jR , Fi R (±jR ), vij ). For each such four tuple, S checks ±jR = ±S

R

j

?

S R

and vij = vij . If any of these test fails then S concludes that wire fj has delivered

incorrect values to R during Phase I and adds fj to a list LSault . On the other

f

?

hand, if both the test passes then S checks FiS (±S ) = Fi R (±jR ). If the test fails

j

then S concludes that wire fi has delivered incorrect Fi R (x) = FiS (x) to R

during Phase I and adds fi to LSault . Note that S does not know whether Y S

f

is a genuine con¬‚ict list and is indeed sent by R. But still S computes LSault .

f

S now ¬nds the cardinality of list LSault . Now there are two possible cases. If

f

S

|Lf ault | ¤ (t ’ 2 ), then S concludes that at least t ’ u + 1 wires have delivered

u

2

correct polynomial during Phase I. S then performs the same computation as

shown in Table 7. The correctness of the protocol in this execution sequence is

given by Lemma 4.

Lemma 4. If |LSault | ¤ (t ’ u ), then with very high probability, R can correctly

f 2

recover m from the polynomials delivered by the wires in P R .

S

Proof: For complete proof see [7]. 2

If |LSault | ≥ (t ’ u + 1), then S further communicates with R to ¬nd whether

f 2

S

Y was indeed sent by R. For this, S and R executes the steps in Table 8.

Before proceeding further, we state the following lemma.

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

Table 8. Execution of Π U RM T if |LSault | ≥ (t ’ u

+ 1)

f 2

Phase III: S to R: S selects 2|LSault | elements from the set K as authentications

f

keys and using them authenticates each element of LSault by using U Rauth function.

f

Let LSaultauth denotes the set of corresponding authenticated values. S then sends

f

(Y S , LSault , LSaultauth ) to R through top band.

f f

Phase IV: R to S: Let R receives (Yj , LRaultj , LRaultj,auth ) from S along wire

R

f f