Method for broadcast encryption and key revocation of stateless receivers

• US 7,039,803 B2
• Filed: 01/26/2001
• Issued: 05/02/2006
• Est. Priority Date: 01/26/2001
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lotspiech, Jeffrey Bruce, Naor, Dalit, Naor, Simeon
• Primary Examiner(s): Caldwell, Andrew
• Assistant Examiner(s): NGUYEN, MINH DIEU T
• Application Number:
  US09/770,877
• Publication Number:
  US 20020147906A1
• Time in Patent Office: 1,922 Days
• Field of Search: 713162-163, 380/277, 380/279, 380/282, 380/239
• US Class Current: 713/163
• CPC Class Codes: G11B 20/0021 involving encryption or decryption of contents recorded on or reproduced from a record carrier
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 2209/605 Copy protection
• CPC Class Codes: H04L 2209/606 Traitor tracing
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 9/0836 using tree structure or hierarchical structure
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying

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.

Claims

1. A method for broadcast encryption, comprising:

assigning each user in a group of users respective private information I_u;

selecting at leas one session encryption key K;

partitioning use not in a revoked set R into disjoint subsets S_i1, . . . S_im having associated subset keys L_i1, . . . , L_im;

encrypting the session key K with the subset keys L_i1, . . . , L_im to render m encrypted versions of the session key K;

partitioning the users into groups S₁, . . . , S_w, wherein “

w”

is an integer, and the groups establish subtrees in a tree, wherein each subset S_i1, . . . S_im includes all leaves in a subtree rooted at some node v_i at least each node in the subtree being associated with a respective subset key, wherein content is provided to users in at least one message defining a header, and the header includes at most r*log(N/r) subset keys and encryptions, wherein r is the number of users in the revoked set R and N is the total number of users.

2. The method of claim 1, wherein the tree is a complete binary tree.

3. The method of claim 1, further comprising using private information I_u to decrypt the session key.

4. The method of claim 3, 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.

5. The method of claim 1, wherein each user must store log N keys, wherein N is the total number of users.

6. The method of claim 1, wherein the revoked set R defines a spanning tree, and subtrees having roots attache to nodes of the spanning tree define the subsets.

7. The method of claim 1, 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 v₁ that are not in the subtree rooted at some other node v_j that descends from v_i.

8. The method of claim 7, wherein each node has plural labels with each ancestor of the node inducing a respective label, and wherein each user is assigned labels from all nodes hanging from a direct path between the user and the root but not from nodes in the direct path.

9. The method of claim 1, wherein the tree includes a root and plural nodes, each node having an associated key, and wherein each user is assigned keys from all nodes in a direct path between a leaf representing the user and the root.

10. A method for broadcast encryption, 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_i1, . . . S_im having associated subset keys L_i1, . . . , L_im;

encrypting the session key K with the subset keys L_i1, . . . , L_im to render m encrypted versions of the session key K;

partitioning the users into groups S₁, . . . , S_w, wherein “

w”

is an integer, and the groups establish subtrees in a tree, wherein each subset S_i1, . . . S_im includes all leaves in a subtree rooted at some node v₁ at least each node in the subtree being associated with a respective subset key, wherein content is provided to users in at least one message, and wherein each user processes the message using at most log log N operations plus a single decryption operation, wherein N is the total number of users.

11. A method for broadcast encryption, 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_i1, . . . S_im having associated subset keys L_i1, . . . , L_im;

encrypting the session key K with the subset keys L_i1, . . . , L_im to render m encrypted versions of the session key K;

partitioning the users into groups S₁, . . . , S_w, wherein “

w”

is an integer, 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 each subset includes all leaves in a subtree rooted at some node v_i that are not in the subtree rooted some other node v_j that descends from v_i, wherein content is provided to users in at least one message defining a header, and the header includes at most 2r−

1 subset keys and encryptions, wherein r is the number of users in the revoked set R.

12. A method for broadcast encryption, 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_i1, . . . S_im having associated subset keys L_i1, . . . L_im;

encrypting the session key K with the subset keys L_i1, . . . , L_im to render m encrypted versions of the session key K;

partitioning the users into groups S₁, . . . , S_w, wherein “

w”

is an integer, 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 each subset includes all leaves in a subtree rooted at some node v_i that are not in the subtree rooted at some other node v_j that descends from v_i, wherein each user must store 0.5 log² N+0.5 log N+1 keys, wherein N is the total number of users.

