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