Revocation and Tracing Schemes for Stateless Receivers

 Dalit Naor      Moni Naor      Jeff Lotspiech


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 for media devices.

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, 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) providing a seamless integration between the revocation and tracing so that the tracing mechanism does not require any change to the revocation algorithm.

We also give a rigorous treatment of the security of such schemes, identifying the effect of parameter choice on the overall security of the scheme.

Postscript , gzipped Postscript. Slides of talk on the subject: ppt

Related On-Line Papers:

Back to On-Line Publications

Back Home