13. A method for broadcast encryption, 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_i1, . . . S_im having associated subset keys L_i1, . . . L_im;

encrypting the session key K with the subset keys L_i1, . . . , L_im to render m encrypted versions of the session key K;

partitioning the users into groups S₁, . . . , S_w, wherein “

w”

is an integer, 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 each subset includes all leaves in a subtree rooted at some node v_i that are not in the subtree rooted some other node v_j that descends from v_i, wherein content is provided to users in at least one message, and wherein each user processes the message using at most log N operations plus a single decryption operation, wherein N is the total number of users.

14. A method for broadcast encryption, 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_i1, . . . S_im having associated subset keys L_i1, . . . L_im;

encrypting the session key K with the subset keys L_i1, . . . , L_im to render m encrypted versions of the session key K;

partitioning the users into groups S₁, . . . , S_w, wherein “

w”

is an integer, 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 each subset includes all leaves in a subtree rooted at some node v_i that are not in the subtree rooted some other node v_j that descends from v_i, wherein the revoked set R defines a spanning tree, and wherein the method includes;

initializing a cover tree T as the spanning tree;

iteratively removing nodes from the cover tree T and adding nodes to cover until the cover tree T has at most one node.

15. A method for broadcast encryption, 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_i1, . . . S_im having associated subset keys L_i1, . . . L_im;

encrypting the session key K with the subset keys L_i1, . . . , L_im to render m encrypted versions of the session key K;

partitioning the users into groups S₁, . . . , S_w, wherein “

w”

is an integer, 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 each subset includes all leaves in a subtree rooted at some node v_i that are not in the subtree rooted some other node v_j that descends from v_i, wherein each node has at least one label possibly induced by at least one of its ancestors, and wherein each user is assigned labels from all nodes hanging from a direct path between the user and the root but not from nodes in the direct path.

16. The method of claim 15, wherein labels are assigned to subsets using a pseudorandom sequence generator, and the act of decrypting includes evaluating the pseudorandom sequence generator.

17. A method for broadcast encryption, 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_i1, . . . S_im having associated subset keys L_i1, . . . L_im; and

encrypting the session key K with the subset keys L_i1, . . . , L_im to render m encrypted versions of the session key K, wherein content is provided to users in at least one message having a header including a cryptographic function E_L, and the method includes prefix-truncating the cryptographic function E_L.

18. A method for broadcast encryption, 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_i1, . . . S_im having associated subset keys L_i1, . . . L_im; and

encrypting the session key K with the subset keys L_i1, . . . , L_im to render m encrypted versions of the session key K, wherein content is provided to users in at least one message defining plural portions, and each portion is encrypted with a respective session key.

19. A computer program device, comprising:

a computer program storage device including a program of instructions usable by a computer, comprising;

logic means for accessing a tree to identify plural subset keys;

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;

logic means for sending the encrypted versions of the session key in header of the message to plural stateless receivers, wherein logic means provide content to receivers in at least one message, and wherein each receiver processes the message using at most log log N operations plus a single decryption operation, wherein N is the total number of receivers.

20. The computer program device of claim 19, further comprising:

logic means for partitioning receivers not in a revoked set R into disjoint subsets S_i1, . . . S_im having associated subset keys L_i1, . . . , L_im.

21. The computer program device of claim 20, further comprising logic means for partitioning the users into groups S₁, . . . , S_w, wherein “

w”

is an integer, and the groups establish subtrees in a tree.

22. The computer program device of claim 21, wherein each subset S_i1, . . . S_im includes all leaves in a subtree rooted at some node v_i, at least each node in the subtree being associated with a respective subset key.

23. The computer program device of claim 22, wherein each receiver must store log N keys, wherein N is the total number of receivers.

24. The computer program device of claim 22, wherein the revoked set R defines a spanning tree, and subtrees having roots attached to nodes of the spanning tree define the subsets.

25. The computer program device of claim 21, 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 v_i that are not in the subtree rooted at some other node v_j that descends from v_i.

26. The computer program device of claim 21, wherein the tree includes a root and plural nodes, each node having an associated key, and wherein logic means assign each receiver keys from all nodes in a direct path between a leaf representing the receiver and the root.

27. The computer program device of claim 19, further comprising logic means for using private information I_u to decrypt the session key.

28. The computer program device of claim 27, wherein the means for decrypting includes logic means for using information i_j such that a receiver belongs to a subset S_ij, and retrieving a key L_ij from the private information of the receiver.

