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