计算机科学作业代写：Study On Computation Efficient Multicast Key Distribution

Efficient key distribution is an important problem for secure group communications. The communication and storage complexity of multicast key distribution problem has been studied extensively. In this paper, we propose a new multicast key distribution scheme whose computation complexity is significantly reduced. Instead of using conventional encryption algorithms, the scheme employs MDS codes, a class of error control codes, to distribute multicast key dynamically. This scheme drastically reduces the computation load of each group member compared to existing schemes employing traditional encryption algorithms. Such a scheme is desirable for many wireless applications where portable devices or sensors need to reduce their computation as much as possible due to battery power limitations. Easily combined with any key-tree-based schemes, this scheme provides much lower computation complexity while maintaining low and balanced communication complexity and storage complexity for secure dynamic multicast key distribution.

Index Terms-Key distribution, multicast, MDS codes, erasure decoding, computation complexity.

INTRODUCTION

IN many applications, multicast is an efficient means of distributing data in terms of resources (such as network bandwidth, server computation, and I/O load) usage. The privacy of a multicast communication session is usually ensured using (symmetric) encryption. All the designated receivers or members in a multicast group share a session (encryption) key. In many applications, however, the multicast group membership changes dynamically, i.e., some new members are authorized to join a new multicast session, whereas some old members should be excluded. Thus, session keys shall change dynamically to ensure both forward secrecy and backward secrecy of multicast sessions. The forward secrecy is maintained if an old member who has been excluded from the current and future sessions cannot access the communication of the current and future sessions, and the backward secrecy is guaranteed if a new member of the current session cannot recover the communication data of past sessions. Each session thus needs a new key that is only known to the current session members, i.e., session keys need to be dynamically distributed to

authorized session members.

In this paper, we study how a multicast group key can efficiently be distributed in computation. We adopt a common model where session keys are issued and distributed by a central group controller (GC), as it has much less communication complexity, as compared to distributed key exchange protocols, which is a very desired property in most wireless applications. The resources needed for the GC to distribute session keys to group members include communication, storage, and computation resources. The communication complexity is usually measured by the number of data bits that need to be transmitted from the GC to group members to convey information of session keys, whereas the storage complexity is measured by the number of data bits that the GC and group members need to store to obtain session keys. Another similarly important but usually undernoticed, if not ignored, factor is the computation complexity, which can be measured by the number of computation operations (or the computation time on a given computing platform) that the GC and group members need to distribute and extract session keys. Hereafter, the problem of how resources can effectively be used to distribute session keys is referred to as the group key distribution problem.

The group key distribution problem has been studied extensively in the larger context of key management for secure group communications mainly on balancing the storage complexity and the communication complexity. There are two trivial schemes for distributing a session key to a group of n members. The first one is that the GC shares an individual key with each group member, which can be used to encrypt a new group session key. In this scheme, the communication complexity is O(n), whereas the GC needs to store O(n) key information, each member stores O(1) key information, and O(n) encryption and decryption operations are needed. In the second scheme, the GC shares an individual key with each subset of the group, which can then be used to multicast a session key to a designated subset of group members. Now, both the communication complexity and the computation complexity reduce to O(1), but at the cost of increasing the storage complexity to O(2n) for both the GC and each group member. It is easy to see that neither scheme works for practical applications with a reasonable group size n. Thus, research efforts have been made to achieve low communication and storage complexity for group key distribution.

计算机科学作业代写：Study On Computation Efficient Multicast Key Distribution

2.THE BASIC SCHEME: DYNAMIC KEY DISTRIBUTION USING MAXIMUM DISTANCE SEPARABLE CODES

2.1 Maximum Distance Separable Codes