29. A computer program device, comprising:

a computer program storage device including a program of instructions usable by a computer, comprising;

logic means for accessing a tree to identify plural subset keys;

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;

logic means for sending the encrypted versions of the session key in a header of the message to plural stateless receivers;

logic means for partitioning receivers not in a revoked set R into disjoint subsets S_i1, . . . S_im having associated subset keys L_i1, . . . , L_im;

logic means for partitioning the users into groups S₁, . . . , S_w, wherein “

w”

is an integer, 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 each subset includes all leaves in a subtree rooted at some node v_i that are not in the subtree rooted at some other node v_j that descends from v_i, wherein logic means provide content to receivers in at least one message defining a header, and the header includes at most 2r−

1 subset keys and encryptions, wherein r is the number of receivers in the revoked set R.

30. A computer program device, comprising:

a computer program storage device including a program of instructions usable by a computer, comprising;

logic means for accessing a tree to identify plural subset keys;

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;

logic means for sending the encrypted versions of the session key in a header of the message to plural stateless receivers;

logic means for partitioning receivers not in a revoked set R into disjoint subsets S_i1, . . . S_im having associated subset keys L_i1, . . . , L_im;

logic means for partitioning the users into groups S₁, . . . , S_w, wherein “

w”

is an integer, 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 each subset includes all leaves in a subtree rooted at some node v_i that are not in the subtree rooted at some other node v_j that descends from v_i, wherein each receiver must store 0.51 log² N+0.5 log N+1 keys, wherein N is the total number of receivers.

31. A computer program device, comprising:

a computer program storage device including a program of instructions usable by a computer, comprising;

logic means for accessing a tree to identify plural subset keys;

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;

logic means for sending the encrypted versions of the session key in a header of the message to plural stateless receivers;

logic means for partitioning receivers not in a revoked set R into disjoint subsets S_i1, . . . S_im having associated subset keys L_i1, . . . , L_im;

logic means for partitioning the users into groups S₁, . . . , S_w, wherein “

w”

is an integer, 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 each subset includes all leaves in a subtree rooted at some node v_i that are not in the subtree rooted at some other node v_j that descends from v_i, wherein logic means provide content to receivers in at least one message, and wherein each receiver processes the message using at most log N operations plus a single decryption operation, wherein N is the total number of receivers.

32. A computer program device, comprising:

a computer program storage device including a program of instructions usable by a computer, comprising;

logic means for accessing a tree to identify plural subset keys;

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;

logic means for sending the encrypted versions of the session key in a header of the message to plural stateless receivers;

logic means for partitioning receivers not in a revoked set R into disjoint subsets S_i1, . . . S_im having associated subset keys L_i1, . . . , L_im;

logic means for partitioning the users into groups S₁, . . . , S_w, wherein “

w”

is an integer, 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 each subset includes all leaves in a subtree rooted at some node v_i that are not in the subtree rooted at some other node v_j that descends from v_i, wherein the revoked set R defines a spanning tree, and wherein the computer program device includes;

logic means for initializing a cover tree T as the spanning tree; and

logic means for iteratively removing nodes from the cover tree T and adding nodes to a cover until the cover tree T has at most one node.

33. The computer program device of claim 32, wherein logic means assign labels to receivers using a pseudorandom sequence generator, and the labels induce subset keys.

34. The computer program device of claim 33, wherein the means for decrypting includes evaluating the pseudorandom sequence generator.

35. A computer program device, comprising:

a computer program storage device including a program of instructions usable by a computer, comprising;

logic means for accessing a tree to identify plural subset keys;

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, wherein logic means provide content to receivers in at least one message having a header including a cryptographic function E_L, and the computer program device includes logic means for prefix-truncating the cryptographic function E_L.

36. A computer program device, comprising:

a computer program storage device including a program of instructions usable by a computer, comprising;

logic means for accessing a tree to identify plural subset keys;

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, wherein logic means provide content to receivers in at least one message defining plural portions, and each portion is encrypted with a respective session key.

37. A computer programmed with instructions to cause the computer to execute method acts including:

encrypting broadcast content;

sending the broadcast content to plural stateless receivers and to at least one revoked receiver such that each stateless receiver can decrypt the content and the revoked receiver cannot decrypt the content;

partitioning the users into groups S₁, . . . , S_w, wherein “

w”

