Method for tracing traitor receivers in a broadcast encryption system

[Technical field]

【0001】

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

[Background technology]

【0002】

Various broadcast encryption systems that encrypt content that is potentially broadcast to millions of receivers using recorded media such as CDs and DVDs or via radio broadcasting methods such as satellite broadcasting. Has been proposed. These systems encrypt content and only authorized receivers (also referred to as "users" or "player-recorders") can decode and play the content, but somehow valid encryption from authorized devices. A software or hardware-implemented pirate device (also known as a "clone" or "bad device") that has been able to obtain an decryption key (a "trater": rebel) still decrypts the content and It is intended to prevent it from being regenerated.

【0003】

An example of such a system is disclosed in US Pat. No. 6,118,873 of the assignee of the present application, which is incorporated herein by reference. As shown in it, only authorized player-recorders may play and / or copy the content only in accordance with the rules established by the content vendor. In this way, content providers can now prevent pirated copies of content that cost billions of dollars each year.

【0004】

Another example of a broadcast encryption system is disclosed in US Provisional Patent Application No. [reference number ARC9200100_US] of the assignee of the present application, which is incorporated herein by reference. This latter system, the details of which are shown below for illustration, is in the difficult scenario of a "stateless" receiver, a receiver that does not necessarily update its encryption state during broadcasts to accept countermeasures against pirated devices. deal with. For example, a television subscribed to a pay channel may be powered off from its set-top box during the time period during which the updated encrypted data is broadcast through the system. Such devices are made "stateless" if they cannot update themselves after being power cycled, and will not receive the updates needed for future content decryption. Another example of a stateless receiver is a CD and DVD player-recorder, as these usually do not interact with other system components and no player receives all sold discs. , Not receive all encrypted data updates.

[Patent Document 1]

US Pat. No. 6,118,873 [Patent Document 2]

US Provisional Patent Application No. [Reference Number ARC9200100_US]

[Disclosure of Invention]

[Problems to be Solved by the Invention]

【0005】

As will be appreciated by those skilled in the art, the decryption key of a broadcast encryption system could be compromised, allowing unauthorized pirates to decrypt the content. Such pirate devices can be implemented in hardware or software, and in the latter case can be posted on the internet for free download by anyone seeking to obtain proprietary content without payment. There is sex. In any case, the present invention keeps the spread of pirate clones by finding the identification of the system receiver (traitor receiver: rebel receiver) whose key was obtained by the pirate, or the clone cannot be decrypted. It aims to render pirate clones useless by finding encryption that can be decrypted by authorized users.

[Means for solving problems]

【0006】

The present invention specifically (although not exclusively) focuses on the problem of tracing tracers in subset cover systems. Unlike the '873 patented system referenced above, there is no key overlap between devices in the subset cover system. One of the consequences of key overlap is the '873 patented system, in which it is quite normal for one device key to properly decrypt content and another device key not, and as a result, a clone. Is that it is not possible to ascertain whether the clone has been tested by observing whether the message sent to it can be decrypted with all the keys of the clone. This is not true in subset cover systems. This is because every device has at least one unique key. As a result, the clone gets the keys from multiple traitors, one key from one traitor correctly decrypts the content, but another key from another traitor does not properly decrypt the content. In some cases, the clone can infer that it has been tested.

【0007】

A clone can undertake any of a number of opposing means, such as switching identification between trayrs, or self-destructing, if it is inferred that it has been tested. Of course, in the case of self-destruction, the licensing agency could simply obtain another clone for further (modified) testing, but this would be time consuming. With these critical observations in mind, preferred embodiments of the present invention provide the following solutions to one or more observations.

【0008】

Accordingly, in the first aspect, the present invention identifies or disables at least one traitor receiver with at least one associated unique compromised decryption key in a broadcast encryption system. The method is to receive a set of subsets derived from the tree that defines the leaves, each of which contains at least one leaf that represents the receiver of each, receives, and represents the tracer receiver. Provided are methods that include identifying at least one traitor subset from a set of subsets, and using the traitor subset to identify or disable the traitor receiver.

【0009】

The method of the first aspect appropriately further comprises determining whether the traitor subset represents at least one traitor receiver and, if so, splitting the traitor subset into two child sets. ..

【0010】

The method of the first aspect appropriately further comprises removing the interpolated subset from the frontier set, appropriately determining if the tracer subset is an element of the frontier set, and if so.

【0011】

Appropriately, the act of identifying or disabling involves encoding multiple subsets of a set of subsets with a false key.

【0012】

The method of the first aspect further comprises performing a binary search on a set of subsets, as appropriate, using probabilities.

【0013】

Appropriately, the probability that a binary search decrypts a message when the first j subset contains a fake key p_jAnd the probability of decrypting the message when the first j-1 subset contains a fake key p_j-1It ends by determining if the difference between and is equal to at least a given probability.

【0014】

Appropriately, the traitor subset is -p_j-1-p_j-> P / m identified, where m is the number of subsets contained in the subset set.

【0015】