Maximum Distance Separable (MDS) codes are a class of error control codes that meet the Singleton bound. Letting GF (q) be a finite field with q elements , an (n; k) (block) error control code is then a mapping from GF (q)k to GF (q)n : E(m) = c, where m = m1m2 … mk is the original message block, c = c1c2 … cn is its code word block, and E(.) is an encoding function, with k <= n. If a decoding function D(.) exists such that D(ci1 ci2 … cik ; i1; i2; . . . ; ik) = m for 1 <= ij <= n and 1 <= j <= k, then this code is called an (n; k) MDS code. For an (n; k) MDS code, the k original message symbols can be recovered from any k symbols of its code word block. The process of recovering the k message symbols is called erasure decoding. All the symbols are defined over GF (q), and usually, q = 2m. The well-known Reed-Solomon (RS) codes are a class of widely used MDS codes. Notably, the RS codes and other MDS codes can be used to construct secret-sharing and threshold schemes .

2.2 Description of the Basic Scheme

For a dynamic multicast group, a session key is issued by a GC. Using this session key, the GC can establish a secure multicast channel with the authorized group members. Every time group memberships change because of the join or leave of some group members, the GC reissues a new session key, which is independent of all the old session keys. This rekeying procedure ensures the security of the current session and that of the old sessions, i.e., the newly joined members cannot recover the communications of the old sessions, and those old members who left the group cannot access the current session. Thus, both the backward secrecy and the forward secrecy of group communication are maintained.

The complexity of the rekeying operation is asymmetric between a new member's join and an old member's leave. When a new member joins, the GC can easily multicast the new session key encrypted by the current session key to all the current members, followed by a uni-cast to the new member to send the new session key encrypted by a predetermined encryption key shared between the GC and the new member. Thus, join is easy, with low communication and computation cost. However, when an old member leaves, the current session key cannot be used to convey the new session key information securely, since it is also known to the old member. Thus, hereafter, we will focus on the rekeying operation for a single member leave. The same idea can easily be extended to other rekeying operations such as batch rekeying .

2.2.1 Group Controller Initialization

Initially, the GC constructs a nonsystematic (L; n) MDS code C over GF (q) and a secure one way hash function H(.) whose codomain is GF (q). (For a nonsystematic code, none of the original message block symbols directly appears in the corresponding code word block.) The domain of H(.) can be an arbitrary space F that is large enough so that H(.) has a secure one-way property: given any arbitrary y E GF (q), it is impossible or computationally hard to derive x E F such that H(x) = y.

2.2.2 Member Initial Join

Whenever a new member i is authorized to join the multicast group for the first time, the GC sends it (using a secure unicast) a pair (ji; si), where si is a random element in H(₃)'s domain F , and ji is a positive integer satisfying ji not equal to jk for all k's, where k is a current member of the multicast group. The pair (ji; si) will be used as member i's seed key (denoted as Si) and is kept in the GC's local database, as long as member i remains a potential member of the multicast group.

计算机科学作业代写：Study On Computation Efficient Multicast Key Distribution

2.2.3 Rekeying

Whenever some new members join or some old members leave a multicast group, the GC needs to distribute a new session key to all the current members. As already discussed, we will focus on the rekeying operation when an old member leaves. After an old member leaves, the GC needs to distribute a new key to n remaining members to achieve both forward and backward secrecy of the session key.

The GC executes the rekeying process in the following steps:

The GC randomly chooses a fresh element r in F , which has not been used to generate previous keys.

In the remaining group of n members, for each member i of the current group with its seed key (ji; si), the GC constructs an element cji in GF (q) : cji = H(si + r), where + is a simple combining operation in F , for example, string concatenation.

Using all the cji 's in the above step, the GC constructs a code word c of the (L; n) MDS code C: set the (ji)th symbol of the code word c to be cji . Since C is an (L; n) MDS code, the code word c is uniquely determined by its n symbols. Using an efficient erasure decoding algorithm for C, the GC can easily calculate the n corresponding message symbols m1m2 . . . mn.

The GC sets the new session key k to be the first message symbol m1 : k = m1.

The GC multicasts r and m2 . . . mn.