is an integer, and the groups establish subtrees in a tree, wherein each subset S_i1, . . . , S_im includes all leaves in a subtree rooted at some node v_i, at least each node in the subtree being associated with a respective subset key, wherein content is provided to receivers in at least one message defining a header, and the header includes at most r*log(N/r) subset keys and encryptions, where r is the number of receivers in the revoked set R and N is the total number of receivers.

38. The computer of claim 37, wherein the method acts further comprise:

assigning each receiver in a group of receivers respective private information I_u;

selecting at least one session encryption key K;

partitioning all receivers not in a revoked set R into disjoint subsets S_i1, . . . S_im having associated subset keys L_i1, . . . , L_im; and

encrypting the session key K with the subset keys L_i1, . . . , L_im to render m encrypted versions of the session key K.

39. The computer of claim 37, wherein the tree is a complete binary tree.

40. The computer of claim 37, wherein each receiver must store log N keys, wherein N is the total number of receivers.

41. The computer of claim 37, wherein the revoked set R defines a spanning tree, and subtrees having roots attached to nodes of the spanning tree define the subsets.

42. The computer of claim 41, 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 v_i that are not in the subtree rooted at some other node v_j that descends from V_i.

43. The computer of claim 42, wherein content is provided to receivers in at least one message defining a header, and the header includes at most 2r−

1 subset keys and encryptions, wherein r is the number of receivers in the revoked set R.

44. The computer of claim 42, wherein each receiver must store 0.51 log² N+0.5 log N+1 keys, wherein N is the total number of receivers.

45. The computer of claim 42, wherein content is provided to receivers in at least one message, and wherein each receiver processes the message using at most log N operations plus a single decryption operation, wherein N is the total number of receivers.

46. The computer of claim 42, wherein the revoked set R defines a spanning tree, and wherein the method acts undertaken by the computer further include:

initializing a cover tree T as the spanning tree;

iteratively removing nodes from the cover tree T and adding nodes to a cover until the cover tree T has at most one node.

47. The computer of claim 46, wherein the computer assigns node labels to receivers from the tree using a pseudorandom sequence generator.

48. The computer of claim 47, wherein the act of decrypting undertaken by the computer includes evaluating the pseudorandom sequence generator.

49. The computer of claim 37, wherein the act of partitioning is undertaken by a system computer in a system of receivers separate from the system computer.

50. The computer of claim 37, wherein the act of partitioning is undertaken by a receiver computer.

51. The computer of claim 37, wherein the method acts include using private information I_u to decrypt the session key.

52. A computer programmed with instructions to cause the computer to execute method acts including:

encrypting broadcast content;

partitioning users into groups S₁, . . . , S_w, wherein “

w”

is an integer, and the groups establish subtrees in a tree, wherein each subset S_i1, . . . , S_im includes all leaves in a subtree rooted at some node v_i, at least each node in the subtree being associated with a respective subset key;

sending the broadcast content to plural stateless receivers and to at least one revoked receiver such that each stateless receiver can decrypt the content and the revoked receiver cannot decrypt the content, wherein content is provided to receivers in at least one message, and wherein each receiver processes the message using at most log log N operations plus a single decryption operation, wherein N is the total number of receivers.

53. The computer of claim 52, wherein the act of decrypting undertaken by the computer includes using information i_j such that a receiver belongs to a subset S_ij, and retrieving a key L_ij using the private information of the receiver.

54. A computer programmed with instructions to cause the computer to execute method acts including:

encrypting broadcast content;

sending the broadcast content to plural stateless receivers and to at least one revoked receiver such that each stateless receiver can decrypt the content and the revoked receiver cannot decrypt the content, wherein content is provided to receivers in at least one message having a header including a cryptographic function E_L, and the method acts undertaken by the computer include prefix-truncating the cryptographic function E_L.

55. A computer programmed with instructions to cause the computer to execute method acts including:

encrypting broadcast content;

sending the broadcast content to plural stateless receivers and to at least one revoked receiver such that each stateless receiver can decrypt the content and the revoked receiver cannot decrypt the content, wherein content is provided to receivers in at least one message defining plural portions, and each portion is encrypted by the computer with a respective session key.

56. A receiver of content, comprising:

means for storing respective private information I_u;

means for receiving at least one session encryption key K encrypted with plural subset keys, the session key encrypting content; and

