Abstract In secure multicast communication, group key management plays an essential role for the guarantee of data confidentiality and integrity. Because communication bandwidth is a limited resource, most group key management schemes for scalable secure multicast communications have focused on reducing the number of update messages, i.e., communication cost. To alleviate the scalability problem, a key tree structure was proposed and many group key management schemes have since adopted this approach. Though a key tree structure reduces communication cost, it often requires, as a tradeoff, a more powerful computing capability for executing several cryptography algorithms and having enough storage for various kinds of keys, i.e., computation cost and storage cost, respectively. However, in mobile devices with limited computation power and storage space, it is crucial to minimize simultaneously the overheads of computation and storage as well as that of communication. In this paper, we propose a computation-and-storage-efficient key tree structure, and a key tree management protocol for secure multicast communication. By considering the resource information of each group member’s device, the proposed protocol manages the key tree structure to maximize the efficiency of the computation and storage costs, and to minimize the increment of the communication cost. Through analysis and simulations using three kinds of cost metrics, it demonstrated that the proposed protocol saves computation and storage costs at the expense of a very small increase in communication cost as a tradeoff when the number of total members and the ratio of members leaving in a batch update interval are moderately large.