The above rekeying process is illustrated in Fig. 1a. Note that when n = 1, i.e., there is only one member remaining, then in step 3 above, the (L; n) MDS code becomes a trivial repetition code, i.e., all the symbols in a code word are the same. Hence, the decoding algorithm in step 3 becomes trivial, i.e., m1 = cji , without the need to compute any other mi (i >= 2). This is also intuitive: the GC in this case simply sets a session key that is solely derived from the remaining member's seed key (ji; si).

Upon receiving r and m2m3. . . mn from the GC, an authorized member i of the current group executes the following steps to obtain the new session key:

1. Calculate cji = H(si + r) with its seed key (ji; si).

Decode the first message symbol m1 from the (n - 1) message symbols m2 . . . mn, together with its code word symbol cji .

Recover the new session key k, i.e., k = m1.

Fig. 1. Rekeying process of the basic scheme. (a) GC's operations. (b) Operations of members.

This key recovery process, as shown in Fig. 1b, finishes the whole rekeying procedure. Note that in step 2 of the key recovery process, virtually, all MDS codes in use, for example, the RS code, are linear, i.e., any single code word symbol is a linear combination of all the n original message symbols. This decoding process is essentially for solving a single linear equation with only one unknown. Thus, it is equivalent to an encoding operation with much lower computation than a general erasure decoding operation for multiple unknowns.

The MDS property of the code C ensures that each authorized member, with its cij and m2 . . . mn, can derive the new session key k = m1 as the GC. It is worth noting that the new session key k is only the first message symbol m1, which is independent of all the other message symbols m2 . . . mn. Thus, any unauthorized receiver cannot deduce m1 just from m2 . . . mn, since it needs one more symbol of the code word c. Any stale seed key (j0i; s0j) cannot generate a valid symbol of the current code word c, since the pair (j0i; s0j) is not used in the generation of c. Thus, both the forward and the backward secrecy are achieved.

2.3 Evaluation of the Basic Scheme

As can be seen from the above basic scheme, for all the authorized group members, the GC generates a new session key by generating a common new message word, the first symbol of which is used as the new session key. The new session key is decided by a random element r in F , as well as all the seed keys of the current authorized group members. The random element r and the (n - 1 ) message symbols are multicast in plaintext to all the group members, and the computation cost is thus much lower than using encrypted point-to-point communications for the rekeying process in all existing schemes. The computation operations needed for this new scheme are erasure decoding of a chosen MDS code, a one-way hash function, and some simple combining functions, all of which can be implemented efficiently and are computationally much cheaper than traditional encryptions.

2.3.1 Security

Since r and m2 . . . mn are multicast in plaintext and are thus known to all interested parties, including unauthorized receivers who attempt to access the current session, the security of the new session key relies on the secrecy of a code word symbol cji that authorized member i of the current multicast group has. The secrecy of cji , in turn, depends on the secrecy that the seed key member i has. Thus, an attacker who attempts to deduce the new session key k has three potential options:

brute-force attack, i.e., guessing the session key k itself,

guessing a symbol ck of the code word, or

guessing a current member's seed key.

2.3.2 Complexity

When a new member i is authorized to join a multicast group, the GC assigns a seed key pair (ji; si) to it. This seed key pair remains valid until member i leaves the multicast group permanently. Thus, the seed key pair is unicast only once to an authorized member. Compared to the rekeying procedure that is needed whenever there is a membership change for the multicast group, this communication cost (in terms of the number of the bits transmitted) is negligibly small.

Fig. 2. A key tree for a nine-member group.

PRACTICAL KEY DISTRIBUTION: APPLYING THE BASIC SCHEME TO KEY TREES

The basic key distribution scheme reduces computation complexity by replacing computationally expensive encryption and decryption operations with more efficient erasure decoding operations of MDS codes. This basic scheme has the same communication complexity as conventional key distribution schemes using secure unicasts. Thus, the basic scheme can be readily used as a building block to replace encrypted unicasts in any key distribution schemes, particularly schemes with low communication complexity.

