Method for broadcast encryption and key revocation of stateless receivers

Abstract

A tree is used to partition stateless receivers in a broadcast content encryption system into subsets. Two different methods of partitioning are disclosed. When a set of revoked receivers is identified, the revoked receivers define a relatively small cover of the non-revoked receivers by disjoint subsets. Subset keys associated with the subsets are then used to encrypt a session key that in turn is used to encrypt the broadcast content. Only non-revoked receivers can decrypt the session key and, hence, the content.

1. A digital processing apparatus accessing a computer readable storage medium storing logic, the logic comprising:
 assigning each user in a group of users respective private information I u ; 
 selecting at least one session encryption key K; 
 partitioning users not in a revoked set R into disjoint subsets S il , . . . S im  having associated subset keys L il , . . . L im ; 
 encrypting the session key K with the subset keys L il , . . . , L im  to render m encrypted versions of the session key K; 
 identifying subsets of users using a subset difference routine wherein respective groups of users correspond to a universe of sets S l , . . . , S w  that can be described as “a first subtree A minus a second subtree B that is entirely contained in A” with each node in the tree having a set of labels, one unique to the node and others that are induced by ancestor nodes and with each user being assigned labels from all nodes hanging from nodes in a direct path between the user and the root but not from nodes in the direct path itself, further comprising: 
 partitioning the users into groups S l , . . . , S w , wherein “w” is an integer, and the groups establish subtrees in a tree; 
 using private information I u  to decrypt the session key, wherein the act of decrypting includes using information i j  such that a user belongs to a subset S ij , and retrieving a subset key L ij  using the private information of the user.