We address the problem of a Center sending a message to a group of users where some subset of the users is considered revoked and should not be able to obtain the content of the message. We concentrate on the stateless receiver/user case, where the users do not (necessarily) update their state from session to session. This scenario is particularly applicable for Copyright Protection.
We present a framework called the Subset-Cover framework, which abstracts a variety of revocation schemes and suggest two new algorithms in this framework. These algorithms are very flexible and work for any number of revoked users. 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.
These methods improve upon previously suggested ones, even when adopted to the stateless scenario, by: (1) reducing the message length to O(r) regardless of the coalition size (r is the number of revoked users) while maintaining a single decryption at the user's end (2) provide a seamless integration between the revocation and tracing so that the tracing mechanism does not require any change to the revocation algorithm.
Joint work with Moni Naor and Jeff Lotspiech.
Gates 4B (opposite 490), 2/13/01, 4:15 PM