HK1068513B - Method for tracing traitor receivers in a broadcast encryption system - Google Patents

Description

Method for tracing traitor receivers in a broadcast encryption system

Background

1. Field of the invention

The present invention relates to broadcast data encryption using an encryption key.

2. Description of the related Art

Various broadcast encryption systems have been proposed to encrypt content, which is broadcast to potentially millions of receivers using recording media such as CDs and DVDs or by wireless broadcast methods such as satellite broadcast. These systems are used to encrypt content so that only authorized receivers (also referred to as "users" and "players-recorders") can decode and play the content, but software-or hardware-implemented pirate devices (also referred to as "maskers" or "malicious devices") that somehow try to obtain a valid decryption key from an authorized device (a "traitor").

An example of such a system is disclosed in U.S. patent No. 6,118,873, assigned to the present assignee, which is hereby incorporated by reference. As described in this patent, only authorized playback machines can play and/or copy content, and only according to rules established by the content vendor. In this way pirated copies of content can be prevented, with billions of dollars being lost annually by content providers today.

Another example of a broadcast encryption system is the "subset cover" system disclosed in copending U.S. patent application serial No. arc9200100_ US, assigned to the present assignee, which is incorporated herein by reference. Such a system, which will be described in detail below, is directed to the difficult case of "stateless" receivers that do not necessarily update their encryption state between broadcasts to accept countermeasures against pirated devices. For example, a pay channel television may have its set-top box switched off for a period of time during which updated encrypted data is broadcast over the system. If such a device were to fail to update itself after being switched off, the device would be considered "stateless" and would not be able to receive the update data needed for later content decryption. Another example of a stateless receiver is a CD and DVD player-recorder, which usually does not interact with other system components, and which will not receive every possible encrypted data update, since no player receives every disc sold.

As known to those skilled in the art, the decryption key in a broadcast encryption system may be compromised so that unauthorized pirate devices can decrypt the content. Such pirated devices can be implemented in hardware or software, and in the case of software can be distributed over the internet for arbitrary download to anyone who wants to obtain proprietary content without paying for it. In any case, the invention aims to suppress the spread of pirate counterfeiters by looking for the identity of the system receiver ("traitor") that those keys have been obtained by the pirate, or by finding an encryption that cannot be decrypted by the counterfeiters but can be decrypted by authorized users, thus rendering the pirate counterfeiters useless.

The present invention is particularly, but not exclusively, directed to the problem of tracing traitors in a subset-cover system. Unlike the system described in the above-referenced' 873 patent, there is no overlap of keys between devices in the subset-cover system. One result of key overlap is that in the system of the' 873 patent the following scenario is perfectly normal in operation: some device keys will decrypt the content correctly and some device keys will not, so a masquerade cannot determine whether it is being tested simply by monitoring whether a message sent to it cannot be decrypted with all of its keys. This is not the case in a subset-cover system, since each device has at least one unique key. Thus, a masker can conclude that it is being tested if it obtains keys from multiple traitors, and if the key obtained from one traitor correctly decrypts the content, while other keys obtained from other traitors cannot.

Once a masker concludes that it is being tested, it may take any of a variety of countermeasures, such as switching identities between traitors, or even self-destruction. Of course, in the case of self-destruction, the privileged agent can simply obtain yet another masquerade machine for further (altered) testing, but this takes time. In view of these drawbacks, a preferred embodiment of the present invention proposes the following solution to one or more of the drawbacks.

Summary of The Invention

First aspect the present invention accordingly proposes a method for identifying or disabling at least one traitor receiver having at least one associated unique, compromised decryption key in a broadcast encryption system, the method comprising: receiving a subset set derived from a tree defining leaves, each leaf representing a respective receiver; identifying at least one traitor subset from the set of subsets if it contains at least one blade representing a traitor receiver; and identifying or disabling the traitor receivers using the subset of traitors, wherein the identifying or disabling step includes encoding the plurality of subsets in the set of subsets with a dummy key.

The method as the first aspect of the present invention may further comprise: determining whether the traitor subset represents at least one traitor receiver, and if so, partitioning the traitor subset into two subsets.

The method as the first aspect of the present invention may further comprise: determining whether the traitor subset is a member of a boundary set, and if so, removing a complementary subset from the boundary set.

The method as the first aspect of the present invention may further comprise: a binary search over the set of subsets is performed using the probabilities.

Suitably, the binary search is terminated by determining that the difference between two probabilities, one of which is the probability P of decrypting a message when the current j subsets contain false keys, is at least equal to a predetermined probability_jThe other is the probability P of decrypting a message if the first j-1 subset contains a false key_j-1。

This is appropriate when | P_j-1-P_jIdentification of traitors > P/mSubsets, where m is the number of subsets in the set of subsets.

This is appropriate, and the subset set is generated by: respective personal information I assigned to each receiver of a group of receivers_u(ii) a Selecting at least one session encryption key K; partitioning receivers not in the discarded set R into a set of disjoint subsets S_i1，…，S_imThey have an associated subset key L_i1，…，L_im(ii) a And using the subset key L_i1，…，L_imThe session key K and the dummy key are encrypted.

