On a Recent Problem of Communication-Storage Tradeoffs for Secure Multicast for Large Networks

A variety of rooted tree-based secure multicast networks with different efficiencies and storage requirements that are linear in group size have been proposed. Recently, Canetti et. al. presented a scheme based on clustering that had sub-linear storage requirements at the group controller. However, they were unable to prove or disprove that the scheme was optimal, and posed it as an open question. In this paper we answer the question with affirmative NO! Additionally we use our results to show that the optimal clustering in this context is related to maximum entropy of member revocation event, and corresponding optimal strategy is to partition members such that each cluster has the same probability of being revoked.Second Workshop on Security in Communication Networks