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

- For small
`r`, bandwidth is Ω(`r`) - For some
`r`, bandwidth is Ω(`n`/ log(`s`)) - For large
`r`, bandwidth is`n`-`r`

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

- Slides from presentation at Africacrypt 2008
- Full Article