This is suitable where the tree comprises a root and a plurality of nodes, each node having an associated key, and where each receiver is assigned a key from all nodes in the direct path between the leaf representing the receiver and the root.

This is suitable where the tree comprises a root and a plurality of nodes, each node corresponding to a set of labels, and where each receiver is assigned labels from all nodes hanging on the direct path between the receiver and the root, and not from nodes in the direct path.

This is suitable, the revoked set R defining a spanning tree, wherein the method comprises: initializing a covering tree T as a spanning tree; the nodes are repeatedly removed from and added to the coverage tree T until the coverage tree T has at most one node.

The method as a first aspect of the invention may comprise identifying or disabling a plurality of traitor receivers included in one pseudolite.

Where appropriate, the identifying or disabling step includes encoding the first j subsets of the set of subsets with a dummy key.

The present invention may suitably provide a computer program device comprising: a computer program storage device embodying a program of instructions useable by a computer, the program comprising: logic 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 for encrypting a dummy key j times and for encrypting a session key m-j times, where m is the number of subsets in the set of subsets; logic for identifying a traitor subset in response to the encryption logic; and logic for employing the subset of traitors to identify or disable the traitor device.

Further preferred features of the computer program device may comprise logic for causing a computing system to carry out the steps of the preferred method according to the preferred features of the first aspect of the invention.

In a second aspect, the present invention provides a computer program comprising computer program code to, when loaded into a computing system and executed, cause the computing system to perform the method steps of the first aspect of the invention.

The optimization feature of the second aspect of the invention comprises computer program code which causes a computing system to implement the preferred steps of the method according to the optimization feature of the first aspect of the invention.

The invention may further provide a computer programmed with instructions to cause the computer to perform method steps comprising: encoding subsets representing stateless receivers with a dummy key, at least one traitor receiver of the receivers having associated with at least one compromised key, the key having been obtained by at least one pirate receiver; and determining the identity of the traitor receiver with the pirate receiver or one of its counterfeiters, or rendering the pirate receiver or its counterfeiters incapable of decrypting the data with the compromised key.

Suitably, the plurality of subsets defines a set of subsets, and the computer-implemented method steps further comprise: receiving a subset set derived from a tree defining leaves, each leaf representing a respective receiver; identifying at least one traitor subset from the set of subsets if it contains at least one blade representing a traitor receiver; and applying the subset of traitors to identify traitor receivers.

Suitably, the computer-implemented method steps further comprise: determining whether the traitor subset represents at least one traitor receiver, and if so, partitioning the traitor subset into two subsets.

Suitably, the computer-implemented method steps further comprise: determining whether the traitor subset is a member of a boundary set, and if so, removing a complementary subset from the boundary set.

This is suitable, the identifying step comprising: a plurality of subsets of the set of subsets are encoded with a dummy key.

Suitably, the computer-implemented method steps further comprise: a binary search over the set of subsets is performed using the probabilities.

This is suitably done by determining the probability P of decrypting a message when the current j subsets contain false keys_jAt least equal to a predetermined probability.

This is appropriate when | P_j-1-P_jIf | P/m, where m is the number of subsets in the set of subsets.

This is appropriate, and the subset set is generated by: respective personal information I assigned to each receiver of a group of receivers_u(ii) a Selecting at least one session encryption key K; partitioning receivers not in the discarded set R into a set of disjoint subsets S_i1，…，S_imThey have an associated subset key L_i1，…，L_im(ii) a And using the subset key L_i1，…，L_imEncrypting the session key K and the dummy key, wherein the tree comprises a root and a plurality of nodes, each node corresponding to a set of labels, and wherein each receiver is assigned labels from all nodes hanging on a direct path between the receiver and the root, and not from nodes in the direct path.

The invention accordingly comprises a computer system for implementing the inventive logic described. The present invention may be implemented as a computer program product that stores the logic and that is accessible by a processor to execute the logic. The present invention is therefore a computer-implemented method that performs the following logical operations.

The computer is suitably programmed to encode the plurality of subsets representing stateless receivers with a dummy key. At least one traitor receiver in the system is associated with a compromised key that has been obtained by a counterfeit pirate receiver. The computer determines the identity of the traitor receiver using a pirate receiver's counterfeiter, or renders the pirate receiver's counterfeiter incapable of data decryption with the compromised key by generating an appropriate encryption policy.

In another aspect, a preferred method is disclosed for identifying a traitor receiver in a broadcast encryption system having an associated unique, compromised decryption key. The method comprises the following steps: a set of subsets derived from a tree defining leaves, each leaf representing a respective receiver, is received. The method further includes identifying a subset of traitors from the set of subsets and identifying traitor receivers with the subset of traitors if at least one traitor receiver is included.

In a preferred embodiment, the method comprises: determining whether the traitor subset represents one or more traitor receivers, and if so, partitioning the traitor subset into two subsets, and identifying a new traitor subset with the two subsets. The preferred method further includes determining whether the traitor subset is a member of a set of boundaries, and if so, removing a complementary subset from the set of boundaries.

