Minimizing center key storage in hybrid one-way function based group key management with communication constraints

Abstract

We study the problem of designing a storage efficient secure multicast key management scheme based on one-way function trees (OFT) for a prespecified key update communication overhead. Canetti, Malkin and Nissim presented a hybrid model that divides a group of N members into clusters of M members and assigns each cluster to one leaf node of a key tree. Using the model, we formulate a constrained optimization problem to minimize the center storage in terms of the cluster size M. Due to the monotonicity of the center storage with respect to M, we convert the constrained optimization into a fixed point equation and derive the optimal $M^{*}$ explicitly. We show that the asymptotic value of the optimal $M^{*}$, given as $\mu +\frac{a-1}{{\log }_{e}a}{\log }_e\mu$ with $\mu =\mathrm{O}(\log N)$ and a being the degree of a key tree, leads to the minimal storage as $\mathrm{O}(\frac{N}{\log N})$, when the update communication constraint is given as $\mathrm{O}(\log N)$. We present an explicit design algorithm that achieves minimal center storage for a given update communication constraint.