A Convex Optimization Approach for Addressing Storage-Communication Tradeoffs in Multicast Encryption

Abstract

In Eurocrypt'99, Canetti, Malkin, and Nissim [1], presented a new tree based key distribution algorithm that required sublinear storage of keys while preserving logarithmic update communication as functions of the group size. The results in are known to be the first results presenting the sub-linear storage among the family of tree based key distribution schemes. The question of whether this storage was the possible optimal value while keeping the communication as logarithmic was posed as a problem. We show that the storage-communication tradeoff can be formulated as a convex optimization problem in terms of the size of the minimal storage parameter defined in. In particular, we show that the optimal solution is parameterizable by the ratio of the communication and storage costs, the degree of the tree, and the group size. Using this design triplet, we show that not only the results in [1] but also the results of the basic scheme of Wallner, Harder, and Agee [2] can be derived as specific Pareto optimal points for specific choice of the triplet. We also present an exact design procedure for feasibility testing and constructing optimal key distribution tree of the type in. We also show that if the communication and the storage are equally weighted, then the optimal value for storage and communication grows as square root of group size , a value noted in [1].