means for obtaining at least one subset key using the private information such that the session key K can be decrypted to play the content, wherein the receiver receives content in at least one message defining a header, and the header includes at most r*log(N/r) subset keys and encryptions, wherein r is the number of receivers in a revoked set R and N is the total number of receivers.

57. There receiver of claim 56, wherein the receiver is partitioned into one of a set of groups S₁, . . . , S_w, wherein “

w”

is an integer, and the groups establish subtrees in a tree defining nodes and leaves.

58. The receiver of claim 57, wherein subsets S_i1, . . . , S_im derived from the set of groups S₁, . . . , S_w define a cover.

59. There receiver of claim 58, wherein the receiver must store log N keys, wherein N is the total number of receivers.

60. The receiver of claim 58, wherein a revoked set R defines a spanning tree, and subtrees having roots attached to nodes of the spanning tree define the subsets.

61. The receiver of claim 58, 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 v_i that are not in the subtree rooted at some other node v_j that descends from v_i.

62. The receiver of claim 61, wherein the receiver decrypts the subset key by evaluating a pseudorandom sequence generator.

63. The receiver of claim 58, wherein the receiver derives the subsets in the cover.

64. A receiver of content, comprising:

means for storing respective private information I_u;

means for receiving at least one session encryption key K encrypted with plural subset keys, the session key encrypting content; and

means for obtaining at least one subset key using the private information such that the session key K can be decrypted to play the content, wherein the receiver receives content in at least one message defining a header, and wherein the receiver processes the message using at most log log N operations plus a single decryption operation, wherein N is the total number of receivers.

65. A receiver of content, comprising:

means for storing respective private information I_u;

means for receiving at least one session encryption key K encrypted with plural subset keys, the session key encrypting content; and

means for obtaining at least one subset key using the private information such that the session key K can be decrypted to play the content, wherein the receiver receives content in message having a header including at most 2r−

1 subset keys and encryptions, wherein r is the number of receivers in the revoked set R.

66. A receiver of content, comprising:

means for storing respective private information I_u;

means for receiving at least one session encryption key K encrypted with plural subset keys, the session key encrypting content; and

means for obtaining at least one subset key using the private information such that the session key K can be decrypted to play the content, wherein the receiver must store 0.5 log² N+0.5 log N+1 keys, wherein N is the total number of receivers.

67. A receiver of content, comprising:

means for storm respective private information I_u;

means for receiving at least one session encryption key K encrypted with plural subset keys, the session key encrypting content; and

means for obtaining at least one subset key using the private information such that the session key K can be decrypted to play the content, wherein content is provided to the receiver in at least one message, and wherein the receiver processes the message using at most log N operation plus a single decryption operation, wherein N is the total number of receivers.

68. A receiver of content, comprising:

a data storage storing respective private information I_u;

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 at the session key K can be decrypted to play the content, wherein the receiver receives content in at least one message defining a header, and wherein the receiver processes the message using at most log log N operations plus a single decryption operation, wherein N is the total number of receivers.

69. The receiver of claim 68, wherein the receiver is partitioned into one of a set of groups S₁, . . . , S_w, wherein “

w”

is an integer, and the groups establish subtrees in a tree.

70. The receiver of claim 69, wherein subsets S_i1, . . . , S_im derived from the set of groups S₁, . . . , S_w define a cover.

71. The receiver of claim 70, wherein the receiver receives content in at least one message defining a header, and the header includes at most r*log(N/r) subset keys and encryptions, wherein r is the number of receivers in a revoked set R and N is the total number of receivers.

72. The receiver of claim 70, wherein the receiver must store log N keys, wherein N is the total number of receivers.

73. The receiver of claim 70, wherein one revoked set R defines a spanning tree, and subtrees having roots attached to nodes of the spanning tree define the subsets.

74. The receiver of claim 70, 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 v_i that are not in the subtree rooted at some other node v_j that descends from v_i.

75. The receiver of claim 74, wherein the receiver receives content in a message having a header including at most 2r−

1 subset keys and encryptions, wherein r is the number of receivers in the revoked set R.

76. The receiver of claim 74, wherein the receiver must store 0.5 log² N+0.5 log N+1 keys, wherein N is the total number of receivers.

77. The receiver of claim 74, wherein content is provided to the receiver in at least one message, and wherein the receiver processes the message using at most log N operations plus a single decryption operation, wherein N is the total number of receivers.

78. The receiver of claim 74, wherein the receiver decrypts the subset key by evaluating a pseudorandom sequence generator.