A preferred method of identifying a traitor subset comprises: the first j subsets of the subset set are encoded with a dummy key and then a binary search over the subset set is performed with probabilities. The binary search is terminated by determining that the difference between two probabilities, one of which is the probability P of decrypting a message when the current j subsets contain false keys, is at least equal to a predetermined probability_jAnd the other is the first j-1Probability of decryption P when a subset contains a false key_j-1. Particularly, when | P_j-1-P_jIf | P/m, where m is the number of subsets in the set of subsets. The subset set is generated by a subset-covering scheme having the property of generating subsets that can be bifurcated.

In another aspect, a computer program device comprises: 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 are provided for encrypting a dummy key j times and for encrypting a session key m-j times, where m is the number of subsets in the set of subsets. The logic means is also for identifying a traitor subset in response to the encryption logic means. Further, the logic device identifies the traitor devices with a subset of traitors.

Brief Description of Drawings

Preferred embodiments of the invention will now be described, by way of example only, with reference to the accompanying drawings, in which:

FIG. 1 is a block diagram of the system of the present invention;

FIG. 2 is a flow diagram of the overall encryption logic;

FIG. 3 is a flow diagram of the overall decryption logic;

FIG. 4 is a partial flow diagram of the key assignment portion of the complete subtree method;

FIG. 5 is a flow diagram of the encryption portion of the complete subtree method;

FIG. 6 is a flow diagram of the decryption portion of the complete subtree method;

FIG. 7 is a schematic illustration of a subset of a complete subtree;

FIG. 8 is a schematic diagram of a subset in a subset difference method;

FIG. 9 is another form of a subset schematic in the subset difference method;

FIG. 10 is a logic flow diagram for determining a coverage in a subset difference method;

FIG. 11 is a schematic diagram of a subset of a tree illustrating key assignment in the subset differencing approach;

FIG. 12 is a flow chart of the decryption portion of the subset difference method;

FIG. 13 is a logic flow diagram for assigning keys in a subset differencing method;

FIG. 14 is a diagram of a subset of a tree in the subset difference method;

FIG. 15 is a flow chart showing the tracking logic of the present invention, an

FIG. 16 is a flow diagram of a subset tracking module representing tracking logic.

Description of The Preferred Embodiment

A preferred embodiment of the present invention may be used with any broadcast encryption method. By way of non-limiting example, one such system, the subset cover system, is first described, and then the tracking algorithm of the present invention is described in terms of the subset cover system.

Referring first to fig. 1, there is shown a system 10 for generating a key set in a broadcast content protection system, such as, but not limited to, the system disclosed in the above-referenced patent. The term "broadcast" means the widespread distribution of programming from one content provider to many users simultaneously over cable (from a satellite source), or wire, or radio frequency (including from a satellite source), or from widely sold content discs.

As shown, the system 10 includes a key set determination computer 12 that accesses a key set determination module 14, the function of which is described below. The set of keys determined by computer 12 is applied by a potentially stateless play-and-play device 16, also referred to as a "receiver" and a "user", having a processor therein for decrypting the content. The content is provided to the respective device on the medium 17, for example by the device manufacturer 16, together with some keys as will be explained below. A player-recorder can access its key set to decrypt the content on the medium or broadcast to it via wireless communication. "media" as used herein may include, but is not limited to, DVDs, CDs, hard drives and flash memory devices. In another embodiment, each receiver 16 can manipulate the module 14 to perform the step of calculating the "coverage" described below by giving a set of revoked receivers and implementing the logic described below.

It will be appreciated that the processor associated with module 14 accesses the module to implement the logic shown and discussed below, which may be executed by the processor as a sequence of computer-executable instructions. Two methods are presented below-a full subtree method and a subset differencing method-to apply the system 10 to selectively revoke the ability of compromised key receivers 16 to decrypt broadcast content without revoking the ability of any compromised key receivers 16 to decrypt broadcast content.

The instructions may be provided on a data storage device having a computer-readable medium, such as a computer diskette, having a computer usable medium with computer readable code means stored therein. Or the instructions may be stored on a DASD array, magnetic tape, conventional hard disk drive, electronic read-only memory, optical storage device, or other suitable data storage device. In the illustrated embodiment of the invention, the computer-executable instructions may be lines of compiled C⁺⁺And (4) compatible codes.

Indeed, the flow charts reflect the logical structures of preferred embodiments of the present invention as implemented in computer program software. Those skilled in the art will appreciate that the flow charts illustrate the structures of computer program code elements including logic circuits on an integrated circuit, which operate according to the present invention. It is clear that the invention is implemented in its basic embodiment by a machine component implementing the program code means in the form of instructions to a digital processing apparatus, i.e. a computer, to perform a series of functional operations corresponding to the program code means.

FIG. 2 illustrates the overall logic of a preferred embodiment of the present invention when implemented in both the subset difference method and the full subtree method. For purposes of illustration, it is assumed that there are N receivers 16 in the system 10 and that the ability to revoke R receivers in a revoked receiver subset R to decrypt content is required, even if the revoked receivers are within a union (by sharing the knowledge of decryption), while other receivers can still decrypt the content. Beginning at block 19, the system begins by aggregating S a subset₁，…S_wIs assigned a long-life subset key L₁，…，L_wIn the subset set, the receivers are grouped according to the following method, each subset S_jHaving a long-life subset key L associated with it_j. In the first ("complete subtree") method, the subset covering receivers not in the revoked set is a simple subtree, which results from the following method. In a second ("subset difference") approach, the subset covering receivers not in the revoked set is defined by the difference between the first subtree and a smaller subtree, which is entirely within the first subtree, as described below.