To reduce the communication complexity of rekeying operations, a key-tree-based scheme and many of its variations have been proposed. This scheme reduces the communication complexity of rekeying operations to O(logn), whereas each member needs to store O(logn) keys, and the GC needs to store O(nlogn) keys, where n is the multicast group size. This is the most practical key distribution scheme, which balances the communication and storage complexity for dynamic multicast key distribution.

计算机科学作业代写：Study On Computation Efficient Multicast Key Distribution

3.1 Key-Tree-Based Rekeying Scheme

The main idea of reducing the rekeying communication complexity of this scheme is to have the GC distribute subgroup keys in addition to individual member keys and the group session key. These keys are arranged in a logical tree hierarchy, where the group session key serves as the root, the individual member keys are the leaves, and the subgroup keys correspond to intermediate nodes. Each member stores all the keys along the path from the corresponding leaf to the root in the tree. Then, each subgroup key can be used to securely multicast to the members that are leaves of the corresponding subtree. During the rekeying process, the GC can thus securely multicast to a subgroup of members using their shared subgroup key instead of individual member keys.

Fig. 2 shows a key tree for a nine-member group. Ki (1 <= i <= 9) is the individual key of member i. K1- 9 is the group session key that is shared by all the members. Finally, K1-3, K4-6, and K7-9 are three subgroup keys for the three corresponding subgroups respectively. For example, K1-3 is shared by members 1 through 3, who form the first subgroup.

3.2 MDS Code-Based Rekeying on a Key Tree

The GC initialization and each member's initial join can be performed exactly the same on a key tree as in the basic scheme described in Section 2.2. Thus, we focus on the adaption of the basic scheme for rekeying on a key tree.

MDS Code Implementation for the Rekeying Operation

As pointed out previously, d needs to be 3 to minimize the communication complexity during rekeying. Hence, only two types of MDS codes are needed, which are (L; 2) and (L; 3) codes. In fact, the rekeying scheme only needs two specific MDS codes, i.e., an (L; 2) code and an (L; 3) code. Although any general (n; k) MDS code can be used for the rekeying purpose by setting k = 2 or k = 3, there are a number of optimization techniques that can be applied for special implementations of the (L; 2) and (L; 3) codes. As we shall see in the following, these techniques turn out to make the codes used for rekeying extremely fast, even though they do not readily extend to the implementations of general MDS codes.

Reed-Solomon (RS) Implementation: Vandermonde Representation versus Cauchy Representation

We choose the RS codes [28] as the MDS codes, since it is the most widely used MDS code. Among numerous ways of constructing an RS code, the two popular ones are Vandermonde and Cauchy representations. In the Vander-monde representation, a Vandermonde Matrix is used as a generator matrix for the chosen RS code [19], which is a traditional description of the RS code. Recently, a Cauchy representation for the RS code has been proposed to make general encoding and decoding of an RS code faster by using mostly XOR operations instead of more expensive finite-field operations [5]. In this representation, a Cauchy Matrix is used as a generator matrix.

For our rekeying purpose, an RS decoding operation is equivalent to solving a group of linear equations. It thus mainly involves two steps: 1) inverting a coefficient matrix and 2) multiplying the inverse matrix to get the values of the unknowns. In general, the second step has quite similar complexity among different representations for the same code. Thus, if one code representation has lower complexity in the first step (inverting the coefficient matrix), its overall decoding operation will be more efficient. It is well understood that the inversion of the Cauchy matrix requires less complexity than that of the Vandermonde matrix. Therefore, in general, Cauchy-matrix-based RS codes are considered as more efficient than Vandermonde-matrix-based RS codes [5], [25].

Quite contrary, we observe that Vandermonde representations are, in fact, more efficient for (L; 2) and (L; 3) RS codes in terms of decoding operations for the rekeying process. The main reason is that the inverse Vandermonde matrix is much simpler than the inverse Cauchy matrix for k = 2 and k = 3. Taking k = 3 as an example, a more

