Lower Bounds for Subset Cover Based Broadcast Encryption

by Per Austrin, Gunnar Kreitz

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

Abstract

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

Download

• Slides from presentation at Africacrypt 2008
• Full Article