Designing a key distribution protocol with minimal computation and storage complexity is a challenging issue in secure multimedia multicast. In most of the multimedia multicast applications, the group membership requires secured dynamic key generation and updation operations that usually consume much of the computation time. In this paper, we propose a new GCD (Greatest Common Divisor) based Key Distribution Protocol which focuses on two dimensions. The first dimension deals with the reduction of computation complexity which is achieved in our protocol by performing fewer multiplication operations during the key updation process. To optimize the number of multiplication operations, the existing Karatsuba divide and conquer approach for multiplication is used in this proposed work. The second dimension aims at reducing the amount of information stored in the Group Center and group members while performing the update operation in the key content. The proposed algorithm which focuses on these two dimensions has been implemented and tested using a Cluster tree based key management scheme and has been found to produce promising results. Comparative analysis to illustrate the performance of various key distribution protocols is shown in this paper and it has been observed that this proposed algorithm reduces the computation and storage complexity significantly. © 2012 Elsevier Ltd. All rights reserved.