computation-efficient variant of a Vandermonde-matrix-based RS code can be represented as follows [23], [24]:

where i, j, and k are the positions of members assigned by the GC when they join the multicast group. They are also considered to be elements in the corresponding finite field GF(2m), which is used to construct the RS codes. Then, the inverse matrix can be represented as

Note that m1 is just the multicast session key here. Similarly, the RS codes constructed from the Cauchy

matrix can be represented as

where xi, xj, and xk change values based on the positions of the members, whereas y1, y2, and y3 are constants. The inverse matrix turns out to be much more complicated than that of the Vandermonde matrix, so we simply present one single entry to further elaborate. Letting d1;1 be the entry of the inverse matrix at row 1 and column 1, then

It is true that the common terms ( for example y1 y2 , y2 y3, and y1 y3) can be pre computed for each given code construction, but still, every entry requires more operations than the inverse of the Vandermonde matrix.

Based on the above observation, we choose to use the Vandermonde matrix to construct the (L; 2) and (L; 3) RS codes, instead of using the Cauchy matrix, as conventional wisdom suggests.

Optimized Lookup Table for Multiplication and Division

Finite-field multiplication and division are usually implemented via lookup tables. Each element (except 0) in a finite field can be represented as a power to a primitive element (say, ). Hence, the multiplication of two elements a and b can be done by first adding the power values together and then calculating the exponential value as

a x b = αlogαa+logαb: (5)

It is straightforward to pre compute a logarithmic table and an exponential table for a given finite field. With that, the multiplication can simply be implemented by look up tables as

a x b = exp[log[a] ) log[b]]. (6)

Similarly, the division can be implemented

a x b = exp[log[a] - log[b[]. (7)

Careful readers might immediately spot the potential problems of the exponential table, as 1) element a or b might be 0, which will not yield correct results from the lookup table, 2) the index to the table might exceed the table boundary in the multiplication case, and 3) the index to the table might become negative in the division case. These issues can essentially be addressed by augmenting the exponential table in the following ways: 1) augmenting the table such that the sum of two power values is always covered, 2) further augmenting the table such that 0 maps to a remote entry in the table such that a further operation (plus/minus) results in a region nearby, where all corresponding values are 0, and 3) shifting the pointer to the table such that negative indices are allowed. Of course, the last one is programming language specific. However, even without programming language support, the same goal can still be achieved simply by adding a constant offset to a computed (negative) index. These techniques are also applicable to general implementations of the RS codes.

Considering our special needs of implementing the (L; 2) and (L; 3) codes, we discover that the lookup table idea can be extended to further simplify operations. The most complicated calculation in (2) requires three multiplications and two divisions (for example ). Hence, instead of performing this calculation as a series of binary operations, where each operation is similar to (6) or (7), we can build a special augmented exponential table to accommodate the entire 5-ary calculation as

(a x b x c) ÷ (d x e)

= exp[log[a] + log[b] + log[c] - log[d] - log[e]]. (8)

In addition, notice that only element a could take value 0 (b, c, d, and e cannot be 0 due to the construction of the RS codes), which means that the table needs just slightly further augmentation to accommodate this special case. Indeed, when a finite-field GF(256) is used, an exponential table of size 2,304 is sufficient. Assuming that negative index is supported, then the table spans from [-1,535,768]. Exp[-1535, -512] always maps to 0 to handle the special case when a = 0 (the logarithmic table maps 0 to -1,024 here, i.e., log[0] = -1024), and exp[-511, 768] handles normal 5-ary operations (multiplications together with divisions). It is conceivable that such exponential table can easily fit into the fast cache of modern computing devices.

计算机科学作业代写：Study On Computation Efficient Multicast Key Distribution

3.3.3 Size of the Finite Field