At block 20, the system further initializes: providing each receiver u with personal information I_uIt is useful for decrypting content. Personal information I_uThe details of which are further described below. If I_uIs secret information provided to receiver u, at S_jCan be determined by its I_uPush out L_j. As explained more fully below, given a revoked set R, a non-revoked receiver is partitioned into m disjoint subsets S_i1，…，S_imAnd a short-lived session key K using the corresponding subset S_i1，…，S_imAssociated long lifetime subset key L_i1，…L_imAnd (5) encrypting for m times. In the complete subtree approachThe set key is an explicit subset key, whereas in the subset difference method the subset key is derived from the subset flag.

In particular, at block 22 at least one session key K is selected for encrypting the content broadcast in a message M, the broadcast being effected via a wireless or wired communication line or via a storage medium such as a CD or DVD. The session key K is a random bit string that is reselected for each message. If desired, multiple session keys may be used to encrypt portions of message M.

In both methods described below, the non-revoked receivers are partitioned into disjoint subsets S at block 24 using a tree_i1，…，S_im. Sometimes referred to herein as a subset, a sub-tree, which is considered directly in the first approach and in the second approach to this form: "first subtree minus a second subtree that is completely contained in the first subtree". Each subset S_i1，…，S_imIs associated with a corresponding subset key L_i1，…，L_im. When considering any data tree structure, for purposes of illustration, it is assumed that the tree is a full bifurcate tree.

Turning now to block 26, the session key K is typically encrypted m times, one subset key L at a time_i1，…，L_im. The derived broadcast ciphertext may be represented as follows:

<[i₁，i₂，…，i_m，E_Li1(k)，E_Li2(K)，…，E_Lim(k)]，F_K(M)>wherein the part between brackets represents the header of the message M, and i₁，i₂，…，i_mIndicating the number of disjoint subsets.

In one embodiment, the cryptographic primitive F_KBy xoring the message M with a string of ciphers generated by the session key K. Encryption element E_LIs a method of delivering the session key K to the receiver 16 using a long-lived subset key. It can be understood that for F_K，E_LAll encryption algorithms of (a) are within the scope of the present invention. E_LA preferred implementation of (a) may be a prefix-truncation specification of a block cipher. Let l denote a length equal to E_LAnd assuming K is for a cipher F of length, for example 56 bits_KA short key of (2). Thus [ Prefix_-k-E_L(1)/K]A strong encryption is provided. Thus, the prefix-truncation header becomes

<[i₁，i₂，…，i_m，U，[Prefix_-k-E_Li1(U)]/K，…，[Prefix_-k-E_Lim(U)]/K]，F_K(M)>

This advantageously reduces the length of the header to about m-K-bits instead of m-L-bits. At E_LThe following method can be used to exclude the factor m in the case of very small key lengths, with the advantage that the adversary must make a strong attack, which results from encrypting the same string 1 with m different keys. String 1/i_jIs encrypted. Namely, it is

<[i₁，i₂，…，i_m，U，[Prefix_-L-E_Li1(U/i₁)]/K，…，[Prefix_-L-E_Lim(U/i_m)]/K]，F_K(M)>

Having described the preferred, non-limiting method by which the cryptographic primitives E and F are accomplished, attention is now directed to fig. 3, which illustrates the decryption logic performed by the receiver 16. Beginning in block 28, each non-revoked receiver u finds a subset tag i in the ciphertext_jIt belongs to the subset S_ij. As will be explained further below, the result of block 28 will be "null" if the receiver is in the revoked set R. Next, the receiver uses its personal information I at block 30_uThe extraction corresponds to the subset S_ijIs given by the subset key L_ij. With this subset key, the session key is determined at block 32, and the message is then decrypted with the session key at block 34.

A preferred method for implementing the entire logic described above is described below. In each method a set of subsets is determined, a method specifying that keys are assigned to the subsets and a method covering non-revoked receivers with disjoint subsets of the set. In each method the set of receivers in the system builds a leaf of a tree, such as but not limited to a full bifurcate tree.

The first method discussed is the complete subtree approach shown in fig. 4 to 7. Beginning at block 36 of FIG. 4, an independent and random subset key L_iIs assigned to each node V in the tree_i. This subset key L_iCorresponding to the node V_iA subset of all the blades. Each receiver u is then provided with all subset keys in the direct path from the receiver to the root at block 38. As shown briefly in fig. 7, in subset S_iIs provided with a node V_iAssociated subset key L_iAnd a key associated with a node P, the node P being located at S_iBetween the receiver in (1) and the root of the tree.

