A Convex Optimization Approach for Addressing Storage-Communication
Tradeoffs in Multicast Encryption
A Convex Optimization Approach for Addressing Storage-Communication
Tradeoffs in Multicast Encryption
Files
Publication or External Link
Date
1999-11-05
Authors
Poovendran, Radha
Advisor
Citation
DRUM DOI
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].