Paper review: Reliable Group Rekeying: A Performance Analysis

Reviewer: Hanlin D. Qian

The scalability issues of reliable group rekeying and performance improvement are the two main problems that this paper addresses. There are two types of rekeying access control: back access control and forward access control. The traditional implemention of the latter is to distribute a new key to all of N - 1 users after one user leaves, and this process is repeated every time a user leaves. This approach has a large overhead and leads to synchronization problems when the rekeying process repeats faster than it can complete itself.

This paper addresses these problems by making the following four observations, improvements, and methods:

1. The rekeying process can be done in a periodic batch process so that only one repetition is done after every set number of users joins or leaves. The period of time between two rekeying process is called the rekey interval. Essentially, during this interval of time, joining or leaving users will experience a delay before their requests can be handled. There is a trade-off between the shortening of the duration of such a delay and the gained performance of rekeying from using larger batches. This paper also examines how to balance this trade-off.
2. Rekey transport has an eventual reliability and a soft real-time requirement. Also the rekey workload has the sparseness property. Using these observations, the average number of packets that a user has to receive in a rekeying process can be reduced. This property reduces the bandwidth overhead and increases efficiency.
3. The reliable rekey transport of this paper can be analyzed by converting it to conventional reliable multicast.
4. The trade-off between bandwidth requirements and rekey interval is examined in detail in this paper. Bounds and constraints are set to optimize a rekey interval.

I give this paper a rating of 3 for modest contribution. I think this paper has some good ideas and improvements for rekeying process.

The graphs and diagrams in the paper help to make things a little clearer for me. The equations are quite complex and a bit hard to understand. The observations made in the paper are good, but I think they're still quite a ways to being implemented. I'd love to see a comparison of how much better this model works than previous models.

Limitations include that this paper focuses on interactions with only one key server. How are things different when multiple key servers are needed to handle a situation where too many users exist to fulfill all the system constraints discussed in 4.3?