If a message is to be sent and some receivers are disabled from decrypting the message, the logic of fig. 5 is invoked to partition non-revoked receivers into disjoint subsets. Proceeding from block 40, a spanning tree is found which is determined by the leaves in the revoked receiver set R. The spanning tree is the smallest sub-tree of a full bifurcate tree, it connects "revoked" leaves, and it can be a Steiner tree. At block 42, those subtrees in the tree having roots adjacent to first-order nodes (i.e., nodes immediately adjacent to the minimum tree) are determined. These subtrees define a "cover" and establish a subset S_i1，…，S_im. The coverage contains all non-revoked receivers. Accordingly, the session key K is encrypted at block 44 with the subset key determined by the overlay.

To decrypt the message, each receiver invokes the logic shown in fig. 6. From block 46, by determining whether any source originating node is in the set i in the header of the message₁，i₂，…，i_mTo determine receptionWhether any of the source start nodes of the machine is associated with a subset key of the overlay. Personal information I of receiver_uIn the full subtree method it includes its position in the tree and the subset key associated with the source start node-is used to determine this. If a source originating node is found in the header (indicating that the receiver is a non-revoked receiver), the session key K is decrypted with the subset key in block 48, and then the message is decrypted with the session key in block 50.

In the full subtree approach, the header contains at most r × log (N/r) subset keys and encryption. This is also the average of the key and encryption. Furthermore, each receiver must store logN keys, and each receiver processes messages with at most log logN operations plus a single decryption operation.

The method of differencing subsets of revoked receivers is now described with reference to fig. 8-13. In the subset difference method, each receiver must store more keys (0.5 log) than the full subtree method²N +0.5logN +1 keys), but the header only contains at most 2r-1 subset keys and encryptions (1.25 r on average), and this is significantly shorter than the full sub-tree approach. In the subset difference method, a message is processed by at most logN operations of a pseudorandom number generator plus a single decryption operation.

As shown in fig. 8 and 9, the subset difference method assumes that the subset is the difference between a larger subset a and a smaller subset B that is fully contained in a. Accordingly, as shown, a larger subset is rooted at node V_iWhere the root of a smaller subset is at node V_jAt node V_jIs a slave node V_iAnd (4) generating. Derived subset S_ijComprising V_iBelow except for V_jAll leaves except those marked "no" are "yes" (the leaves marked "no" are darker in the figure than the leaves marked "yes"). Fig. 9 illustrates this as follows: subset V_i，jRepresented as regions inside the large triangle and outside the small triangle.

In the subset differencing approach, if a message is to be sent and the ability of some receivers to decrypt the message is to be revoked, the above structure is applied as shown in fig. 10. Proceeding from block 52, a spanning tree is found, which is determined by the leaves in the set R of revoked receivers. The spanning tree is the smallest sub-tree of the full bifurcate tree connecting the "revoked" leaves, which may be a Steiner tree. At block 54, a coverage tree T is initialized as a spanning tree. An iterative loop is then started in which nodes are removed from the overlay tree and subtrees are added to the overlay until the overlay tree has at most one node. The output determines coverage to non-revoked receivers.

In particular, moving from block 54 to block 56, the leaf V is found in the coverage tree T_iAnd V_jWherein their smallest common source origin node V does not contain other leaves in T. A determination is made at decision diamond 57 as to whether there is only one leaf in the overlay tree T. If more than one leaf exists, the logic proceeds to block 58 to find node V in V_l，V_KSo that V is_iFrom V_lIs generated out of_jFrom V_KIs generated out of, and V_l，V_kIs the next generation of V (i.e. generated directly from V, at V and V_l，V_kWithout any intermediate nodes in between). Conversely, if only a single leaf exists in T, the logic moves from decision diamond 57 to block 60, where V is set_i＝V_jRoot with V as T, left as the only leaf, juxtaposition V_l＝V_KRoot of Longtube Bethlehem.

From either block 58 or 60, the logic passes to decision diamond 62. At decision diamond 62, decision V_lWhether or not it is equal to V_i。V_KWhether or not it is equal to V_jAnd is also determined. If V_lIs not equal to V_iThen the logic moves to block 64 to add the subset S_i，IBy T, all descendants of V are removed from T and V is made a leaf. Likewise, if V_KIs not equal to V_jThe logic moves to block 64 to add the subset S_k，jIn T, all descendants of V are eliminated from T and V is a leaf. The logic loops back from block 64 or from decision diamond 62 if it is determined that there is no inequalityAnd block 56.

With the above overview of the subset differential key assignment method in mind, a particularly preferred embodiment will now be described. When the total number of subsets to which a receiver belongs is as large as N, the subsets can be grouped into logN clusters determined by the first subset i (from which another subset is subtracted). For each 1 < i < N corresponding to an internal node in the full tree, an independent and random LABEL LABEL is selected_iIt leads out form S_i，jOf all legal subsets. Whereby the flag deduces the subset key. Fig. 11 illustrates the preferred identification method discussed below. Is marked as L_iIs a subtree T_iAnd its progeny are identified in accordance with the principles of the present invention.

