Storage-efficient stateless group key revocation

Abstract. Secure group communication relies on secure and robust distribution of group keys. A stateless group key distribution scheme is an ideal candidate when the communication channel is unreliable. Several stateless group key dis-tribution schemes have been proposed. However, these schemes require all users store a certain number of auxiliary keys. The number of such keys increases as the group size grows. As a result, it is quite challenging to use these schemes when the users in a relatively large group have memory constraints. Thus, it is desirable to develop new schemes that can reduce the memory requirement. This paper introduces two novel stateless group key revocation schemes named key-chain tree (KCT) and layered key-chain tree (LKCT), which combine one-way key chains with a logical key tree. These schemes reduce the user storage require-ments by trading off it with communication and computation costs. Specifically, these schemes can revoke any R users from a user group of size N by sending a key update message with at most 4R keys, while only requiring each user to store 2 logN keys.