Appropriately, a set of subsets will be sent to each receiver in the group of receivers._uAssigning, selecting at least one session encryption key K, and assigning receivers not included in the revoked set R to the associated subset key L._i1, ..., L_{im im}Coprime subset S with_i1, ..., S_{im im}The session key K and the fake key are divided into a set of subset keys L._i1, ..., L_{im im}It is generated by encrypting with.

【0016】

Appropriately, the tree contains a root and multiple nodes, each node has an associated key, and each receiver assigns a key from all nodes in the direct path between the leaf representing the receiver and the root. Be done.

【0017】

Appropriately, the tree contains the root and multiple nodes, each node is associated with a set of labels, and each receiver hangs from the direct path between the receiver and the root, but is not included in the direct path. Can be assigned a label from.

【0018】

Appropriately, the canceled set R defines a spanning tree, and the method repeats until the cover tree T is initialized as a spanning tree and the cover tree T has at most one node. Includes removing a node from the cover tree T and adding a node to the cover tree T.

【0019】

The method of the first aspect further comprises, as appropriate, identifying or disabling multiple trayer receivers performed on the clone.

【0020】

Appropriately identifying or disabling involves encoding the first j subsets of a set of subsets with a fake key.

【0021】

The present invention includes a computer program device, including a computer program storage device that includes a program of instructions that can be used by a computer, wherein the program of the instructions accesses the tree to generate a set of subsets of the tree. A logical means that the tree contains a leaf that represents at least one traitor device that features a compromised key, encrypts the fake key j times, and encrypts the session key mj times. A logical means, a logical means that identifies a traitor subset in response to a means of encrypting, and a traitor device, where m is the number of subsets contained in the set of subsets. Computer programming equipment can be adequately provided, including with logical means that uses a traitor subset to identify or disable.

【0022】

Further preferred features of the computer programming device can include logical means of causing the computing system to perform the steps of the preferred method according to the preferred features of the first aspect.

【0023】

In a second aspect, the invention comprises a computer program that includes computer program code that causes the computing system to perform the steps of the method according to the first aspect when loaded and executed in the computing system. provide.

【0024】

The preferred features of the second aspect include computer program code that causes the computing system to perform the preferred steps of the method according to the preferred features of the first aspect.

【0025】

The present invention is to appropriately use a fake key to encode a plurality of subsets representing stateless receivers, wherein at least one traitor receiver of said receivers is by at least one pirate receiver. Use and use the pirate receiver or its clone, determine the identity of the traitor receiver, or endanger the pirate receiver or its clone in connection with at least one compromised key obtained. It is possible to further provide a computer programmed with instructions that cause the computer to perform method actions, including making it useless for decrypting data that uses a key.

【0026】

Appropriately, the subset defines the set of subsets, and the method operation undertaken by the computer is to receive the set of subsets derived from the tree that defines the leaves, and each leaf is a receiver for each. Identifying at least one traitor subset from a set of subsets, and using the traitor subset to identify the traitor receiver, as containing at least one leaf representing, receiving, and representing the traitor receiver. Including what to do.

【0027】

Appropriately, the method behavior undertaken by the computer further includes determining whether the traitor subset represents at least one traitor receiver, and if so, splitting the traitor subset into two child sets. ..

【0028】

Appropriately, the method operation undertaken by the computer further comprises determining whether the traitor subset is an element of the frontier set and, if so, removing the interpolated subset from the frontier set.

【0029】

Appropriately, the discriminating action involves encoding multiple subsets of a subset of subsets with a false key.

【0030】

Appropriately, the method operation undertaken by the computer further includes performing a binary search on the set of subsets using probabilities.

【0031】

Appropriately, the probability that a binary search decrypts a message when the first j subset contains a fake key p_jEnds by determining if is at least equal to a given probability.

【0032】

Appropriately, the traitor subset is -p_j-1-p_j-> P / m identified, where m is the number of subsets contained in the subset set.

【0033】

Appropriately, a set of subsets will be sent to each receiver in the group of receivers._uAssigning, selecting at least one session encryption key K, and assigning receivers not included in the revoked set R to the associated subset key L._i1, ..., L_{im im}Coprime subset S with_i1, ..., S_{im im}The session key K and the fake key are divided into a set of subset keys L._i1, ..., L_{im im}Generated by encrypting with, the tree contains the root and multiple nodes, each node is associated with a set of labels, and each receiver hangs from the direct path between the receiver and the root. Labels can be assigned from all nodes that are not directly included in the path.

【0034】

Appropriately, the invention includes a computer system that undertakes the inventive logic described herein. The present invention can also be implemented in computer program products that store the logic of the present invention and can be accessed by a processor to execute the logic. The present invention is also a computer-implemented method according to the logic disclosed below.

【0035】

Program the computer appropriately and use a fake key to encode multiple subsets of stateless receivers. At least one traitor receiver in the system is associated with a compromised key obtained by a cloned pirate receiver. Using a pirate receiver clone, a computer can determine the identity of the traitor receiver or generate a suitable encryption strategy to obtain a pirate receiver clone with a compromised key. Makes the data useless for decrypting.

【0036】