If G is a cryptographic pseudo-random sequence generator, it triples the input length, G _ L (S) represents the left third of G' S output on seed S, G _ R (S) represents the right third, and G _ M (S) represents the middle third. Considering a subtree T of a coverage tree T_iIts root is marked LABEL_iNode V of_iTo (3). If the node is labeled S, its two next generations are labeled G _ L (S) and G _ R (S), respectively. Assigned to set S_i，jIs given by the subset key L_i，jIs in subtree T_iNode V of middle push-out_jLABEL of_i，jIdentified G _ M. Note that each token S elicits three parts, namely a token for the left and right child nodes and a key for the node. Thus, given the label of a node, the labels and keys of all its descendant nodes can be computed. In a preferred embodiment the function G is a cryptographically hashed data, such as secure hash algorithm-1, although other functions may be used.

Fig. 12 shows how the receiver decrypts the message in the subset difference method. From block 66, the receiver finds the subset S to which the receiver belongs_i，jAnd an associated tag (which is part of the receiver's personal information to enable the receiver to derive the LABEL_i，jAnd a subset key L_i，j). The receiver uses this flag to calculate the subset key L at block 68 by evaluating the function G up to N times_i，j. The receiver then decrypts the session key K with the subset key at block 70 for subsequent decryption of the message.

Fig. 13 shows that in the subset difference method the token and thus the subset key is assigned to the receiver. The identification method described is used to minimize the number of keys that must be stored by each receiver.

From block 72, each receiver is provided with indicia of those nodes that are not on the direct path between the receiver and the root, but rather "hanging" on the direct path, and that are originated by the source start node V of u_iAnd (4) pushing out. These marks establish at block 74 the personal information I of the receiver_uThe subsequent message session key is encrypted at block 76 with the subset key derived by the token.

Fig. 14 schematically illustrates the above principle. Each source origin node V with a tag S for a receiver u_iReceiver u receiving signal hanging from slave node V_iLabels of all nodes 71 on the direct path to receiver u. These markers are preferably all derived from S, as will be discussed further. In contrast to the complete subtree approach, the receiver u does not receive data from the receiver u to the node V in the subset difference approach shown in FIGS. 8 to 14_iOf any node 73 in the direct path. Using these flags, receiver u can compute all the roots as nodes V by evaluating the function G described above_iBut not the other subset keys of the set (except the set in the direct path).

Conventional multicast systems lack reverse security in that a revoked regularly receiving receiver can still record all encrypted content and then at some future point obtain a valid new key (e.g., by re-registering the registration) that can decrypt the past content. A preferred embodiment of the invention can be used in this case to solve the problem of reverse security deficiency by including in the revoked receiver set all receiver identities that are deemed not to have been assigned yet. This can be achieved if all receivers are assigned to the blades in sequential order. In this case, the revocation of all unassigned identities results in a modest increase in the size of the message header, but is not proportional to the number of these identities.

A preferred embodiment of the present invention also recognizes that this is required: simply encoding a subset i in a message header_jAnd provides a receiver with a quick determination of whether it belongs to a subset i_jThe pathway of (1). Assume a node is represented by its path to the root, with O representing a left branch and 1 representing a right branch. The end of the path is indicated by a 1 followed by one or more O. So the root is 1000 … 000b, the rightmost progeny of the root is 01000 … 000b, the leftmost progeny of the root is 11000 … 000b, and one leaf is xxx … xxx 1 b.

As described above, the root path of a larger subtree is a subset of the root path of a smaller subtree, and the subset difference may be expressed as the length of the root of the smaller subtree added to the root path of the larger subtree. With this in mind, a receiver can be implemented by implementing the following Intel Pentium^®The processor cycles quickly to determine whether it is in a given subset.

Outside the loop, the following registers are set: the ECX contains the leaf node of the receiver, the ESI points to the message buffer (the first byte is the length of the path to the root of the larger sub-tree and the next 4 bytes are the root of the smaller sub-tree), and a static list outputs 32 bits when indexed by path length, with the preceding length bit being 1 and the remaining bits being 0.

Loop：MOV BYTE EBX，[ESI++]

MOV DWORD EAX，[ESI++]

XOR EAX，ECX

AND EAX，TABLE[EBX]

JNZ LOOP

If a receiver falls outside the loop, it does not necessarily mean that it belongs to a particular subset. It may be in a smaller incompatible subtree and if so it must return to the loop. However, since in most cases the receiver is not already in the larger sub-tree, little processing time is used in this loop.

In a further optimization of the subset difference approach, the system server does not need to remember every marker, which can amount to millions. Alternatively, the marking of the ith node may be a secret function of the node. The security function may be a triple DES encryption that uses an encryption key to regenerate the token for the ith node when applied to the number i.

Having described in detail the subset-cover system that can be used with the preferred embodiment of the present invention, reference is now made to fig. 15 and 16. Proceeding from block 100, subset S_i1，…，S_imIs input to a suspected pirate masquerading device, which has been obtained by an authorized tracing agent. The initial partition S is determined by the current set of revoked devices or, if there are no devices that have been revoked, the initial partition S is the set of all users. Turning now to decision diamond 102, a determination is made as to whether the masker has decrypted content using partition S in accordance with the subset-covering system principles described above, and in particular in accordance with the principles of the subset difference embodiment. A masker is considered to have decrypted the content if it can decrypt the content with some predetermined probability, e.g., P > 0.5. In the most practical counterfeit machine, P is 1. If the masker is not able to decrypt, an encryption has been found that defeats the masker, and processing ends accordingly at state 104.

If, however, the masker has successfully decrypted the content, the process passes to block 124. At block 124, the subset tracking logic routine of FIG. 16, described further below, is executed on the partition S to produce a subset S_ijAnd the logic proceeds to block 106 to receive the subset S_ij. Turning now to decision diamond 108, the subset S is determined_ijWhether or not there is only a single traitor candidate, i.e. subset S_ijWhether there is only a single blade. If so, the traitor has beenFind and process indicates that the jth device is a "traitor" and revokes this traitor by moving it out of the set of non-revoked receivers and placing it in the set R of revoked receivers in block 110. While a new coverage set S is determined at block 111 and processing transfers to block 124, which is described further below.

If subset S_i，jWith more than one traitor candidate, the logic proceeds from decision diamond 108 to block 112 where S is aggregated_ijIs split into two subsets S_ij ¹And S_ij ². Due to the bifurcated nature of the subset-cover system, the subtrees therein can be roughly (but not necessarily precisely) divided into two.

To improve efficiency by reducing the message length required to trace traitors, a preferred method is to move from block 112 to the sub-routine of block 114-122. This subroutine merges those subsets that have not been found to contain traitors into a single, effectively processed group. If this reduction is not required, S_ij ¹And S_ij ²Is added to the overlay and block 114-122 is omitted.

At block 114, subset S_ij ¹And S_ij ²Is added to one of the boundary sets F and is contacted with every other as a "buddy set". The set S is then determined at decision diamond 116_ijWhether in the preceding set of boundaries F (i.e. in the subset S)_ij ¹And S_ij ²The set F before being added to it). If so, it means the set S_ijA complementary set of so-called "buddies" is also in the boundary set F and this set of "buddies" (representing one or more receivers) is removed from the boundary set F in block 118. In this way, sets that have not been found to contain traitor candidates are grouped while departing from the boundary set F.

