Networking

Approximation Algorithms for Key Management in Secure Multicast

Free registration required

Executive Summary

Many data dissemination and publish-subscribe systems that guarantee the privacy and authenticity of the participants rely on symmetric key cryptography. An important problem in such a system is to maintain the shared group key as the group membership changes. The authors consider the problem of determining a key hierarchy that minimizes the average communication cost of an update, given update frequencies of the group members and an edge-weighted undirected graph that captures routing costs. They first present a polynomial-time approximation scheme for minimizing the average number of multicast messages needed for an update.

  • Format: PDF
  • Size: 316.05 KB