In another aspect, a preferred method of identifying a traitor receiver with an associated unique compromised decryption key within a broadcast encryption system is disclosed. This method involves receiving a set of subsets derived from the tree that defines the leaves, with each leaf representing each receiver. The method also includes identifying the traitor subset from a set of subsets as including at least one traitor receiver, and then using the traitor subset to identify the traitor receiver. ..

【0037】

In a preferred embodiment, the method determines whether the traitor subset represents one or more traitor receivers, and if so, splits the traitor subset into two child sets and two individual sets. Includes identifying a new trayer subset using. A preferred method also includes determining if the traitor subset is an element of the frontier set and, if so, removing the interpolated subset from the frontier set.

【0038】

A preferred form of identifying a traitor subset is to use a false key to encode the first j subsets of the subset set, and then use probabilities to perform a dichotomy on the subset set. Is included. Binary search is the probability of decrypting a message when the first j subset contains a fake key p_jAnd the probability of decrypting when the first j-1 subset contains a fake key p_j-1It ends by determining if the difference between and is equal to at least a given probability. Specifically, the traitor subset is -p_j-1-p_jIdentified when-> p / m, where m is the number of subsets contained in the subset set. A set of subsets is generated by a subset cover scheme that has the property of producing a subset that can be bifurcated.

【0039】

In another aspect, the computer programming device includes a logical means of accessing the tree to generate a set of subsets of the tree, and the tree has at least one traitor characterized by a compromised key. Includes leaves representing the device. A logical means is provided to encrypt the fake key j times and the session key mj times, where m is the number of subsets contained in the subset set. There are also logical means of identifying the traitor subset in response to the means of encryption. Then, by logical means, the traitor subset is used to identify the traitor device.

【0040】

Preferred embodiments of the present invention will be described with reference to the accompanying drawings only by way of example.

[Best mode for carrying out the invention]

【0041】

Preferred embodiments of the present invention can be used with any of a plurality of broadcast encryption methods. As a non-restrictive example, one such system, namely a subset cover system, is shown first, and then the tracing algorithm of the present invention is disclosed with respect to the subset cover system.

【0042】

First, see Figure 1 to show a system generally designated as 10 that generates a set of keys in a broadcast content protection system, such as, but not limited to, the systems disclosed in the patents referenced above. Has been done. "Broadcast" is a program from a content provider to a large number of users, either over cables (from satellite sources), wires, radio frequencies (including satellite sources), or from content discs that are widely sold. Means wide spraying.

【0043】

As can be seen, the system 10 includes a key set definition computer 12 that accesses the key set definition module 14 that functions according to the disclosure below. The key set defined by computer 12 is used by a potentially stateless player-recorder device 16 that has an internal processor to decrypt the content, also referred to herein as "receiver" and "user". Will be done. The content, along with some of the keys disclosed below, is supplied to each device in medium 17 via, for example, device manufacturer 16. The player-recorder device can access the key set to decrypt the content broadcast on the medium or via wireless communication. The "medium" used herein may include, but is not limited to, DVDs, CDs, hard disks, and flash memory devices. In an alternative embodiment, each receiver 16 executes module 14, given a set of canceled receivers, and undertakes the step of calculating the "cover" disclosed below by working on the logic shown below.

【0044】

It should be appreciated that the processor associated with module 14 accesses this module and undertakes the logic illustrated and described below, which can be executed by the processor as a series of computer executable instructions. Selectively use System 10 to allow an endangered receiver 16 to decrypt broadcast content without revoking the ability of the unaffected receiver 16 to decrypt the broadcast content. Two methods of revoking the method, namely the complete subtree method and the subset difference method, are disclosed herein.

【0045】

Instructions can be included in a data storage device that has a computer-readable medium, such as a computer diskette that has a computer-enabled medium on which a computer-readable code element is stored. Alternatively, the instructions can be stored on a DASD array, magnetic tape, conventional hard disk, electronic read-only memory, optical storage, or other suitable data storage. In an exemplary embodiment of the invention, a computer executable instruction can be a line of compiled C ++ compatible code.

【0046】

In fact, the flow charts herein show the logical structure of a preferred embodiment of the invention implemented in computer program software. Those skilled in the art will appreciate that these flow diagrams show the structure of computer program code elements, including logic circuits on integrated circuits, that function according to the present invention. Obviously, the present invention, in its essential embodiment, is a machine that directs a program code element to a digital processor (ie, a computer) to perform a sequence of functional operations corresponding to those shown. Practiced by the components.

【0047】

The overall logic of preferred embodiments of the invention implemented by both the subset difference method and the complete subtree method can be seen with respect to FIG. In this disclosure, if there are N receivers 16 in system 10 and the revoked receivers work together (by sharing encryption knowledge) all receivers can still decrypt the content. Even so, assume that it is desirable that r receivers in the canceled receiver subset R be able to revoke the ability to decrypt the content. Starting at block 19, the system has a long-lived subset key L₁, ..., L_w, The population S of the subset₁, ..., S_wInitiated by assigning to the corresponding subset of, to this population the receivers are grouped according to the disclosure below, and therefore each subset S._jBut the associated long-lived subset key L_jHave. In the first ("complete subtree") method, the subset that covers the receivers that are not included in the canceled set is simply the subtree that is generated according to the disclosure below. In the second ("subset difference") method, as further shown below, the subset covering receivers not included in the canceled set is smaller than the first subtree and completely within the first subtree. Defined by the difference between the subtrees.

