Lower Bounds for Subset Cover Based Broadcast Encryption

by Per Austrin, Gunnar Kreitz

Published in LNCS 5023 (pp. 343-356), Proceedings of Africacrypt 2008


In this paper, we prove lower bounds for a large class of Subset Cover schemes (including all existing schemes based on pseudo-random sequence generators). In particular, we show that

where n is the number of users, r is the number of revoked users, and s is the space required per user.

These bounds are all tight in the sense that they match known constructions up to small constants.

Keywords. Broadcast Encryption, Subset Cover, key revocation, lower bounds