Cryptography: Theory and Practice:Key Distribution and Key Agreement

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

8.2.1 Blom’s Scheme

As above, we suppose that we have a network of n users. For convenience, we suppose that keys are chosen from a finite field , where p ≥ n is prime. Let k be an integer, 1 ≥ k ≥ n - 2. The value k is the largest size coalition against which the scheme will remain secure. In the Blom Scheme, the TA will transmit k + 1 elements of to each user over a secure channel (as opposed to n - 1 in the basic key predistribution scheme). Each pair of users, U and V, will be able to compute a key K_U,V = K_V,U, as before. The security condition is as follows: any set of at most k users disjoint from {U, V} must be unable to determine any information about K_U,V (note that we are speaking here about unconditional security).

We first present the special case of Blom’s scheme where k = 1. Here, the TA will transmit two elements of to each user over a secure channel, and any individual user W will be unable to determine any information about K_U,V if W ≠ U, V. Blom’s scheme is presented in Figure 8.1. We illustrate the Blom Scheme with k = 1 in the following example.

Example 8.1

Suppose the three users are U, V and W, p = 17, and their public elements are r_U = 12, r_V = 7 and r_W = 1. Suppose that the TA chooses a = 8, b = 7 and c = 2, so the polynomial f is

The g polynomials are as follows:

Figure 8.1 Blom Key Distribution Scheme (k = 1)

The three keys are thus

U would compute K_U,V as

V would compute K_U,V as

We leave the computation of the other keys as an exercise for the reader.

We now prove that no one user can determine any information about the key of two other users.

THEOREM 8.1

The Blom Scheme with k = 1 is unconditionally secure against any individual user.

PROOF Let’s suppose that user W wants to try to compute the key

The values r_U and r_V are public, but a, b and c are unknown. W does know the values

and

since these are the coefficients of the polynomial gW (x) that was sent to W by the TA.

What we will do is show that the information known by W is consistent with any possible value of the key K_U,V. Hence, W cannot rule out any values for K_U,V. Consider the following matrix equation (in ):

The first equation represents the hypothesis that ; the second and third equations contain the information that W knows about a, b and c from g_W (x).

The determinant of the coefficient matrix is

where all arithmetic is done in . Since r_W ≠ r_U and r_W ≠ r_V, it follows that the coefficient matrix has non-zero determinant, and hence the matrix equation has a unique solution for a, b, c. In other words, any possible value of K_U,V is consistent with the information known to W.

On the other hand, a coalition of two users, say {W, X}, will be able to determine any key K_U,V where W and X together know that

Thus they have four equations in three unknowns, and they can easily compute a unique solution for a, b and c. Once they know a, b and c, they can form the polynomial f(x, y) and compute any key they wish.

It is straightforward to generalize the scheme to remain secure against coalitions of size k. The only thing that changes is step 2. The TA will use a polynomial f(x, y) having the form

where , and a_i.j = a_j,i for all i, j. The remainder of the protocol is unchanged.

8.2.2 Diffie-Hellman Key Predistribution

In this section, we describe a key predistribution scheme that is a modification of the well-known Diffie-Hellman key exchange protocol that we will discuss a bit later, in Section 8.4. We call this the Diffie-Hellman Key Predistribution Scheme. The scheme is computationally secure provided a problem related to the Discrete Logarithm problem is intractible.

We will describe the scheme over , where p is prime, though it can be implemented in any finite group in which the Discrete Logarithm problem is intractible. We will assume that a is a primitive element of , and that the values p and α are publicly known to everyone in the network.

In this scheme, ID(U) will denote certain identification information for each user U in the network, e.g., his or her name, e-mail address, telephone number, or other relevant information. Also, each user U has a secret exponent a_U (where 0 ≤ a_U ≤ p - 2), and a corresponding public value

The TA will have a signature scheme with a (public) verification algorithm ver_TA and a secret signing algorithm sig_TA. Finally, we will implicitly assume that all information is hashed, using a public hash function, before it is signed. To make the procedures easier to read, we will not include the necessary hashing in the description of the protocols.

Certain information pertaining to a user U will be authenticated by means of a certificate which is issued and signed by the TA. Each user U will have a certificate

where b_U is formed as described above (note that the TA does not need to know the value of a_U). A certificate for a user U will be issued when U joins the network. Certificates can be stored in a public database, or each user can store his or her own certificate. The signature of the TA on a certificate allows anyone in the network to verify the information it contains.

It is very easy for U and V to compute the common key

as shown in Figure 8.2.

Table of Contents