【0048】

At block 20, private information useful for decrypting content I_uIs further started by supplying each receiver u. Private information I_uDetails of are shown below. I_uIf is confidential information supplied to receiver u, then S_jEach receiver u included in is its I_uFrom L_jCan be derived. As shown more fully below, given the canceled set R, the uncancelled receivers have m relatively prime subsets S._i1, ..., S_{im im}The short-lived session key K is divided into, and the subset S of each is_i1, ..., S_{im im}Long-lived subset key L related to_i1, ..., L_{im im}Is encrypted m times using. The subset key is an explicit subset key in the complete subtree method and is derived by the subset label in the subset difference method.

【0049】

Specifically, in block 22, at least one session key K is selected and used to broadcast in message M via either a wireless or wired communication path or a storage medium such as a CD and DVD. Encrypt the content. The session key K is a random string of bits newly selected for each message. Multiple session keys can be used to encrypt each part of message M, if desired.

【0050】

In both of the methods described below, the uncancelled receivers are disjoint subsets S using a tree in block 24._i1, ..., S_{im im}Divide into. This subset is sometimes referred to herein as a "subtree", but in the first method the subtree is explicitly considered and in the second method the subtree is "completely the first from the first subtree". It is considered to be in the form of "subtree of the second subtree contained in the subtree". Each subset S_i1, ..., S_{im im}Is a subset key L of each_i1, ..., L_{im im}is connected with. Although any data tree-like structure is contemplated herein, it is assumed in the disclosure that the tree is an entire binary tree.

【0051】

Proceeding to block 26, in general, the session key K is the subset key L._i1, ..., L_{im im}It is encrypted m times using each of the above once. In the resulting ciphertext that is broadcast, the part between the square brackets represents the header of message M, i₁, I₂, ..., i_mAssuming that represents the index of a subset of coprime, it can be expressed as follows. <[i₁, I₂, ..., i_m, E_Li1(K), E_Li2(K), ..., E_Lim(K)], F_K(M)> [0052]

In one embodiment, the encryption primitive F_KIs implemented by XORing the message M and the stream cipher generated by the session key K. Cryptographic Primitive E_LIs a method of delivering the session key K to the receiver 16 using a long-lived subset key. F_K, E_LIt should be understood that all cryptographic algorithms related to are within the scope of the present invention. E_LOne of the preferred embodiments of is a block cipher prefix truncation designation. l, but the length is E_LAssuming that it represents a random string equal to the block length of, K is a cipher F of length, for example 56 bits._KSuppose it is a short key. In that case, [Prefix_-K-E_L(l) / K] provides strong encryption. Therefore, the header with the prefix truncated is as follows. <[i₁, I₂, ..., i_m, U, [Prefix_-K-E_Li1(U)] / K, ..., [Prefix_-K-E_Lim(U)] / K], F_K(M)> [0053]

This advantageously reduces the header length to about mK-bits instead of mL-. E_LFactor m that an adversary has a brute force attack resulting from encrypting the same string l with m different keys, using the following when the key length of is minimal. The advantage of can be eliminated. String l / i_jIs encrypted. That is, <[i₁, I₂, ..., i_m, U, [Prefix_-L-E_Li1(U / i₁)] / K, ..., [Prefix_-L-E_Lim(U / i_m)] / K], F_K(M)> [0054]

Having described the preferred non-restrictive form of implementing the encryption primitives E and F, moving on to Figure 3, this figure shows the decryption logic that receiver 16 undertakes. Starting from block 28, each undone receiver u has a ciphertext subset identifier i_jAnd its receiver is a subset S_ijTo belong to. As further disclosed below, the result of block 28 does not exist when the receiver is included in the canceled set R. Then, in block 30, the receiver has its private information I_uUsing the subset S_ijSubset key L corresponding to_ijIs extracted. Using this subset key, block 32 determines the session key K, and block 34 uses the session key K to decrypt the message.

【0055】

Two preferred ways to approach the overall logic described above are disclosed below. In both cases, a collection of subsets is specified as a way to cover unrevoked receivers using the form of assigning keys to subsets and the disjoint subsets from the collection. In both cases, the set of receivers in the system establishes leaves, such as, but not limited to, the entire binary tree.

【0056】

The first method described is the complete subtree method shown in Figures 4-7. Starting from block 36 in Figure 4, an independent random subset key L_i, Each node of the tree v_iAssign to. This subset key L_iIs node v_iCorresponds to a subset containing all leaves rooted in. Then, in block 38, each receiver u is given all the subset keys in the direct path from that receiver to the root. Subset S, as you can see by temporarily referring to Figure 7._iThe receiver u included in the node v_iSubset key L related to_i, As well as S_iGiven the key associated with node P between the receiver contained in and the root of the tree.

【0057】

