We describe two explicit Subset-Cover revocation algorithms; these algorithms are very flexible and work for any number of revoked users. The schemes require storage at the receiver of $\log N$ and $\frac{1}{2} \log^2 N$ keys respectively ($N$ is the total number of users), and in order to revoke $r$ users the required message lengths are of $r \log N$ and $2r$ keys respectively. We also provide a general traitor tracing mechanism that can be integrated with any Subset-Cover revocation scheme that satisfies a ``bifurcation property''. This mechanism does not need an a priori bound on the number of traitors and does not expand the message length by much compared to the revocation of the same set of traitors.
The main improvements of these methods over previously suggested methods, when adapted to the stateless scenario, are: (1) reducing the message length to $O(r)$ regardless of the coalition size while maintaining a single decryption at the user's end (2) provide a seamless integration between the revocation and tracing so that the tracing mechanisms does not require any change to the revocation algorithm.
Category / Keywords: foundations / broadcast encryption, traitor tracing, key management, multicast, revocation scheme Publication Info: Published in Crypto 2001 Date: received 24 Jul 2001, last revised 5 Dec 2001 Contact author: dalit at il ibm com Available format(s): PDF | BibTeX Citation Version: 20011205:104841 (All versions of this report) Short URL: ia.cr/2001/059 Discussion forum: Show discussion | Start new discussion