Minimal key set of binary key-derivation tree in cloud storage

Managing multiple symmetric keys is a critical issue when symmetric cryptography is adopted to protect the confidentiality of the outsourced data in cloud storage. Hierarchical key management utilizing key derivation is a widely studied mechanism. In this mechanism, a large number of keys can be derived from a handful of keys and organized by a hierarchical structure. However, the distribution of multiple derived keys was rarely discussed in the literature. How to minimize the traffic cost of key distribution, especially in the dynamic scenario, is still an open issue. In this paper, we study how to (i) construct a binary key-derivation tree to support in-situ updates, (ii) minimize the traffic cost of distributing derived keys in both static and dynamic cases via the minimal key set. A new key node structure is designed to keep the node positions unchanged during the update process and simplify the generation of the minimal key set. Based on the design, we develop a basic generation algorithm which is the basis of our final algorithm. In addition, the key distribution and re-derivation processes are also expounded as the essential parts of the complete scheme. We also evaluate the performance overheads by extensive experiments and analyze the reduced traffic cost theoretically. The results show the proposed algorithm is efficient and practical in cloud storage systems.