Method for tracing traitor receivers in a broadcast encryption system

• US 20020133701A1
• Filed: 01/26/2001
• Published: 09/19/2002
• Est. Priority Date: 01/26/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lotspiech, Jeffrey Bruce, Naor, Dalit, Naor, Simeon
• Granted Patent: US 7,010,125 B2
• Time in Patent Office: Days
• US Class Current: 713/163
• CPC Class Codes: G11B 20/00086 Circuits for prevention of unauthorised reproduction or copying, e.g. piracy indicating unauthorised use of record carriers in general G11B23/28; scrambling for television signal recording H04N5/913; network architectures or network protocols for network security H04L63/00; cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
• CPC Class Codes: G11B 20/0021 involving encryption or decryption of contents recorded on or reproduced from a record carrier
• CPC Class Codes: G11B 20/00224 wherein the key is obtained from a remote server
• CPC Class Codes: G11B 20/00246 wherein the key is obtained from a local device, e.g. device key initially stored by the player or by the recorder
• CPC Class Codes: G11B 20/00253 wherein the key is stored on the record carrier
• CPC Class Codes: G11B 20/00492 wherein content or user data is encrypted
• CPC Class Codes: G11B 2220/2537 Optical discs
• CPC Class Codes: H04L 2209/601 Broadcast encryption
• CPC Class Codes: H04L 2209/606 Traitor tracing
• 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
• CPC Class Codes: H04N 21/26606 for generating or managing entitlement messages, e.g. Entitlement Control Message [ECM] or Entitlement Management Message [EMM] arrangements for conditional access to broadcast information or to broadcast-related services H04H60/14
• CPC Class Codes: H04N 21/4181 for conditional access
• CPC Class Codes: H04N 21/4331 Caching operations, e.g. of an advertisement for later insertion during playback
• CPC Class Codes: H04N 21/4623 Processing of entitlement messages, e.g. ECM [Entitlement Control Message] or EMM [Entitlement Management Message] arrangements for conditional access to broadcast information or to broadcast-related services H04H60/14
• CPC Class Codes: H04N 7/1675 Providing digital key or authorisation information for generation or regeneration of the scrambling sequence pseudo-random number generators in general G06F7/58

Abstract

A method for tracing traitor receivers in a broadcast encryption system. The method includes using a false key to encode plural subsets representing receivers in the system. The subsets are derived from a tree using a Subset-Cover system, and the traitor receiver is associated with one or more compromised keys that have been obtained by a potentially cloned pirate receiver. Using a clone of the pirate receiver, the identity of the traitor receiver is determined, or the pirate receiver clones are rendered useless for decrypting data using the compromised key by generating an appropriate set of subsets.

Claims

1. A method for identifying or disabling at least one traitor receiver with at least one associated unique, compromised decryption key in a broadcast encryption system, comprising:

receiving a set of subsets derived from a tree defining leaves, each leaf representing a respective receiver;

identifying at least one traitor subset from the set of subsets as containing at least one leaf representing a traitor receiver; and

using the traitor subset, identifying or disabling the traitor receiver.

2. The method of claim 1, further comprising:

determining whether the traitor subset represents at least one traitor receiver, and if so, dividing the traitor subset into two child sets.

3. The method of claim 2, further comprising determining whether the traitor subset is a member of a frontier set, and if so, removing a complementary subset from the frontier set.

4. The method of claim 1, wherein the act of identifying or disabling includes encoding plural subsets of the set of subsets with a false key.

5. The method of claim 4, further comprising executing a binary search on the set of subsets using probabilities.

6. The method of claim 5, wherein the binary search ends by determining that the difference between a probability p_j of decrypting a message when the first j subsets contain the false key and a probability p_j−

1 of decrypting a message when the first j−

1 subsets contain the false key is at least equal to a predetermined probability.

7. The method of claim 6, wherein the traitor subset is identified when |p_j−

1−

p_j|>

p/m, wherein m is the number of subsets in the set of subsets.

8. The method of claim 1, wherein the set of subsets is generated by:

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

selecting at least one session encryption key K;

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

encrypting the session key K and the false key with the subset keys L_i1, . . . , L_im.

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

