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.
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.