When a message is sent and one receiver wants to revoke the ability to decrypt the message, the logic in Figure 5 is called to split the unrevoked receivers into relatively disjoint subsets. Starting at block 40, we discover the spanning tree defined by the leaves of R, which is a collection of canceled receivers. Spanning tree is a minimal subtree of the entire binary tree that connects "cancelled" leaves and can be a Steiner tree. Proceed to block 42 to identify subtrees that have routes adjacent to one node in the tree (ie, nodes that are directly adjacent to the minimal tree). These subtrees define a "cover" and the subset S_i1, ..., S_{im im}Is established. The cover contains all undone receivers. Therefore, at block 44, the session key K is encrypted using the subset key defined by the cover.

【0058】

Each receiver calls the logic in Figure 6 to decrypt the message. Starting at block 46, the higher-level nodes are the set i in the message header.₁, I₂, ..., i_mBy determining if it is inside, it is determined whether any of the upper nodes of the receiver is associated with the subset key of the cover. Receiver private information I_uConsists of a subset key associated with a position in the tree and a higher-level node in the full subtree method, but this private information I_uIs used for this determination. If the ancestor is found in the message header (indicating that the receiver is an unrevoked receiver), block 48 uses the subset key to decrypt the session key K and then blocks it. At 50, use session key K to decrypt the message.

【0059】

In the full subtree method, the header contains at most r × log (N / r) subset keys and encryption. This is also the average number of keys and encryption. In addition, each receiver must store log N keys, and each receiver processes the message using at most log log N operations and a single decryption operation.

【0060】

Then, referring to FIGS. 8 to 13, we can see the subset difference method for canceling the receiver. In the subset finite difference method, each receiver has a relatively large number of keys (.5log) than in the full subtree method.² N + .5log N + 1 key) must be stored, but the message header contains at most 2r-1 subset keys and encryption (average 1.25r), which is Substantially less than the full subtree method. Also, in the subset delta method, messages are processed using at most log N application and a single decryption operation of the pseudo-random number generator.

【0061】

With reference to FIGS. 8 and 9, in the subset difference method, a subset is considered to be the difference between the larger subset A and the smaller subset B that is completely contained in A. Therefore, as you can see in the figure, the larger subtree is the node v_iIs the root, and smaller subtrees are v_iNode descending from v_jIs the root. Subset of results S_{i, j}Is v_jExcept for the leaves labeled "no" below (and the leaves that are darker than the leaves labeled "yes"), v_iConsists of all the leaves "yes" underneath. Figure 9 shows this, but the subset v_{i, j}Is represented by the area outside the smaller triangle within the larger triangle.

【0062】

The structure described above is used as shown in FIG. 10 when the subset difference method is used to send a message and some receivers want to undo the ability to decrypt the message. .. Starting at block 52, we discover the spanning tree defined by the leaves contained in R, which is a collection of canceled receivers. This spanning tree is a minimal subtree of the entire binary tree connecting the "cancelled" leaves and can be a Steiner tree. Proceed to block 54 to initialize cover tree T as spanning tree. It then starts an iterative loop, removing the nodes from the cover tree and adding subtrees to the cover until the cover tree T has at most one node. This output defines the cover of the receiver that has not been undone.

【0063】

Specifically, moving from block 54 to block 56, the leaf v in the cover tree T so that its smallest common top v does not contain leaves in T._iAnd v_jTo find out. Judgment Rhombus 57 determines if there is only one leaf in the cover tree T. If there are multiple leaves, the logic moves to block 58, v_iIs v_lDescend from v_jIs v_kDescend from v_l, V_kIs a child of v (ie v and v_l, V_kNodes in v so that they are direct descendants of v, with no intervening nodes between them._l, V_kTo find out. In contrast, when there is only a single leaf in T, this logic moves from judgment diamond 57 to block 60, v_i= v_j= Set the only remaining leaf, put v in the root of T, v_l= v_k= Set the route.

【0064】

From block 58 or 60, this logic moves to the judgment diamond 62. Judgment rhombus 62, v_lAnd v_iDetermine if are equal. Similarly, v_kAnd v_jDetermine if are equal. v_lAnd v_iIf are not equal, this logic moves to block 64 and a subset S to T_{l, i}Adds, removes all of v's offspring from T, and makes v a leaf. Similarly, v_kAnd v_jIf they are not equal, this logic moves to block 64 and a subset S to T_{k, j}Adds, removes all of v's offspring from T, and makes v a leaf. This logic loops back to block 56 from block 64 or from the judgment diamond 62 when no inequality is determined.

【0065】

A particularly preferred embodiment is shown with the overall picture of the above subset differential key allocation method in mind. The total number of subsets to which the receiver belongs is as large as N, but groups these subsets into log N clusters defined by the first subset i (from which another subset is subtracted). Can be transformed into. Independent random label LABEL for each of the 1 <i <N corresponding to the internal nodes of the entire tree_iIs selected, thereby S_{i, j}All labels of a legitimate subset of the form are derived. A subset key is derived from this label. FIG. 11 shows a preferred labeling method described below. L_iThe node labeled is subtree T_iAnd its descendants are labeled according to the principles of the invention.

【0066】

G_L (S) represents the left 1/3 of the output of G for the species S and G_R (S) is the right 1 when G is a cryptographically secure sequence generator that triples the length of the input. Represents / 3 and G_M (S) represents the central 1/3. Node v_iIs the root and the label LABEL_iSubtree T of cover tree T with_iPlease consider. If this node is labeled S, its two children are labeled G_L (S) and G_R (S), respectively. Set S_{i, j}Subset key L assigned to_{i, j}Is a subtree T_iNodes derived within v_jLABEL_{i, j}It is G_M labeled as. Note that each label S derives a key for three parts: the left and right child labels and the node. As a result, given the label of a node, it is possible to calculate the labels and keys of all its offspring. In one preferred embodiment, the function G is a cryptographic hash, such as Secure Hashing Algorithm-1, but other functions can be used.

【0067】

Figure 12 shows how the receiver decrypts a message using the subset difference method. Starting at block 66, the receiver is the subset S to which it belongs._{i, j}The associated label (receiver is LABEL)_{i, j}And subset key L_{i, j}Find with some of the private information) that allows you to derive. Using this label, the receiver in block 68 evaluates the function G at most LOG N times to the subset key L._{i, j}To calculate. The receiver then decrypts the session key K at block 70, using the subset key K for subsequent message decryption.

