Stateful Subset Cover

by Mattias Johansson, Gunnar Kreitz, Fredrik Lindholm.

Published in LNCS 3989 (pp. 178-193), Proceedings of ACNS 2006


This paper describes a method to convert stateless key revocation schemes based on the subset cover principle into stateful schemes. The main motivation is to reduce the bandwidth overhead to make broadcast encryption schemes more practical in network environments with limited bandwidth resources, such as cellular networks. This modification is not fully collusion-resistant.

A concrete new scheme based on the Subset Difference scheme is presented, accomplishing a bandwidth overhead of Δm + 2 Δr + 1 compared to e.g. Logical Key Hierarchy's 2(Δm + Δr)log m, where Δm and Δr is the number of members added and removed since the last stateful update and m is the number of current members.

Keywords. Broadcast encryption, key revocation, subset cover, Subset Difference, Logical Key Hierarchy, stateful, stateless.