The logic proceeds from block 118 or from decision diamond 116 when the test result is negative to block 120, where the subsets are as previously describedThe coverage principle computes a coverage C for all receivers u that are not represented in the set in the boundary set F. In particular, the receivers represented by the sets in the boundary set F are temporarily classified in the revoked set R, and then a coverage is determined according to the above-described principle. At block 122, a new partition S is defined to cover the union of C and the subset in the boundary set F. Then at block 124, the subset tracking logic of FIG. 16 is executed on the new S to generate another S_ijAnd the logic loops back to block 106.

Considering now the subset tracking logic shown in FIG. 16, beginning at block 126, a partition S is received. Logically managing a sequence of steps, an exemplary step implements an encryption where the first j subsets are encrypted with a dummy key R having the same length as the session key K_KAnd (5) encoding. That is, if P is the probability that the masquerade will decrypt correctly with partition S, a message is generated:

<E_Li1(R_K)，E_Li2(R_K)，…，E_Lij(R_K)，E_Li(j+1)(K)，…，E_Lim(K)，F_K(M)>

and P is_jIs the probability of decryption when the first j subsets contain false keys. If | P_j-1-P_jIf | P/m, S is present according to a preferred embodiment of the invention_ijA leaf representing a traitor is included. To find out the probability P_j，m²log (1/e) trials were conducted to determine how many counterfeiters output the true message M throughout the trial sequence. In particular, if the masker does not have any keys from the last M-j subsets (which encrypt the actual session key K), it will never be able to determine M (rather than just chance).

Accordingly, a binary search is performed to efficiently find S' S that contain a traitor_ijThe search begins over the entire interval [0, m ]]The above is carried out, and successively using the upper and lower limits [ a, b ]]Bisecting the interval (initialized to [0, m ] in block 130]). Note P₀P and P_m0. And in most practical cases p is 1, i.e.The counterfeit machine can always decrypt in normal operation.

The binary search begins at decision diamond 132 where a determination is made as to whether the upper and lower limits differ by 1 (indicating the end of the search). If so, the logic moves to block 134 to return the sequence number of the jth traitor as the upper bound b. Otherwise, block 136 is entered to find the probability of the midpoint C of the interval [ a, b ], i.e., the decryption probability when the current C subset contains a false key and the other subsets contain a true key.

According to a preferred embodiment of the invention, the probability P of successfully decrypting a message when the first j subsets contain a false key_jCalculated by the following steps: repeatedly selecting message M and encrypting M as F_K(M) a key K, encoding the first j subsets with a false key, encoding the last M-j subsets with a true key K, and observing whether the masker successfully decrypts M.

Then, a determination is made at decision diamond 138 as to whether the absolute value of the difference between the midpoint probability and the lower bound probability is at least equal to the absolute value of half the difference between the lower bound probability and the upper bound probability, i.e., whether there is | Pc-Pa | > | Pc-Pb |. If so, the interval is halved [ a, C ] by taking the ceiling b equal to the current midpoint C and the ceiling probability Pb equal to the midpoint probability Pc at block 140. If, on the other hand, the decision diamond 138 determines that the result is negative, the logic proceeds to block 142. The interval is taken to be [ C, b ] in block 142 by taking the lower bound a equal to the current midpoint C and the lower bound probability Pa equal to the midpoint probability Pc. The logic then returns to decision diamond 132.