In most current applications, a session key needs to be at least 128 bits to be considered reasonably secure. According to the basic scheme, m = lr = t = 128 bits, so the RS codes should be constructed in a finite field of GF(2128). In such a field, each element is represented by 128 bits, and the total number of elements is 2128. Apparently, this field is too large to have an efficient and meaningful implementation, as it is impossible to have a logarithmic table or an exponential table of this size. Instead, we choose to construct the RS codes in a much smaller field of GF(28), where each element is represented by 8 bits, and there are total 256 elements in the field. This way, a 128-bit key is composed of 16 elements in the finite field.

Comparison with Traditional Cryptographic Schemes

To evaluate the proposed scheme, a multicast key distribution scheme is implemented to disseminate 128-bit session keys among a 3-ary balanced key tree. The proposed scheme is compared with traditional cryptographic schemes. As the communication and storage complexity are the same among all the schemes, it suffices to simply compare the computation complexity.

The comparison considers the following scenario, where each three-member group has one member that departs. These departures are not constrained to happen at the same time, but in practice, they might tend to be close, for example, at the end of one movie broadcast, etc. This makes a batch process possible, which means that all remaining members could be rekeyed at once.

Before reporting the experimental results, it is worth pointing out that any one-way hash function used in the proposed scheme can be simplified from general-sense hash function implementations. For instance, we use the MD5 algorithm [31, chapter18] as an exemplary hash function in our evaluation, which produces a 128-bit hash output from any arbitrary length input. A general MD5 input consists of three components: 1) input data, 2) padding bits, and 3) a final 64-bit field for length. In our case, as the input is always 128 bits, we can preset the final length field to represent 128. Moreover, all the rest bits can be set to 0 and removed from the MD5 logic. This tends to make the MD5 algorithm more efficient. Obviously, the same method can be readily applied to other hash algorithms, for example, SHA-1 and SHA-256 [31, chapter 18], should the MD5 algorithm be considered insufficient or using longer session keys becomes necessary.

Fig. 3 shows the computation time of the key dissemination and recovery using different schemes under various multicast group sizes. The experiments are carried out on a Pentium 4 2.53-GHz machine with a 512-Mbyte memory running Linux Red hat 9.0. It is clear that using one-way hash functions adds none-trivial computation complexity. Nevertheless, the proposed scheme still outperforms the conventional cryptographic schemes by a significant margin.

The computation time of the key distribution is also compared to conventional stream ciphers, as shown in Table 1, for a selected multicast group size. Notice that the computation times of both the GC and the member using the RC4 cipher are significantly larger than using other schemes. Even though RC4 itself is a fast stream cipher, its Computation Time Comparing to the RC4 Approach (Multicast Group Size of 59,049)

Fig. 3. Computation time for key distribution (the RS(MD5) shows the proposed scheme, whereas the RS curve excludes the hash function).

GC's computation time for key dissemination. (b) A member's computation time for key recovery.

TABLE 1

key scheduling process has dominant effect in this particular scenario, where only 128-bit data is encrypted/ decrypted using any given key. Results under other multicast group sizes are similar, which are thus not duplicated here.

Finally, it is worth noting that our basic scheme simply reduces computation complexity by replacing crypto-graphic encryption and decryption operations with more efficient encoding and decoding operations. It is orthogonal to any other schemes that use different rekeying protocols and procedures. This basic scheme can always be combined with any rekeying schemes that use cryptographic encryption and decryption operations. For example, this basic scheme can be readily adapted to incorporate the so-called one-way function tree scheme [33], where a different rekeying protocol on a key tree is used other than the traditional scheme, as described in Section 3.1, to further reduce the computation complexity. We leave this simple exercise to interested readers.

4 CONCLUSION

We have presented a dynamic multicast key distribution scheme using MDS codes. The computation complexity of key distribution is greatly reduced by employing only erasure decoding of MDS codes instead of more expensive encryption and decryption computations. Easily combined with key trees or other rekeying protocols that need encryption and decryption operations, this scheme provides much lower computation complexity while maintaining low and balanced communication complexity and storage complexity for dynamic group key distribution. This scheme is thus practical for many applications in various broadcast capable networks such as Internet and wireless network.

芝加哥作业代写