Assignment help

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

计算机科学作业代写: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.


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.


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.