【0068】

FIG. 13 shows how labels, and thus subset keys, are assigned to receivers with subset differences. The labeling methods disclosed herein are used to minimize the number of keys that each receiver must store.

【0069】

Starting at block 72, each receiver has a node v above u of a node that "hangs" from the direct path rather than being included in the direct path between that receiver and the route._iThe label derived by is given. With these labels, the receiver's private information I at block 74_uIs established, and for subsequent messages, in block 76, the session key is encrypted with the subset key derived from the label.

【0070】

The above principle will be explained with reference to FIG. 14 temporarily. All v with label S on receiver u_iFor the upper node, the receiver u is the node v_iReceives labels for all nodes 71 hanging from the direct path from to receiver u. As further described below, it is preferred that all of these labels are derived from S. In contrast to the full subtree method, in the subset difference method shown in Figures 8-14, the receiver u is from the receiver u to the node v._iDoes not receive labels from all nodes 73 contained in the direct path to. Using these labels, the receiver u evaluates the function G described above to the node v without calculating any other subset keys._iYou can calculate subset keys for all sets rooted in (except direct path sets).

【0071】

Traditional multicast systems lack backward secrecy, that is, a receiver that is revoked but always listening can still record all of the encrypted content, and then in the future. At some point, you will get a valid new key (for example, by re-registering), which will allow you to decrypt past content. A preferred embodiment of the invention can be used in such a scenario to correct the lack of secret in the opposite direction by including all receiver identifications that have not yet been assigned to the set of revoked receivers. .. This can be done if all receivers are assigned to the leaves in a contiguous order. In this case, the cancellation of all unassigned identifications results in a modest increase in message header size rather than proportional to the number of such identifications.

【0072】

In a preferred embodiment of the invention, a subset i in the message header i_jHaving a concise encoding of, and the receiver, that receiver is a subset i_jIt is also acknowledged that it is desirable to provide a method for quickly determining whether or not a member belongs to. Suppose a node is indicated by the path to its root, where 0 indicates the left branch and 1 indicates the right branch. The end of the path is indicated by a 1 followed by zero or more zero bits. So the root is 1000 .... 000b, the rightmost child of the root is 01000 ... 000b, the leftmost child of the root is 11000 ... 000b, and the leaves are xxxx .. .xxxx1b.

【0073】

As recognized herein, the path of the root of the larger subtree is a subset of the path of the root of the smaller subtree, so that the subset difference is greater than the root of the smaller subtree. It can be indicated by the length of the path to the root of the subtree. With this in mind, the receiver can quickly determine if it is part of a given subset by running the Intel Pentium (R) processor loop below.

【0074】

Outside the loop, set up the following registers: ECX stores the leaf node of the receiver and the ESI is the message buffer (the first byte is the length of the path to the larger subtree, then 4 bytes are the root of the smaller tree), and when indexed by the length of the path by the static table, the first length bit is 1 and the remaining bits are 0 32. Bits are output.<img file="JP2004527937A_D0001.tif" /> 【0075】

If the receiver breaks out of the loop, this does not necessarily mean that the receiver belongs to a particular subset. It may be in a smaller excluded subtree, and if so, you must return to the loop. However, in most cases, the receiver is not included in the larger subtree, so it takes very little processing time in the loop.

【0076】

Further optimization of the subset finite difference method does not require the system server to remember each of all levels, which can be in the millions. Instead, the label of the i-th node can be a secret function of the node. This secret function can be Triple DES encryption, which uses the private key to give the label of the i-th node when applied to the number i.

【0077】

