Paper review:  Reliable Group Rekeying: A Performance Analysis

Reviewer: Kevin Hofstra

  1. What is the best way to manage the distribution of group keys in secure group communication such as teleconferencing or multiplayer games?  How must you deal with the constant entry and departure of key holders?  What are the performance requirements of the key server, and what is the limit on the number of group members?
  2. An evaluation of several methods of key distribution, recoding efficiency, and transport.  Analysis of the performance gains in the combination of each self-optimal process.


A.         Reliable rekey transport has 2 requirements:

i.                     Eventual reliability.  The receiver must be able to eventually receive all of the keys.  This is fundamental because this is the only way that they can continue to be a part of the group.

ii.                   Soft real-time requirement.  The rekey transport must be finished by the start of the next rekey interval (with at least a high probability).  This is to ensure that the individual users do not get out of synchronization with the rest of the group.  Rekeying is dependant on having each key in succession to find the next.

B.                 The keygem group management system is based upon the use of key trees.  This changes the rekeying problem to the log of the previous problem.

C.                 Instead of rekeying on the occurrence of a entry or exit, they use periodic batch rekeying to improve scalability and alleviate out of synchronization problems among rekey messages as well as between rekey and data messages.

D.                 The rekey workload has a sparseness factor.  This means that each member of the group only needs to receive a small fraction of the packers that carry a rekey message sent by the key server.

  1. Critique the main contribution
  2. Systems annalists and researchers should recognize that the combination of a few older ideas with some breakthrough ideas can lead to very large performance gains.  Many of the breakthrough ideas in this paper were started by other research, but have been optimized through further research.  I think that this paper shows that many simple ideas can be made better, although more complicated, by combining new strategies.