At block 136, the midpoint probability Pc is preferably calculated to an accuracy of 1/m. In order for Pc to be estimated accurately with a probability of 1-e, it is required to observe m for a counterfeit machine²log (1/e) queries.

Thus, the logic shown in FIG. 16 preferably performs m for a counterfeit machine²log (m) log (1/e) queries. If desired, a perturbed binary search may be conducted, which at each step assumes that the correct decision is obtained with a probability of 1-Q, where Q is a value close to 1/2, e.g., Q1/3. In one model, each answer is given a certain fixed probability independent of history(e.g., greater than 2/3) is correct, one binary search can be achieved by making logm + log1/Q queries over m sets. In the embodiments described above, it may be assumed that the midpoint probability may yield an error value with a probability Q. This means that the number of queries in the whole process can be reduced to m²(logm + log1/Q) because m is required at each step in order to accurately calculate Pc with a probability of 1-Q²And (5) secondary query.

By running the tracing algorithm in parallel on multiple clones with the same input, multiple traitors can be traced from more than one of the clones. The initial input is a division S₀It is derived from the set of all users that are not in the revoked set R. If, as the process advances, the first dummy "detects" a traitor in one of its sets, it re-partitions accordingly (by traitoring to the revoked set R). The new partition is then input to all of the masqueradings simultaneously. The output of the synchronization method is a partition (or "revocation policy") that invalidates all revoked receivers and masqueradings.

A preferred embodiment of the present invention gives the ability to trace a relatively large number of traitors with relatively small messages. It can be seamlessly integrated with the subset-overlay system described above. And no a priori restrictions are required on the number of traitors that can be traced. Moreover, a preferred embodiment of the present invention does not deal with the fact that a counterfeit machine does to combat tracing by tracing traitors or rendering pirated counterfeit machines useless.

The particular method of tracing traitor receivers in a broadcast encryption system shown and described in detail above fully achieves the above objects of the invention, it being understood that it is a presently preferred embodiment of the invention and is representative of the subject matter which is broadly contemplated by the present embodiment, that the breadth of the preferred embodiment of the present invention fully encompasses other embodiments which may become obvious to those skilled in the art, and that the scope of the preferred embodiment of the present invention is limited by nothing other than the appended claims, in which a single element means "at least one" rather than "only one" unless otherwise specified in the claims. All structural and functional equivalents to the elements of the above-described preferred embodiment that are known or that become known to those of ordinary skill in the art are intended to be encompassed by the present claims. Moreover, it is not necessary for a device or method to mention that a preferred embodiment of the invention covered by the claims solves all the problems. Furthermore, no element, component, or method step in the present disclosure is intended to be disclosed unless explicitly stated in the claim. No claim element is to be understood as being under the clause of the sixth paragraph of 35u.s.c.112 unless the element is explicitly recited by the phrase "means for" or in the case of a method claim the element is said to be a "step" rather than an "action".

Claims (10)

1. A method for identifying or disabling at least one traitor receiver in a broadcast encryption system, the traitor receiver having at least one associated unique, compromised decryption key, the method 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 of blades containing at least one representative traitor receiver; and

identifying or disabling traitor receivers with the subset of traitors;

wherein the step of identifying or disabling a traitor receiver with the traitor subset comprises encoding the subsets of the set of subsets with a dummy key.

2. The method of claim 1, further comprising:

determining whether the traitor subset represents at least two traitor receivers and, if so, splitting the traitor subset into two subsets.

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 3, further comprising performing a binary search on the subset set using the probabilities.

5. The method of claim 4, wherein the binary search is terminated by determining that the difference between two probabilities, one of which is the probability P of decrypting a message when the first j subsets contain false keys, is at least equal to a predetermined probability_jAnother probability is the probability P of decrypting a message when the first j-1 subset contains a false key_j-1。

6. The method of claim 5, wherein when | P_j-1-P_jIf p/m, where m is the number of subsets in the set of subsets and p is the probability of correct decryption of a pseudolite.

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

respective personal information I assigned to each receiver of a group of receivers_u；

Selecting at least one session encryption key K;

partitioning receivers not in the revoked set R into a set of disjoint subsets S_i1，...，S_imThese subsets have an associated subset key L_i1，...，L_im(ii) a And

using subset key L_i1，...，L_imThe session key K and the dummy key are encrypted.

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

9. The method of claim 7, wherein the tree comprises a root and a plurality of nodes, each node being associated with a set of labels, and wherein each receiver is assigned labels from all nodes hanging on a direct path between the receiver and the root, and not from nodes in the direct path.

10. The method of claim 9, wherein the revoked set R determines a spanning tree, and the method includes:

initializing a covering tree T as a spanning tree;

the nodes are repeatedly removed from and added to the overlay tree T until the overlay tree T has at most one node.