See FIGS. 15 and 16 for details of the subset cover system in which the preferred embodiments of the present invention can be used with it. Starting at block 100, subset S_i1, ..., S_{im im}Enter the split S in the suspected pirate cloning device obtained by an authorized tracing agency. The first split is guided by the current set of canceled devices, and if the device is not canceled, the first split S is the set of all users. Going to Judgment Diamond 102, whether the clone decrypted the content using the split S according to the Subset Cover System principle disclosed above, preferably according to the Subset Difference Embodiment principle. judge. A clone is considered to decrypt content if it can decrypt the message with a certain probability, for example p&gt; .5. For most practical clones, p = 1. If the clone cannot be decrypted, an encryption has been found that spoils the clone, so the process ends in state 104.

【0078】

However, if the clone successfully decrypts the content, this process moves to block 124. In block 124, the subset tracing logic of FIG. 16 described further below is executed on the partition S, and the subset S is executed._ijIs created and the logic goes to block 106 and the subset S_ijTo receive. Proceed to Judgment Rhombus 108, Subset S_ijWhether it contains only a single tracer candidate, i.e., the subset S_ijDetermines if it has only a single leaf. If so, a traitor has been found, and this process, in block 110, indicates the jth device as a "traitor", removing the traitor from the set of undanced receivers, and undoing the traitor. Cancel the traitor by placing it in the set R of the receivers. This defines a new cover set S in block 111, and processing proceeds to block 124, which is described more fully below.

【0079】

Subset S_ijHowever, if there are multiple traitor candidates, this logic proceeds from the judgment diamond 108 to block 112, where the set S_ij, Two child sets S¹_ijAnd S²_ijDivide into. This is possible due to the bifurcated nature of the subset cover system, which allows the subset cover system to split the subtree into roughly (not necessarily accurate) halves.

【0080】

One of the preferred embodiments to achieve efficiency by reducing the message length required to trace t traitors, from block 112 to the subroutines shown in blocks 114 to 122. You can move. This subroutine serves to merge subsets that have not yet been found to contain a traitor into a single efficiently processed group. If no such reduction is needed, S¹_ijAnd S²_ijIs added to the cover, and blocks 114 to 122 are omitted.

【0081】

At block 114, the child set S¹_ijAnd S²_ijAre added to the frontier set F and related to each other as a "companion set". Next, in the judgment rhombus 116, the set S_ijIs the previous frontier set F (ie, the child set S)¹_ijAnd S²_ijDetermine if it was included in the set F) that existed before was added. If included, this is the set S_ijHowever, it also means that it had a complement set, the so-called "buddy" set, which was also included in the frontier set F, and in block 118, the "buddy" set (representing one or more receivers) was from the frontier set F. Will be removed. In this way, sets that have not yet been found to contain traitor candidates are grouped separately from the frontier set F.

【0082】

Judgment from block 118 or if the test result is negative From rhombus 116, this logic proceeds to block 120, where cover C is set to the set of frontier sets F according to the subset cover principle shown above. Calculate for all unrepresented receivers u. Specifically, the receiver represented by the set contained in the frontier set F is temporarily classified into the canceled set R, and the cover is judged according to the above principle. In block 122, the new split S is defined as the union of the cover C and the subsets contained in the frontier set F. Then, in block 124, perform the subset tracing logic of Figure 16 on the new S to another S._ijAnd this logic loops back to block 106.

【0083】

Therefore, considering the subset tracing logic of FIG. 16, starting at block 126, the split S is received. This logic manages the sequence of steps, in normal steps encryption is performed, and the first j subset is a fake key R with the same length as the session key K._KEncoded using. That is, when p is the probability that the clone will be correctly decrypted using the split S, a message of the form: &lt;E_li1(R_K), E_Li2(R_K), ..., E_Lij(R_K), E_{Li (j + 1)}(K), ..., E_Lim(K), F_K(M)&gt; p_jIs the probability of decryption when the first j subset contains a fake key. -p_j-1-p_j-&gt; P / m, according to the preferred embodiment of the invention, S_ijIncludes leaves that represent the trayer. Probability p_jTo find m²Start log (1 / e) experiments to determine how many times in the entire sequence of experiments the clone will output the actual message M. Specifically, if the clone has no keys from the last mj subset (the key that encrypted the actual session key K), the clone can never determine M (just by chance). except).

【0084】

Therefore, we perform a binary search, starting with the entire interval [0, m] and using the upper and lower boundaries [a, b] (initialized to [0, m] in block 130) for consecutive intervals. S including the traitor by halving_ijEfficiently find. p₀= p and p_mNote that = 0. Moreover, in most practical cases, p = 1, that is, the clone will always be decrypted during normal operation.

【0085】

The binary search begins with a judgment diamond 132, where it is determined whether the upper and lower bounds are one apart (indicating the end of the search). If so, this logic returns the index of the j-th traitor as the upper bound b at block 134. If not, this logic moves to block 136 and the probability of midpoint c in the interval [a, b], that is, the first c subsets contain false keys and the other subsets are true. Find the probability of decryption when the key is included.

【0086】

According to a preferred embodiment of the invention, the probability that a message will be successfully decrypted when the first j subset contains a fake key p_jRepeatedly selects message M with key K, encrypts M as Fk (M), encodes the first j subsets with a fake key, and obtains the true key K. It is calculated by using it to encode the last mj subset and observing whether the clone successfully decrypts M.

