Approximation Algorithms for Key Management in Secure Multicast

Details Approximation Algorithms for Key Management in Secure Multicast Approximation Algorithms for Key Management in Secure Multicast

2009-04-27

arxiv.org/abs/0904.4061v1

Computer Science

Data Structures and Algorithms

COCOON 2009

Scientific paper

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. We 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. We first present a polynomial-time approximation scheme for minimizing the average number of multicast messages needed for an update. We next show that when routing costs are considered, the problem is NP-hard even when the underlying routing network is a tree network or even when every group member has the same update frequency. Our main result is a polynomial time constant-factor approximation algorithm for the general case where the routing network is an arbitrary weighted graph and group members have nonuniform update frequencies.

Affiliated with

Also associated with

No associations

Rating

Approximation Algorithms for Key Management in Secure Multicast does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximation Algorithms for Key Management in Secure Multicast, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation Algorithms for Key Management in Secure Multicast will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-322028