Back to results
US 7,925,025 B2Granted
Method for broadcast encryption and key revocation of stateless receivers
AssigneeInternational Business Machines Corporation
InventorsJeffrey Bruce Lotspiech, Dalit Naor, Simeon Naor
Life of this patent
Estimating the term…
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.
Claims49
A method comprising:
- supplying each user in a group of users respective private information Iu;
- selecting at least one session encryption key K;
- at least in part using a processor accessing a non-transitory storage medium, partitioning users not in a revoked set R of revoked receivers into disjoint subsets Si1, . . . Sim having associated subset keys Li1, . . . Lim;
- encrypting the session key K with the subset keys Li1, . . . , Lim to render m encrypted versions of the session key K, wherein each user deduces at least one subset key using its private information;
- identifying subsets of users using at least one of:
- (a) a subset difference routine wherein respective groups of users correspond to a universe of sets S1, . . . , Sw that is 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, or (b) a complete subtree routine wherein respective subsets correspond to all possible subtrees in a complete tree and each user is assigned keys from all nodes that are in a direct path between a leaf representing the user and the root of the tree, wherein the complete subtree routine includes defining a spanning tree having leaves established by the revoked set R of revoked receivers, the spanning tree being a subtree of a tree connecting leaves corresponding to revoked receivers, subtrees having roots adjacent to nodes of degree one of the spanning tree establishing subsets Si1, . . . , Sim encompassing all non-revoked receivers.
3 more elements
A computer program device, comprising:
- a computer program storage device including a program of instructions usable by a computer, comprising:
- logic means, including at least one of:
- a subset difference routine wherein the subset difference routine is described at least in part by “a first subtree A minus a second subtree B that is entirely contained in A” with at least some nodes of one or more of the subtrees having at least one or more labels and with at least some users being assigned labels from all nodes hanging from nodes in a direct path between the user being assigned labels and the root but not from nodes in the direct path itself, and a complete subtree routine, for accessing a tree to identify plural subset keys, wherein the complete subtree routine includes defining a spanning tree having leaves established by a revoked set R of revoked receivers, the spanning tree being a subtree of a tree connecting leaves corresponding to revoked receivers, subtrees having roots adjacent to nodes of degree one of the spanning tree establishing subsets Si1, . . . , Sim encompassing all non-revoked receivers;
- logic means for encrypting a message with a session key;
- logic means for encrypting the session key at least once with each of the subset keys to render encrypted versions of the session key;
- and
- logic means for sending the encrypted versions of the session key in a header of the message to plural stateless receivers.
4 more elements
A computer programmed with instructions carried on a non-transitory computer readable storage medium to cause the computer to:
- encrypt broadcast content by executing a complete subtree routine or a subset difference routine wherein respective groups of users correspond to a universe of sets S1, . . . , Sw 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, wherein the complete subtree routine includes defining a spanning tree having leaves established by a revoked set R of revoked receivers, the spanning tree being a subtree of a tree connecting leaves corresponding to revoked receivers, subtrees having roots adjacent to nodes of degree one of the spanning tree establishing subsets Si1, . . . , Sim encompassing all non-revoked receivers;
- and
- send the encrypted broadcast content to plural stateless receivers and to at least one revoked receiver such that each stateless receiver decrypts the content and the revoked receiver cannot decrypt the content.
A method for broadcast encryption, comprising:
- assigning each user in a group of users respective private information Iu;
- selecting at least one session encryption key K;
- using a processor accessing a computer-readable storage medium, partitioning all users into groups S1, . . . , Sw, wherein “w” is an integer greater than one, and the groups establish subtrees in a tree;
- partitioning users not in a revoked set R into disjoint subsets Si1, . . . Sim having associated subset keys Li1, . . . Lim, wherein “I” is an integer equal to or greater than one and “m” is an integer greater than one;
- and
- encrypting the session key K with the subset keys Li1, . . . , Lim to render m encrypted versions of the session key K, wherein the tree includes a root and plural nodes, each node having at least one associated label, and wherein each subset includes all leaves in a subtree rooted at some node vi except for leaves of a subtree rooted at some other node vj that descends from vi.
3 more elements
A receiver of content, comprising:
- computer readable storage storing respective private information Iu;
- processor receiving at least one session encryption key K encrypted with plural subset keys, the session key encrypting content;
- and
- the processor obtaining at least one subset key using the private information such that the session key K is decryptable to play the content, wherein the receiver is partitioned into one of a set of groups S1, . . . , Sw, wherein “w” is an integer, and the groups establish subtrees in a tree defining nodes and leaves, wherein subsets Si1, . . . , Sim derived from the set of groups S1, . . . , Sw define a cover of non-revoked receivers, wherein a revoked set R of revoked receivers defines a spanning tree, and subtrees having roots attached adjacent to nodes of the spanning tree define the cover.
1 more element
A receiver of content, comprising:
- a data storage storing respective private information Iu;
- a processing device receiving at least one session encryption key K encrypted with plural subset keys, the session key encrypting content, the processing device obtaining at least one subset key using the private information such that the session key K is decryptable to play the content, wherein the receiver is partitioned into one of a set of groups S1, . . . , Sw, wherein “w” is an integer greater than one, and the groups establish subtrees in a tree, wherein the tree includes a root and plural nodes, each node having at least one associated label, and wherein users that are not revoked are partitioned into subsets and further wherein each subset includes all leaves in a subtree rooted at some node vi except for leaves of a subtree rooted at some other node vj that descends from vi.
Dependencies are inferred from the claim text.