10. The method of claim 8, wherein the tree includes a root and plural nodes, each node associated with a set of labels, and wherein each receiver is assigned labels from all nodes hanging from a direct path between the receiver and the root but not from nodes in the direct path.

11. The method of claim 10, 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 the cover tree T until the cover tree T has at most one node.

13. The computer program device of claim 12, further comprising:

logic means for determining whether the traitor subset represents at least one traitor device, and if so, dividing the traitor subset into two child sets.

14. The computer program device of claim 13, further comprising logic means for determining whether the traitor subset is a member of a frontier set, and if so, removing a complementary subset from the frontier set.

15. The computer program device of claim 12, further comprising logic means for executing a binary search on the set of subsets using probabilities.

16. The computer program device of claim 15, wherein the binary search ends by determining that the difference between a probability p_j of decrypting a message when the first j subsets contain the false key and a probability p_j−

1 of decrypting a message when the first j−

1 subsets contain the false key is at least equal to a predetermined probability.

17. The computer program device of claim 16, wherein the traitor subset is identified when |p_j−

1−

p_j|>

p/m, wherein m is the number of subsets in the set of subsets.

18. The method of claim 12, wherein the set of subsets is generated by logic means including:

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

logic means for selecting at least one session encryption key K;

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

logic means for encrypting the session key K and the false key with the subset keys L_i1, . . . , L_im.

19. The computer program device of claim 18, wherein the tree includes a root and plural nodes, each node having an associated key, and wherein each receiver is assigned keys from all nodes hanging from a direct path between the receiver and the root but not from nodes in the direct path.

29. The method of claim 1, further comprising identifying or disabling plural traitor receivers embodied in a clone.

30. The method of claim 1, wherein the act of identifying or disabling includes encoding the first j subsets of the set of subsets with a false key.

12. 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 generate a set of subsets of the tree, the tree including leaves representing at least one traitor device characterized by a compromised key;

logic means for encrypting a false key j times and for encrypting a session key m-j times, wherein m is a number of subsets in the set of subsets;

logic means responsive to the means for encrypting for identifying a traitor subset; and

logic means for using the traitor subset to identify or disable the traitor device.

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

using a false key to encode plural subsets representing stateless receivers, at least one traitor receiver of which is associated with at least one compromised key that has been obtained by at least one pirate receiver; and

using the pirate receiver or a clone thereof, determining the identity of the traitor receiver, or rendering the pirate receiver or clone thereof useless for decrypting data using the compromised key.

21. The computer of claim 20, wherein the subsets define a set of subsets, and the method acts undertaken by the computer further include:

receiving the set of subsets derived from a tree defining leaves, each leaf representing a respective receiver;

identifying at least one traitor subset from the set of subsets as containing at least one leaf representing the traitor receiver; and

using the traitor subset, identifying the traitor receiver.

22. The computer of claim 21, wherein the method acts undertaken by the computer further comprise:

determining whether the traitor subset represents at least one traitor receiver, and if so, dividing the traitor subset into two child sets.

23. The computer of claim 22, wherein the method acts undertaken by the computer further comprise determining whether the traitor subset is a member of a frontier set, and if so, removing a complementary subset from the frontier set.

24. The computer of claim 21, wherein the act of identifying includes:

encoding plural subsets of the set of subsets with the false key.

25. The computer of claim 24, wherein the method acts undertaken by the computer further comprise executing a binary search on the set of subsets using probabilities.

26. The computer of claim 25, wherein the binary search ends by determining that a probability p_j of decrypting a message when the first j subsets contain the false key is at least equal to a predetermined probability.

27. The computer of claim 26, wherein the traitor subset is identified when |p_j−

1−

p_j|>

p/m, wherein m is the number of subsets in the set of subsets.

28. The computer of claim 21, wherein the set of subsets is generated by:

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

selecting at least one session encryption key K;

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

encrypting the session key K and the false key with the subset keys L_i1, . . . , L_im, herein the tree includes a root and plural nodes, each node being associated with a set of labels, and wherein each receiver is assigned labels from all nodes hanging from a direct path between the receiver and the root but not from nodes in the direct path.