【0087】

The judgment rhombus 138 then determines whether the absolute value of the difference between the probability of the midpoint and the probability of the lower bound is equal to at least half the absolute value of the difference between the probability of the lower bound and the probability of the upper bound. (Ie, -p_c-p_a-&gt; -p_c-p_{b b}-To determine if it is). If so, at block 140, equalize the upper bound b with the current midpoint c, and the upper bound probability p._{b b}Midpoint probability p_cBy making it equal to, the interval is halved [a, c]. On the other hand, in the case of the negative test on the judgment diamond 138, this logic goes to block 142. In block 142, making the lower bound equal to the current midpoint c and the lower bound probability p_aMidpoint probability p_cBy equalizing with, the interval is halved [c, b]. This logic then loops back to the judgment diamond 132.

【0088】

At block 136, the probability of midpoint p_cHowever, it is preferable to calculate with an accuracy of 1 / m. p_cHowever, to ensure that it is estimated accurately with a probability of 1-e, m for the clone² It is necessary to observe log (1 / e) queries.

【0089】

Therefore, in the logic of Figure 16, m for a clone²It is preferable to use log (m) log (1 / e) times of queries. If desired, undertake a noisy binary search, which is assumed at each step to give the correct judgment with a probability of 1-Q (Q is close to 1/2, eg Q = 1/3). be able to. Each answer is a correct model with a fixed probability (eg, more than 2/3) independent of history, and it is possible to perform a binary search on m sets with log m + log 1 / Q queries. is there. In the embodiments disclosed above, it can be assumed that the midpoint probability gives an erroneous value at the probability Q. This is the number of queries for the entire procedure, m²Imply that it can be reduced to (log m + log 1 / Q). Because with a probability of 1-Q, p_cTo calculate accurately, m at each step²This is because multiple queries are required.

【0090】

The traitor can be traced from multiple clones by running the trace algorithm in parallel for the clones using the same input. The first input is a split S that results from a set of all users whose none is placed in the canceled set R.₀Is. As the process progresses, when the first clone "detects" the traitor in one of its sets, the clone subdivides the set accordingly (by moving the traitor to the canceled set R). ). The new split will be entered into all clones at the same time. The output of the concurrent method is a split (or "cancellation strategy") that invalidates all canceled receivers and clones.

【0091】

A preferred embodiment of the present invention provides the ability to trace a relatively large number of traitors using relatively small messages. Preferred embodiments of the present invention can be seamlessly integrated with the subset cover system referenced above. Also, there is no need for an a priori limit on the number of tracers that can be traced. Moreover, a preferred embodiment of the invention works by either tracing the tracer or making the pirate clone useless, regardless of what the clone does against tracing.

【0092】

The particular "method of tracing a traitor receiver in a broadcast encryption system" illustrated and described herein can fully achieve the object described above of the present invention, which is the present invention. Other embodiments that are currently preferred embodiments and thus represent objects broadly contemplated by the preferred embodiments of the invention and that the scope of the preferred embodiments of the invention may be apparent to those skilled in the art. The scope of the preferred embodiments of the present invention is therefore not limited by anything other than the claims, in which the reference to a singular element is made in the claims. It should be understood that unless specified in the form, it means "at least one" rather than "only". All structural and functional equivalents to the elements of the preferred embodiments described above, known to those of skill in the art or later known, are specifically incorporated herein by reference and claimed. Is intended. Moreover, it is not necessary for the device or method to address each of all the problems that are required to be solved by the preferred embodiments of the invention in order to be embraced by the claims. Moreover, the elements, components, or method steps of this disclosure are dedicated to the public, regardless of whether those elements, components, or method steps are specifically specified in the claims. A claim element herein is unless the element is specifically specified as the phrase "means of", or in the case of a method claim, the element is described as "step" instead of "action". , Should not be construed under the provisions of 35 USC Section 112, paragraph 6.

[Simple explanation of drawings]

【0093】

FIG. 1 is a block diagram of this system.

FIG. 2 is a flow chart of the entire encryption logic.

FIG. 3 is a flow chart of the entire decryption logic.

FIG. 4 is a flow chart of a key allocation part of the complete subtree method.

FIG. 5 is a flow chart of an encrypted part of the complete subtree method.

FIG. 6 is a flow chart of an decryption part of the complete subtree method.

FIG. 7 is a schematic diagram of a subset of a complete subtree.

FIG. 8 is a schematic diagram of a subset of the subset difference method.

FIG. 9 is a schematic diagram of another form of a subset of the subset finite difference method.

FIG. 10 is a logic flow diagram defining a cover of the subset finite difference method.

FIG. 11 is a schematic diagram of a subset of a subset finite difference method tree showing key assignment.

FIG. 12 is a flow chart of an decryption part of the subset difference method.

FIG. 13 is a flow diagram of logic for assigning keys of the subset difference method.

FIG. 14 is a schematic diagram of a subset of a tree of the subset finite difference method.

FIG. 15 is a flow chart showing the trace logic of the present invention.

FIG. 16 is a flow diagram showing a subset trace module of trace logic.