Lower bounds for Subset Cover based Broadcast Encryption
2008 (English)In: PROGRESS IN CRYPTOLOGY - AFRICACRYPT 2008 , 2008, Vol. 5023, 343-356 p.Conference paper (Refereed)
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 Omega(r) For some r, bandwidth is Omega(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.
Place, publisher, year, edition, pages
2008. Vol. 5023, 343-356 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 5023
Broadcast Encryption, Subset Cover, key revocation, lower bounds
IdentifiersURN: urn:nbn:se:kth:diva-31974ISI: 000256541200023ScopusID: 2-s2.0-45449109996OAI: oai:DiVA.org:kth-31974DiVA: diva2:407876
1st International Conference on Cryptology in Africa
QC 201104202011-04-012011-04-012011-10-12Bibliographically approved