This paper presents efficient revocation and tracing schemes for stateless receivers. The authors introduce a framework called Subset-Cover, which abstracts various revocation schemes. They describe two explicit Subset-Cover revocation algorithms that are flexible and work for any number of revoked users. These algorithms require storage of log N and ½ log² N keys at the receiver, and message lengths of r log N and 2r keys, respectively. A general traitor tracing mechanism is also provided, which can be integrated with any Subset-Cover revocation scheme that satisfies a "bifurcation property." This mechanism does not require an a priori bound on the number of traitors and does not significantly increase message length. The main improvements of these methods over previously suggested methods, when adopted 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) providing seamless integration between revocation and tracing so that the tracing mechanisms do not require any change to the revocation algorithm. The paper also describes two Subset-Cover revocation algorithms: the Complete Subtree method and the Subset Difference method. The Complete Subtree method requires message length of at most r log (N/r) keys, storage of log N keys at a receiver, and O(log log N) operations plus a single decryption. The Subset Difference method requires message length of at most 2r-1 keys, storage of ½ log² N keys at a receiver, and O(log N) operations plus a single decryption. Both methods are secure and efficient. The paper also discusses the integration of tracing and revocation, and presents a tracing mechanism that works for any Subset-Cover revocation scheme that satisfies the bifurcation property. This mechanism allows the identification of traitors without requiring any changes to the revocation algorithm. The tracing mechanism does not require an a priori bound on the number of traitors and does not significantly increase message length. The paper concludes with a discussion of the applications of these methods, including copy protection and secure multicast. The methods are particularly suitable for stateless receivers, where the receiver is not constantly online. The paper also discusses the use of public-key methods and hierarchical revocation, and provides a comparison of the performance of the methods with existing schemes.This paper presents efficient revocation and tracing schemes for stateless receivers. The authors introduce a framework called Subset-Cover, which abstracts various revocation schemes. They describe two explicit Subset-Cover revocation algorithms that are flexible and work for any number of revoked users. These algorithms require storage of log N and ½ log² N keys at the receiver, and message lengths of r log N and 2r keys, respectively. A general traitor tracing mechanism is also provided, which can be integrated with any Subset-Cover revocation scheme that satisfies a "bifurcation property." This mechanism does not require an a priori bound on the number of traitors and does not significantly increase message length. The main improvements of these methods over previously suggested methods, when adopted 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) providing seamless integration between revocation and tracing so that the tracing mechanisms do not require any change to the revocation algorithm. The paper also describes two Subset-Cover revocation algorithms: the Complete Subtree method and the Subset Difference method. The Complete Subtree method requires message length of at most r log (N/r) keys, storage of log N keys at a receiver, and O(log log N) operations plus a single decryption. The Subset Difference method requires message length of at most 2r-1 keys, storage of ½ log² N keys at a receiver, and O(log N) operations plus a single decryption. Both methods are secure and efficient. The paper also discusses the integration of tracing and revocation, and presents a tracing mechanism that works for any Subset-Cover revocation scheme that satisfies the bifurcation property. This mechanism allows the identification of traitors without requiring any changes to the revocation algorithm. The tracing mechanism does not require an a priori bound on the number of traitors and does not significantly increase message length. The paper concludes with a discussion of the applications of these methods, including copy protection and secure multicast. The methods are particularly suitable for stateless receivers, where the receiver is not constantly online. The paper also discusses the use of public-key methods and hierarchical revocation, and provides a comparison of the performance of the methods with existing schemes.