Patent Publication Number: US-8122246-B2

Title: Method for generating decryption key, apparatus and method using decryption key

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is based upon and claims the benefit of priority from prior Japanese Patent Application No. 2006-019795, filed Jan. 27, 2006, the entire contents of which are incorporated herein by reference. 
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to a system for decrypting an encrypted content. 
     2. Description of the Related Art 
     Conventionally, in broadcast-type content distribution business, broadcast program content is encrypted, and the encrypted content is distributed to users. For example, a user decrypts encrypted content by using an authorized decryption unit leased by a distributor, and views/listens to the broadcast program through the obtained content. In broadcast-type content distribution business, however, there are unauthorized users who produce pirate decryption units (unauthorized decryption units) by copying internal information (decryption key or the like) of an authorized decryption unit, and can illegally decrypt encrypted content. 
     Various types of unauthorized user specifying methods are known, which can specify such an unauthorized user. Such unauthorized user specifying methods are classified into three types according to decryption key generation methods for users. The first type is a method based on a combinatric arrangement. The second type is a method based on a tree structure. The third type is a method based on an algebraic arrangement. 
     The first unauthorized user specifying method has a problem that a very large transmission overhead is required to sufficiently decrease the probability at which an authorized user who is not concerned in the generation of an unauthorized decryption unit is erroneously detected as an unauthorized user. 
     The second and third unauthorized user specifying methods solve this problem and achieve efficient transmission overhead. 
     An unauthorized decryption unit may store a plurality of decryption keys or data having functions equivalent to decryption keys in a conspiracy involving a plurality of unauthorized users. Black box tracking is sometimes performed for this unauthorized decryption unit to specify an unauthorized user by observing only the input/output of the unit without breaking it open. More specifically, a tracker who performs black box tracking assumes a candidate for an unauthorized user (to be referred to as a suspect hereinafter) and checks whether the decryption key of the suspect is held by an unauthorized decryption unit, by only observing the input/output of the unauthorized decryption unit. 
     In the second and third unauthorized user specifying methods, one of the following two problems is left unsolved: 
     Problem 1: In black box tracking, the intention of each input (assumed suspect) is known by an unauthorized decryption unit. If a smart unauthorized decryption unit reads the intention of an input and prevents the unauthorized user from being specified, black box tracking fails. This failure leads to a problem that an unauthorized user cannot be specified, or an innocent user is falsely accused. 
     Problem 2: Although an unauthorized decryption unit cannot read the intention of an input, the probability of correctly specifying an unauthorized user trades off with a transmission overhead. If, therefore, the transmission overhead is made efficient, the probability of correctly specifying an unauthorized user greatly decreases. The number of processing steps required for black box tracking is exponential, and hence such black box tracking is impracticable because a set of nCk=n!/{k!(n−k)!} suspects must be checked, where n is the total number of users and k is the maximum number of conspirators. 
     As described above, the conventional unauthorized user specifying methods fail in black box tracking with respect to smart unauthorized decryption units. In consideration of this problem, JP-A 2005-236963 (KOKAI) discloses an unauthorized user specifying method which can reliably execute black box tracking even with respect to a smart unauthorized decryption unit without allowing it to know the intention of an input. 
     Of the unauthorized user specifying methods disclosed in JP-A 2005-236963 (KOKAI), a method which achieves more efficient transmission overhead is a method in which the amount of transmission data is reduced by assigning the leaves of a tree structure to users and making a key generation polynomial multilevel. In this case, since the memory size which a decryption unit can have is limited by the manufacturing cost and the like, there is a demand for reducing the size of decryption key data to be held by the decryption unit. It is therefore preferable to further reduce the size of decryption key data to be held by the decryption unit. 
     As described above, the conventional unauthorized user specifying methods cannot achieve the two challenges of reliably executing black box tracking even with respect to a smart unauthorized decryption unit without allowing it to know the intention of an input and reducing the size of decryption key data to be held by the decryption unit. 
     BRIEF SUMMARY OF THE INVENTION 
     A decryption key generation method includes (a) dividing a group of a plurality of user identification information items for individually identifying a plurality of user systems into a plurality of subgroups; (b) assigning the subgroups to a plurality of different leaves on a tree structure respectively, the tree structure including a root node, one or a plurality of nodes and the leaves; (c) assigning different individual key generation polynomials to all or some of the root, the nodes, and the leaves on the tree structure respectively; (d) assigning each subgroup one of the individual key generation polynomials which corresponds to one of leaves assigned to the each subgroup or an ancestor node of the one of the leaves; and (d) substituting each user identification information item in the each subgroup into the one of the individual key generation polynomial assigned to the each subgroup and a common key generation polynomial common to the root, the nodes, and the leaves, to obtain a decryption key unique to each user system which corresponds to the each user identification information item,
         wherein at least one of linear sums of coefficients with the same degree of the one of the individual key generation polynomial and the common key generation polynomial differs for each of the root, the nodes, and the leaves on the tree structure, and the linear sums of other coefficients with the same degrees are constant.       

    
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING 
         FIG. 1  is a schematic view showing the arrangement of a data communication system to which a content distribution system, user systems, and the like according to the first embodiment; 
         FIG. 2  is a schematic view for explaining the subgroups of a user set; 
         FIG. 3  is a schematic view for explaining the subgroups of a user set; 
         FIG. 4  is a schematic view showing the arrangement of a tracking system; 
         FIG. 5  is a flowchart for explaining the overall operation of the data communication system; 
         FIG. 6  is a flowchart for explaining operation in an encryption phase; 
         FIG. 7  is a schematic view for explaining processing by a header generation unit; 
         FIG. 8  is a flowchart for explaining operation in a decryption phase; 
         FIG. 9  is a flowchart for explaining operation in a tracking phase; 
         FIG. 10  is a schematic view for explaining an outline of a test; 
         FIG. 11  is a schematic view for explaining a test result; 
         FIG. 12  is a schematic view showing a modification of the data communication system; 
         FIG. 13  is a view for explaining how individual key generation polynomials and a common key generation polynomial are assigned to the root/nodes/leaves on a tree structure; 
         FIG. 14  is a flowchart for explaining another operation in the encryption phase; 
         FIG. 15  is a view for explaining a tree structure; 
         FIG. 16  is a flowchart for explaining decryption key generation processing operation; and 
         FIGS. 17A to 17C  are views for explaining an unauthorized user. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Each embodiment of the present invention will be described below with reference to the views of the accompanying drawing. 
     First Embodiment 
       FIG. 1  is a schematic view showing the arrangement of a data communication system to which a content distribution system, user systems, and the like according to the present invention are applied.  FIGS. 2 and 3  are schematic views for explaining subgroups of a user set in this embodiment.  FIG. 4  is a schematic view showing the arrangement of a tracking apparatus according to the embodiment. 
     As shown in  FIG. 1 , in this data communication system, a content distribution system  1  including an encryption apparatus  10  and n user systems  2  each having a decryption unit  20  are connected to each other through a network  3 . In addition, for example, a tracking apparatus  30  is connected to the network  3 . 
     In this case, the content distribution system  1  encrypts content and broadcasts or multicasts it through the network  3 . 
     The n user systems  2  each receive and decrypt the encrypted content broadcast or multicast by the content distribution system  1  through the network  3 . 
     Although  FIG. 1  shows only one content distribution system  1 , a plurality of content distribution systems  1  may exist. 
     In addition, one node may have both the function of the content distribution system  1  and the function of the user system  2 . Alternatively, all the nodes may each be provided with both the function of the content distribution system  1  and the function of the user system  2  to allow them to perform encrypted communication with each other. 
     The network  3  may be a wired network or a wireless network. Alternatively, the network  3  may include both a wired network and a wireless network, or may be a bidirectional network or a unidirectional network. In addition, the network  3  may be offline. That is, a network may be realized by using a medium such as a DVD. 
     The encryption apparatus  10  mounted in the content distribution system  1  will be described next. 
     The encryption apparatus  10  includes a public key storing unit  11 , first storing unit  12 , session key generation unit  13 , content encryption unit  14 , and header generation unit  15 . 
     The public key storing unit  11  is a memory which stores a public key, from which information can be read by the session key generation unit  13  and the header generation unit  15 . 
     The first storing unit  12  is a memory which stores information (user ID or the like) associated with a user to be invalidated, from which information can be read by the header generation unit  15 . 
     The session key generation unit  13  has a function of generating a session key on the basis of a public key in the public key storing unit  11 . 
     The content encryption unit  14  has a function of obtaining an encrypted content by encrypting a content to be distributed on the basis of the session key generated by the session key generation unit  13 . Note that the encrypted content can be decrypted on the basis of the session key. 
     The header generation unit  15  has a function of generating header information on the basis of a public key, a session key (information on which it is based), invalid user information (if there is an invalid user), other necessary parameters (parameters p, q, k, and T in the case to be described later), and the like. 
     More specifically, the header generation unit  15  has a function of generating encrypted session key and three types of header information. An encrypted session key is generated by encrypting a session key with a public key. 
     First header information is associated with an invalid user, and includes no encrypted session key. 
     Second header information is associated with an invalid user and a valid user. The second header information includes an encrypted session key obtained by encrypting a session key with a public key and a value based on user identification information of at least one of user systems which are permitted to decrypt the encrypted session key. Note that an encrypted session key can be decrypted on the basis of a decryption key. 
     Third header information is associated with a valid user, and includes an encrypted session key. Note that the third header information includes no value based on the user identification information of a valid user. Note, however, that the third header information may include a value based on the user identification information of a valid user. 
     Assume that the content distribution system  1  comprises various types of devices as needed, e.g., a communication interface for header information and encrypted contents, a device which stores contents, and a device which inputs contents or a decryption key generating device (not shown). When transmitting pieces of header information to a plurality of subgroups, the content distribution system  1  preferably transmits them while letting the subgroups share the common portions of the respective pieces of header information from the viewpoint of a reduction in data amount. However, the present invention is not limited to this, and the common portions need not be shared. 
     In this case, the decryption key generating device is designed to generate a decryption key unique to each user system. The decryption key generating device has a function of obtaining a tree structure by dividing a group to which a plurality of pieces of user identification information for individually identifying a plurality of user systems belong into subgroups, a function of assigning the respective subgroups different key generation polynomials and a common key generation polynomial, and a function of substituting the pieces of user identification information of the respective user systems into the key generation polynomials for the subgroups to which the respective pieces of user identification information belong and setting the obtained values as decryption keys unique to the respective user systems. 
     More specifically, a decryption key for a user is generated by substituting the user ID (positive integers selected from a predetermined range (e.g., consecutive numbers from 1 to n)) into key generation polynomials. In this case, as shown in  FIG. 15 , a total user set U is divided into a plurality of subgroups and the respective subgroups are assigned to the leaves of a tree structure.  FIG. 15  shows an example of a complete binary tree with a total leaf count of “8”. Let L be a total leaf count, D be a tree depth, and T be a tree structure including each node ID and information indicating which subgroup is assigned to which leaf. 
     As shown in  FIG. 15 , in the tree structure T, IDs (“0”, “1”, “2”, . . . , “13” in this case) are assigned to the respective nodes. Let U v  be user sets assigned to leaves having a given node v as an ancestor. Note that the term “ancestor” is not limited to a root node, and means a parent node, a grandparent node, a great-grand parent, or the like. Referring to  FIG. 15 , for example, U 8 =U 0 +U 1  where “+” represents the sum of. Referring to  FIG. 15 , the total user set U is divided into subgroups U 0 , . . . , U 7 . 
       FIG. 2  shows an example of subgroups U 1 , U 2 , and U 3 . As shown in  FIG. 3 , a user set is divided into a plurality of subgroups, and key generation polynomials are assigned to the respective subgroups in the following manner. 
     For example, the subgroup U 1  is assigned A 1 (x) and B(x). 
     The subgroup U 2  is assigned A 2 (x) and B(x). 
     The subgroup U 3  is assigned A 3 (x) and B(x). 
     Subsequently, likewise, a subgroup U i  is assigned A i (x) and B(x). 
     In this case, A i (x) is a key generation polynomial (individual key generation polynomial) unique to the subgroup U i  (i.e., a node i), and B(x) is a key generation polynomial (common key generation polynomial) common to the respective subgroups (i.e., the respective nodes). Note that the above manner of assignment is an example. For example, a key generation polynomial A i (x) may be randomly and uniquely assigned to a subgroup without being made to correspond to a subgroup number i, and a key generation polynomial A j (x) which is not assigned to any subgroups may exist. 
     In this manner, different key generation polynomials and a key generation polynomial common to the respective subgroups are assigned to the respective subgroups. A decryption key for a given user ID is generated by using the key generation polynomials assigned to the subgroups to which the user ID belongs. Note that the number of subgroups (excluding the root) to which the user ID belongs is represented by D. For example, in the case shown in  FIG. 15 , the user assigned to leaf 0 also belongs to the subgroups U 8  and U 12 , and a decryption key for the user ID is generated by using the key generation polynomials assigned to the respective subgroups. 
     With this operation, in contrast to the conventional black box tracking method in which both the key generation polynomials A i (x) and B i (x) are different key generation polynomials for a node, in the present invention, as will be described later, introducing key generation polynomials which allow black box tracking with respect to a smart unauthorized decryption unit even by making one key generation polynomial B(x) common to the respective nodes makes it possible to reduce the size of decryption key data to be held by the decryption unit. 
     Assume that the decryption key obtained by substituting the user ID assigned to the user system  2  into the key generation polynomials assigned to the subgroups to which the user ID belongs is supplied from the content distribution system  1  or a reliable third party to the user system  2  to be held therein in advance. 
     The grouping method exemplified by  FIGS. 15 ,  2 , and  3  is an example, and various grouping techniques can be used. 
     According to the above description, positive integers (e.g., consecutive numbers from 1 to n) selected from a predetermined range are used as user IDs or node IDs. However, user IDs need not be positive integers (for example, may be alphanumeric characters). A positive integer selected from a predetermined range may be uniquely assigned to a user ID constituted by alphanumeric characters or the like, and a decryption key can be calculated on the basis of the positive integer uniquely assigned to the user ID and corresponding key generation polynomials. The same applies to node IDs. 
     The decryption unit  20  mounted in the user system  2  will be described next. 
     As shown in  FIG. 1 , the decryption unit  20  includes a second storing unit  21 , session key decryption unit  22 , and content decryption unit  23 . 
     The second storing unit  21  is a memory which stores parameters necessary for decryption (parameters p, q, and k in the case to be described later), the ID of a subgroup to which the user system  2  belongs, the user ID assigned to the user system  2 , and a decryption key corresponding to the user ID. The session key decryption unit  22  can read information from the second storing unit  21 . Note that the decryption key is the value obtained by substituting the user ID into the key generation polynomials assigned to the subgroup to which the user ID belongs. 
     The session key decryption unit  22  has a function of, upon receiving an encrypted content and header information from the content distribution system  1 , acquiring (decrypting) a session key from the header information on the basis of the decryption key in the second storing unit  21 . 
     The content decryption unit  23  has a function of decrypting the encrypted content received from the content distribution system  1 , on the basis of the session key acquired (decrypted) by the session key decryption unit  22 . 
     Assume that the user system  2  comprises various types of devices as needed, e.g., a communication interface which receives encrypted contents and header information from the content distribution system  1 , a device which stores contents, a device which displays contents, and the like. 
     The tracking apparatus  30  will be described next with reference to  FIG. 4 . 
     The tracking apparatus  30  includes a public key storing unit  31 , header generation unit  32 , and control unit  33 . 
     In this case, the public key storing unit  31  is a memory which stores public keys, from which information can be read by the header generation unit  32 . 
     The header generation unit  32  has a function of generating header information on the basis of a public key and other necessary parameters (for example, parameters p, q, k, and T in the case to be described later) in accordance with the invalid user set designated by the control unit  33 , and a function of inputting header information to a test object. Note that a session key (information on which it is based) may be generated by the control unit  33  and designated for the header generation unit  32 , or may be generated by the header generation unit  32  and notified to the control unit  33 . In addition, as described above, header information includes a session key which is encrypted so as to be decrypted with a decryption key unique to a user system and a value based on each user identification information of each user system which is permitted to decrypt the encrypted session key. 
     The control unit (specifying means)  33  performs overall control of the tracking apparatus  30 , and has a function of specifying the unauthorized user or users of one or a plurality of user systems, which is the test object user system, on the basis of the relationship between header information generated by changing the number of user systems incapable of decryption and a decryption result acquired when the header information is input, under the control of the header generation unit  32 . 
     The control unit  33  has a function of designating (one or a plurality) user ID or user IDs to be invalidated (i.e., an invalid user set χ) with respect to the header generation unit  32 , a function of inputting the session key decrypted by a test object decryption unit  20 χ and checking whether a correct session key is obtained, and a function of repeating similar processing while changing an invalid user set and specifying the user ID of an unauthorized user by integrating the determination results. 
     Although the control unit  33  determines the decryption result of a session key obtained by the test object decryption unit  20 χ (whether a correct session key is obtained), the present invention is not limited to this. The control unit  33  may input the content encrypted with a session key to the test object decryption unit  20 χ in addition to header information, and determine whether the decryption result of the content obtained by the test object decryption unit  20 χ (whether the content is decrypted). 
     The tracking apparatus  30  may be mounted in, for example, the content distribution system  1 , or may be a apparatus independent of the content distribution system  1 . In addition, the tracking apparatus  30  may or may not have a function of being connected to the network  3 . 
     The operation of the network communication system having the above arrangement will be described next.  FIG. 5  is a flowchart for explaining the overall operation of the system. 
     Assume that a unique user ID is assigned to each user system  2 . 
     The content distribution system  1  generates a predetermined session key (single key) s (ST 1 ), and generates header information H(χ) by encrypting the session key in accordance with an invalid user set (ST 2 ). 
     The content distribution system  1  then encrypts a content with the session key s (ST 3 ), and broadcasts or multicasts the obtained encrypted content upon adding header information to it (ST 4 ). 
     Note that steps ST 2  and ST 3  may be executed in the order reverse to the above or may be simultaneously executed. If a session key is not changed for every decryption, step ST 1  may sometimes be omitted (a previous session key is used). 
     Upon receiving header information/encrypted content, each user system  2  decrypts the header information in accordance with a relationship with the invalid user set χ on the basis of the self user ID and the subgroup ID (ST 5 ). 
     In this case, if the user system  2  belongs to the invalid user set χ (ST 6 ), no session key can be acquired (ST 7 ). In contrast, if the user system does not belong to the invalid user set χ (ST 6 ), a session key is acquired (ST 8 ), and the encrypted content is decrypted with the session key (ST 9 ). 
     As will be described in detail later, the content distribution system  1  can flexibly invalidate a decryption key because it generates header information in accordance with the invalid user set χ. A decryption key is invalidated by encrypting a session key in a form in which no session key can be obtained by using the decryption key of an invalid user and the key can be decrypted with the decryption keys of users other than the invalid users. 
     Note that in broadcast-type content distribution, transmission data is generally encrypted with a single session key, and a key distribution method means a session key encryption/decryption method of encrypting a session key in a form that allows the key to be decrypted with the decryption key of each user. 
     A key generation phase to be executed in advance, an encryption phase in step ST 2 , and a decryption phase in steps ST 5  to ST 8  will be described in detail below. 
     First of all, parameters are defined. 
     Let n be the total number of users, and k be the maximum number of conspirators. 
     Assume that p and q are prime numbers, p−1 is divisible by q, and q is equal to or more than n+2k−1. 
     Assume that Zq={0, 1, . . . , q−1} and Zp*={1, . . . , p−1}. 
     Let Gq be a partial group of Zp* and also be a multiplicative group with q representing an order, and g be a generating element of Gq. 
     Assume that a user ID (user number) set (to be referred to as a user set hereinafter) is represented by U (U ⊂ Zq−{0}). Note that Zq−{0} indicates the value obtained by removing {0} from Zq. 
     Let χ be an invalid user set (a set of users whose decryption keys are invalidated). 
     The values of p, q, and g are disclosed. 
     Assume that calculation is to be performed on Zp*, unless otherwise specified. Note that Gq may be another group than the one specified above. For example, one can take as Gq an additive group of points of an elliptic curve over a finite field. This applies to other embodiments to be described later. 
     Key Generation Phase 
     This embodiment uses a binary tree structure with divided subgroups being assigned to leaves. More specifically, key generation polynomials are assigned to the respective nodes reaching from the root of the binary tree structure to a plurality of leaves through a plurality of nodes. With this, key generation polynomials are hierarchized into a multilevel structure. In the following case, a binary tree structure is used. However, the present invention is not limited to this. The number of branches is not specifically limited, and nodes with different numbers of branches may exist in one tree structure. In addition, the numbers of nodes (the numbers of levels) reaching from the root to leaves need not be the same with respect to all the leaves, and leaves located at different levels may exist. 
     A public key and decryption key generation processing in a user system corresponding to each user ID will be described below. Note that the flowchart of  FIG. 16  shows decryption key generation processing in a user system corresponding to each user ID. 
     The content distribution system  1  divides the user set U into L or less partial sets (subgroups) having no common element (ST 101 ). For the sake of simplicity, assume that the number of divided subgroups is represented by L, and L is a number represented by the power of two. The content distribution system  1  generates a complete binary tree whose total number of leaves is given by L and the tree depth is given by D=log 2 L, and L subgroups are assigned to different leaves (ST 102 ). Let T be a tree structure including information indicating which subgroup is assigned to which leaf and each node ID. T is disclosed. 
     Parameters a 0 , . . . , a 2k−1 , b 0 , . . . , b 2k−1  on which a public key is based are randomly selected from Zq. In addition, with regard to each element i belonging to N, c i  and λ i  are randomly selected from Zq. 
     The content distribution system  1  then calculates a public key e. The pubic key e is given by
 
 e =( g, g   λ     0     , . . . , g   λ     2L−3     , g   a     0     , . . . , g   a     2k−1     , g   c     0     , . . . , g   c     2L−3   )   (1)
 
     In the tree structure T, let N be a set of the IDs of nodes and leaves excluding the root. For the sake of simplicity, N in the complete binary tree whose total number of leaves is given by L is N={0, . . . , 2L−3}. In the case shown in  FIG. 15 , N={0, . . . 13}. 
     The nodes/leaves (v) of the tree structure T are assigned an individual key generation polynomials A v (x), which differ from each other for the respective root/nodes/leaves, and the common key generation polynomial B(x) common to the root/nodes/leaves (ST 103 ). Note that the common key generation polynomial B(x) common to the root/nodes/leaves need not be assigned to each root/node/leaf. 
     In addition, each subgroup is assigned an individual key generation polynomial which is assigned to a leaf assigned to the subgroup and its ancestor node(s) (ST 104 ). 
     Let U v  be a user set assigned to a leaf having a given node v as an ancestor. Referring to  FIG. 15 , for example, U 8 =U 0 +U 1  where “+” represents the sum of. 
     Lastly, the content distribution system  1  calculates the decryption key of a user ID=u which belongs to the user set (partial set) U v  assigned to a leaf having the node v as an ancestor node by substituting x=u into the key generation polynomials A v (x) and B(x) (ST 105 ). In this case, the generation polynomials A v (x) and B(x) are assigned to the partial set UV to which the user u belongs, and is given by 
     
       
         
           
             
               
                 
                   
                     
                       
                         A 
                         v 
                       
                       ⁡ 
                       
                         ( 
                         x 
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           0 
                         
                         
                           
                             2 
                             ⁢ 
                             k 
                           
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                         
                           ( 
                           
                             
                               a 
                               
                                 v 
                                 , 
                                 i 
                               
                             
                             - 
                             
                               
                                 λ 
                                 v 
                               
                               ⁢ 
                               
                                 b 
                                 i 
                               
                             
                           
                           ) 
                         
                         ⁢ 
                         
                           x 
                           i 
                         
                         ⁢ 
                         mod 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         q 
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       B 
                       ⁡ 
                       
                         ( 
                         x 
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           0 
                         
                         
                           
                             2 
                             ⁢ 
                             k 
                           
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                         
                           b 
                           i 
                         
                         ⁢ 
                         
                           x 
                           i 
                         
                         ⁢ 
                         mod 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         q 
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       a 
                       
                         v 
                         , 
                         i 
                       
                     
                     = 
                     
                       { 
                       
                         
                           
                             
                               
                                 a 
                                 i 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   i 
                                   ≠ 
                                   
                                     v 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     mod 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     2 
                                     ⁢ 
                                     k 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                         
                           
                             
                               
                                 c 
                                 v 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   i 
                                   = 
                                   
                                     v 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     mod 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     2 
                                     ⁢ 
                                     k 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     Letting U i  be a user set assigned to a leaf having a given node i on the tree structure as an ancestor and A i (x) be an individual key generation polynomial assigned to the node i, a decryption key generation polynomial for the user set U i  is given by, for example,
 
 A   i ( x )+λ i   B ( x ) =a   0   +c   i   x+a   2   x   2   + . . . +a   2k−1   x   2k−1  
 
Letting U j  be a user set assigned to a leaf having a node j different from the node i on the tree structure as an ancestor and A j (x) be an individual key generation polynomial assigned to the node j, a decryption key generation polynomial for the user set U j  is given by, for example,
 
 A   j ( x )+λ j   B ( x ) =a   0   +c   j   x+a   2   x   2   + . . . +a   2k−1   x   2k−1  
 
     As described above, in the decryption key generation polynomial for the user set U i  assigned to a leaf having the node i as an ancestor and the decryption key generation polynomial for the user set U j  assigned to a leaf having the node j as an ancestor, the coefficients with the same degrees excluding one or a plurality of coefficients (e.g., c i  and c j ) unique to the root/nodes/leaves on the tree structure are constant regardless of i and j. 
     That is, at least one of the linear sums of coefficients with the same degrees in the individual key generation polynomial A i (x) assigned to the node i and the common key generation polynomial B(x) common to the root/nodes/leaves is a coefficient unique to the root/nodes/leaves on the tree structure, and other coefficients, i.e., “mth degree coefficients of A i (x)”+“mth degree coefficients of λ i B(x)” are constant regardless of i and j. 
     A decryption key for user ID=u belonging to the user set U i  assigned to a leaf having the node i as an ancestor is obtained by substituting “u” into “x” of the above decryption key polynomial A i (x)+λ i B(x). 
     In the above case, when the maximum number of conspirators is set to k, the degree of a key generation polynomial is preferably equal to or more than 2k−1 from the viewpoint of safety, and hence is set to 2k−1. However, the degree of the key generation polynomial is not limited to this and may be set to an arbitrary value. In addition, the degree of the key generation polynomial A i (x) assigned to the node i may differ from the degree of the key generation polynomial A j (x) assigned to the node j, and the degrees of the key generation polynomials A i (x) and B(x) may differ from each other. This applies to other embodiments to be described later. 
     Letting d u  be a decryption key for a user with user ID=u, d u  is given by
 
 d   u ={( u,v,A   v ( u ), B ( u ))| v εN,u εU   v }  (3)
 
     Referring to  FIG. 15 , if the user u is assigned to leaf 0, d u  is given by
 
 d   u ={( u, 0 ,A   0 ( u ), B ( u )),( u, 8, A   8 ( u ), B ( u )),( u, 12, A   12 ( u ), B ( u ))}  (4)
 
     As shown in  FIG. 12 , processing in the above key generation phase may be performed by a reliable third party apparatus other than the content distribution system  1 . In expression (4), although the individual key generation polynomial assigned to the root node (node v=“14”) is not assigned to the subgroup of leaf 0, the individual key generation polynomial assigned to the root may be assigned to the subgroup of leaf 0. In this case, a decryption key (u, 14, A 14 (u), B(u)) using the key generation polynomial for the root is added to expression (4) indicating the decryption key for the user with user ID=u. In addition, there may be one or more nodes to which no individual key generation polynomial is assigned. In this case, it is unnecessary to generate the corresponding c i  and λ i  in the calculation of the public key e. These apply to each embodiment described below. 
     Encryption Phase 
     The session key generation unit  13  of the content distribution system  1  randomly selects the session key s from Gq. The header generation unit  15  then repeats the following processing for j by setting integer j=0 and substituting one of the node IDs of the child nodes of the root of the tree structure T into v 0 . 
     If v j  is a leaf ID, the processing is terminated upon substituting the ID of a brother leaf of v j  into v j+1 . Otherwise, one of the child nodes of the brother node of v j  is selected, and the node ID is substituted into v j+1 . Then, j is incremented by one. 
     After the above processing, log 2 L+1 node IDs including two leaf IDs are selected. Note that in the following description, log 2 L is sometimes written as β. Referring to  FIG. 15 , four node IDs (e.g., 0, 1, 9, and 13) are selected. 
     The header generation unit  15  then selects random numbers r 0  and r 1  and calculates Hv 0 , . . . , Hv β  by repeating the following processing for 0≦j≦log 2 L (=β) (steps ST 2 - 1  to ST 2 - 8  in  FIG. 6 ) 
     The header generation unit  15  determines whether the product set of the invalid user set χ and Uv j  is an empty set (ST 2 - 2 ). 
     A case wherein the product set of χ and Uv j  is an empty set will be described below. This is a case wherein not all users belonging to Uv j  are invalid users. For example, U 3  in  FIG. 2  corresponds to this case. The header generation unit  15  calculates Hv j  according to expression (5) (ST 2 - 3 ). 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           H 
                           
                             v 
                             j 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           ( 
                           
                             
                               h 
                               
                                 v 
                                 j 
                               
                             
                             , 
                             
                               h 
                               
                                 v 
                                 j 
                               
                               ′ 
                             
                             , 
                             
                               h 
                               
                                 
                                   v 
                                   j 
                                 
                                 , 
                                 0 
                               
                             
                             , 
                             … 
                             ⁢ 
                             
                                 
                             
                             , 
                             
                               h 
                               
                                 v 
                                 j 
                               
                             
                             , 
                             
                               y 
                               
                                 v 
                                 j 
                               
                             
                             , 
                             … 
                             ⁢ 
                             
                                 
                             
                             , 
                             
                               h 
                               
                                 
                                   v 
                                   j 
                                 
                                 , 
                                 
                                   
                                     2 
                                     ⁢ 
                                     k 
                                   
                                   - 
                                   1 
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           ( 
                           
                             
                               g 
                               r 
                             
                             , 
                             
                               g 
                               
                                 
                                   λ 
                                   
                                     v 
                                     j 
                                   
                                 
                                 ⁢ 
                                 r 
                               
                             
                             , 
                             
                               g 
                               
                                 ra 
                                 0 
                               
                             
                             , 
                             … 
                             ⁢ 
                             
                                 
                             
                             , 
                             
                               s 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 g 
                                 
                                   rc 
                                   
                                     v 
                                     j 
                                   
                                 
                               
                             
                             , 
                             … 
                             ⁢ 
                             
                                 
                             
                             , 
                             
                               g 
                               
                                 ra 
                                 
                                   
                                     2 
                                     ⁢ 
                                     k 
                                   
                                   - 
                                   1 
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                   
                     
                       
                         
                           y 
                           
                             v 
                             j 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           
                             v 
                             j 
                           
                           ⁢ 
                           mod 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           2 
                           ⁢ 
                           k 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
     For example, only determination in steps ST 2 - 2 , ST 2 - 4 , and ST 2 - 6  may be performed in advance. If NO is obtained in step ST 2 - 4  (NO in step ST 2 - 4 ), either r 0  or r 1  may be substituted into r. Otherwise, r 0  is substituted into r. 
     If it is determined in step ST- 2  that the product set of the invalid user set χ and Uv j  is not an empty set, the header generation unit  15  determines whether the product set of χ and Uv j  is Uv j  (ST 2 - 4 ). 
     A case wherein the product set of χ and Uv j  is Uv j  will be described below. This is a case wherein all the users belonging to Uv j  are invalid users. For example, U 1  in  FIG. 2  corresponds to this case. The header generation unit  15  substitutes either r 0  or r 1  into r and selects a random number z vj . In step ST 2 - 5 , if a user set other than Uv j  includes no invalid user, i.e., it is determined that case wherein NO is obtained in step ST 2 - 4  (NO in step ST 2 - 4 ) does not exist in a user set other than Uv j , Hv j  is calculated according to expression (6) (ST 2 - 5 ).
 
 H   v     j   =( g   r   , g   λ     vj     r   , g   ra     0     , . . . , g   z     vj     , . . . , g   ra     2k−1   )   (6)
 
     If the user set other than Uv j  includes an invalid user, i.e., a case wherein NO is obtained in step ST 2 - 4  (NO in step ST 2 - 4 ) exists in the user set other than Uv j , Hv j  is calculated according to expression (7) (ST 2 - 5 ). 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           H 
                           
                             v 
                             j 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           ( 
                           
                             
                               h 
                               
                                 v 
                                 j 
                               
                             
                             , 
                             
                               h 
                               
                                 v 
                                 j 
                               
                               ′ 
                             
                             , 
                             
                               h 
                               
                                 
                                   v 
                                   j 
                                 
                                 , 
                                 0 
                               
                             
                             , 
                             … 
                             ⁢ 
                             
                                 
                             
                             , 
                             
                               h 
                               
                                 
                                   v 
                                   j 
                                 
                                 , 
                                 
                                   y 
                                   
                                     v 
                                     j 
                                   
                                 
                               
                             
                             , 
                             … 
                             ⁢ 
                             
                                 
                             
                             , 
                             
                               h 
                               
                                 
                                   v 
                                   j 
                                 
                                 , 
                                 
                                   
                                     2 
                                     ⁢ 
                                     k 
                                   
                                   - 
                                   1 
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           { 
                           
                             
                               
                                 
                                   ( 
                                   
                                     
                                       g 
                                       
                                         r 
                                         0 
                                       
                                     
                                     , 
                                     
                                       g 
                                       
                                         
                                           λ 
                                           
                                             v 
                                             j 
                                           
                                         
                                         ⁢ 
                                         
                                           r 
                                           0 
                                         
                                       
                                     
                                     , 
                                     
                                       g 
                                       
                                         
                                           r 
                                           0 
                                         
                                         ⁢ 
                                         
                                           a 
                                           0 
                                         
                                       
                                     
                                     , 
                                     … 
                                     ⁢ 
                                     
                                         
                                     
                                     , 
                                     
                                       g 
                                       
                                         z 
                                         
                                           v 
                                           j 
                                         
                                       
                                     
                                     , 
                                     … 
                                     ⁢ 
                                     
                                         
                                     
                                     , 
                                     
                                       g 
                                       
                                         
                                           r 
                                           0 
                                         
                                         ⁢ 
                                         
                                           a 
                                           
                                             
                                               2 
                                               ⁢ 
                                               k 
                                             
                                             - 
                                             1 
                                           
                                         
                                       
                                     
                                   
                                   ) 
                                 
                               
                               
                                 
                                   ( 
                                   
                                     r 
                                     = 
                                     
                                       r 
                                       0 
                                     
                                   
                                   ) 
                                 
                               
                             
                             
                               
                                 
                                   ( 
                                   
                                     
                                       
                                         
                                           
                                             g 
                                             
                                               r 
                                               1 
                                             
                                           
                                           , 
                                           
                                             g 
                                             
                                               
                                                 λ 
                                                 
                                                   v 
                                                   j 
                                                 
                                               
                                               ⁢ 
                                               
                                                 r 
                                                 1 
                                               
                                             
                                           
                                           , 
                                           
                                             
                                               g 
                                               
                                                 L 
                                                 0 
                                               
                                             
                                             ⁢ 
                                             
                                               g 
                                               
                                                 
                                                   r 
                                                   1 
                                                 
                                                 ⁢ 
                                                 
                                                   a 
                                                   0 
                                                 
                                               
                                             
                                           
                                           , 
                                           … 
                                           ⁢ 
                                           
                                               
                                           
                                           , 
                                         
                                       
                                     
                                     
                                       
                                         
                                           
                                             g 
                                             
                                               z 
                                               
                                                 v 
                                                 j 
                                               
                                             
                                           
                                           , 
                                           … 
                                           ⁢ 
                                           
                                               
                                           
                                           , 
                                           
                                             
                                               g 
                                               
                                                 L 
                                                 
                                                   
                                                     2 
                                                     ⁢ 
                                                     k 
                                                   
                                                   - 
                                                   1 
                                                 
                                               
                                             
                                             ⁢ 
                                             
                                               g 
                                               
                                                 
                                                   r 
                                                   1 
                                                 
                                                 ⁢ 
                                                 
                                                   a 
                                                   
                                                     
                                                       2 
                                                       ⁢ 
                                                       k 
                                                     
                                                     - 
                                                     1 
                                                   
                                                 
                                               
                                             
                                           
                                         
                                       
                                     
                                   
                                   ) 
                                 
                               
                               
                                 
                                   ( 
                                   
                                     r 
                                     = 
                                     
                                       r 
                                       1 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
     If neither is the case (the result in step ST 2 - 4  is unknown at this point of time), r 0  is substituted into r, and Hv j  is calculated according to expression (6) (ST 2 - 5 ). 
     Note that the case represented by expressions (6) and (7) is a case wherein when the decryption keys of all the user systems  2  belonging to a specific subgroup Uv j  are to be invalidated, a value c vj  unique to the specific subgroup Uv j  in the header information Hv j  is set to a value z vj  different from a correct value. However, the present invention is not limited to this. For example, with regard to a subgroup to be invalidated, information h vj,yvj  which is an element unique to the specific subgroup Uv j  in the header information Hv j  and based on which a session key is calculated may be deleted (inhibited to be written). 
     With this operation as well, since information based on which a session key is calculated is not included in header information for a subgroup to be invalidated, a correct session key cannot be obtained, whereas a correct session key can be obtained for other subgroups. 
     A case wherein NO is obtained in step ST 2 - 4  (NO in step ST 2 - 4 ) will be described. This is a case wherein at least one of the users belonging to Uv j  is not an invalid user, and at least one of the users is an invalid user. For example, this case corresponds to U 2  in  FIG. 2 . 
     As shown in  FIG. 7  (d=0), the header generation unit  15  obtains a partial set {x 1 , . . . , x m } by removing the invalid user set χ from Uv j . For example, in the case of U 2  in  FIG. 2 , {x 1 , . . . , x 10 }={31, . . . , 40} (m=10). 
     If 2k−m−1&gt;0, the header generation unit  15  randomly selects x m+1 , . . . , x 2k−1  from Zq−(U+{0}). Note that Zq−(U+{0}) means the value obtained by removing the sum of sets U and {0} from Zq. 
     The header generation unit  15  obtains elements L 0 , . . . , L 2k−1  of Zq satisfying expression (8) with respect to 1≦t≦2k−1. 
     
       
         
           
             
               
                 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         0 
                       
                       
                         
                           2 
                           ⁢ 
                           k 
                         
                         - 
                         1 
                       
                     
                     ⁢ 
                     
                       
                         L 
                         i 
                       
                       ⁢ 
                       
                         X 
                         t 
                         i 
                       
                     
                   
                   = 
                   
                     0 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     mod 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     q 
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
     The header generation unit  15  then calculates Hv j  by substituting r 1  into r according to expression (9) (ST 2 - 6 ). 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           H 
                           
                             v 
                             j 
                           
                         
                         = 
                           
                         ⁢ 
                         
                           ( 
                           
                             
                               h 
                               
                                 v 
                                 j 
                               
                             
                             , 
                             
                               h 
                               
                                 v 
                                 j 
                               
                               ′ 
                             
                             , 
                             
                               h 
                               
                                 
                                   v 
                                   j 
                                 
                                 , 
                                 0 
                               
                             
                             , 
                             … 
                             ⁢ 
                             
                                 
                             
                             , 
                             
                               h 
                               
                                 
                                   v 
                                   j 
                                 
                                 , 
                                 
                                   y 
                                   
                                     v 
                                     j 
                                   
                                 
                               
                             
                             , 
                             … 
                             ⁢ 
                             
                                 
                             
                             , 
                             
                               h 
                               
                                 
                                   v 
                                   j 
                                 
                                 , 
                                 
                                   
                                     2 
                                     ⁢ 
                                     k 
                                   
                                   - 
                                   1 
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           ( 
                           
                             
                               g 
                               r 
                             
                             , 
                             
                               g 
                               
                                 
                                   λ 
                                   
                                     v 
                                     j 
                                   
                                 
                                 ⁢ 
                                 r 
                               
                             
                             , 
                             
                               
                                 g 
                                 
                                   L 
                                   o 
                                 
                               
                               ⁢ 
                               
                                 g 
                                 
                                   ra 
                                   0 
                                 
                               
                             
                             , 
                             … 
                             ⁢ 
                             
                                 
                             
                             , 
                             
                               s 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 g 
                                 
                                   L 
                                   
                                     y 
                                     
                                       v 
                                       j 
                                     
                                   
                                 
                               
                               ⁢ 
                               
                                 g 
                                 
                                   rc 
                                   
                                     v 
                                     j 
                                   
                                 
                               
                             
                             , 
                             … 
                             ⁢ 
                             
                                 
                             
                             , 
                             
                               
                                 g 
                                 
                                   L 
                                   
                                     
                                       2 
                                       ⁢ 
                                       k 
                                     
                                     - 
                                     1 
                                   
                                 
                               
                               ⁢ 
                               
                                 g 
                                 
                                   ra 
                                   
                                     
                                       2 
                                       ⁢ 
                                       k 
                                     
                                     - 
                                     1 
                                   
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
     When decryption keys for one or more user systems  2  of all the user systems belonging to a specific subgroups are to be invalidated, the header generation unit  15  may exclude the user ID of the user system  2  to be invalidated from a partial set {x 1 ˜x m } as a set of users who are not invalid users of the user set belonging to Uv j . 
     Note that the value {L 0 , . . . , L 2k−1 } based on the partial set is the first vector satisfying the relation represented by the following expression in which the inner product of the first vector and the second vector is “0” when the second vector is obtained by using an ID {x 1 , . . . , x m } of each user belonging to the partial set as a variable of a (2k−1)th-degree polynomial.
 
( L   0   ,L   1   ,L   2   , . . . ,L   2k−1 )·(1 ,x   w   ,x   w   2   , . . . ,x   w   2k−1 ) =0 mod  q  
 
     for x w =x 1  to x m    
     Although the above case is based on the assumption of m&lt;2k, the value of m can be permitted within the range of m&lt;(degree of key generation polynomial+1) by increasing the degree of the key generation polynomial. 
     In the above case, even if a case wherein NO is obtained in step ST 2 - 4  (NO in step ST 2 - 4 ) has occurred two or more times, r=r 1  is set. However, the present invention is not limited to this. Three or more random numbers to be substituted into r may be prepared, and a different random number may be substituted into r every time a case wherein NO is obtained in step ST 2 - 4  occurs. This applies to other embodiments to be described later. 
     Hv 0 , . . . , Hv β  obtained by the above repetitive processing are set as a header H(χ) (ST 2 - 9 ). In this case, since a header can be calculated by using the public key e, anyone can manage the content distribution system  1 . 
     In addition, the transmission overhead can be further reduced by grouping identical elements of the elements constituting Hv 0 , . . . , Hv β  obtained by the above repetitive processing into one and sharing it in the header H(χ). This applies to each embodiment described below. 
     In the above case, log 2 L+1 nodes are selected. However, the present invention is not limited to this, and nodes may be selected by the method described below. 
     The method will be described with reference to  FIG. 14 . First of all, the header generation unit  15  sets a root R as a node v j  (ST 31 ). It is determined whether each of all users having the node v j  as an ancestor corresponds to any one of following cases (1) to (3) (ST 32 ): (1) a case wherein all the users are invalid users, (2) a case wherein all the users are valid users, and (3) a case wherein the number of valid users is equal to or more than 1 and equal to or less than 2k−1. 
     The header generation unit  15  calculates the header Hv j  on the basis of the determination result (ST 33 ). In each case, the header Hv j  is calculated in the same manner as described above. 
     If a given user does not correspond to any one of cases (1) to (3) (NO in step ST 32 ), a child node which is a child node of the node v j  and has not been tested is set as the node v j  (ST 34 ), and the above processing is repeated. Note that a leaf may be set as the node v j  . 
     It is determined whether Hv j  is generated for all valid user sets (ST 35 ). If Hv j  is generated for all the valid user sets, the generated (a plurality of) Hv j  are set as headers H(χ) (ST 36 ). Otherwise (NO in step ST 35 ), one of untested nodes which is located nearest to the root R, i.e., the top-level node, is set as the node v j  (ST 37 ), and the above processing is repeated. Note that a leaf may be set as the node v j . 
     The above description has exemplified the method of selecting a higher-level node as much as possible to further reduce the header size. However, the present invention is not limited to this node selection method. For example, the following selection method can also be used. 
     Referring to  FIG. 13 , assume that all the users belonging to U 0  are invalid users, k users of the users belonging to U 1  are valid users, all the users belonging to U 2  are valid users, and all the users belonging to U 3  are valid users. In this case, a node j and a node v are selected and H(x)=(H j , H v ) according to the flowchart of  FIG. 4 . In this case, the node j is the parent node of a leaf i (corresponding to U 0 ) and leaf w (corresponding to U 1 ). The node v is the parent node of a leaf corresponding to U 2  and a leaf corresponding to U 3 . However, the present invention is not limited to this. It does not matter how nodes are selected as long as the condition in step S 32  is satisfied. For example, the leaf i, leaf w, and node v may be selected. In this case, H(x)=(H i , H w , H v ). As another example, the leaf j, leaf w, and node v may be selected. In this case, the header, H(x)=(H j , H w , H v ), is constructed in such a way that the valid users belonging to U 1  can decrypt at least one of H j  and H w . That various node selection methods can be used in the same manner as in other embodiments described later. 
     Decryption Phase 
     Consider a user u belonging to the partial set Uv j . As shown in  FIG. 8 , upon receiving the header H(χ) (ST 5 - 1 ), the user system  2  with user ID=u calculates expression (10) by using Hv j . 
     
       
         
           
             
               
                 
                   
                     
                       
                         s 
                         = 
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 
                                   h 
                                   
                                     
                                       v 
                                       j 
                                     
                                     , 
                                     0 
                                   
                                 
                                 × 
                                 … 
                                 × 
                                 
                                   h 
                                   
                                     
                                       v 
                                       j 
                                     
                                     , 
                                     
                                       
                                         2 
                                         ⁢ 
                                         k 
                                       
                                       - 
                                       1 
                                     
                                   
                                   
                                     u 
                                     
                                       
                                         2 
                                         ⁢ 
                                         k 
                                       
                                       - 
                                       1 
                                     
                                   
                                 
                               
                               
                                 
                                   h 
                                   
                                     v 
                                     j 
                                   
                                   
                                     
                                       A 
                                       
                                         v 
                                         j 
                                       
                                     
                                     ⁡ 
                                     
                                       ( 
                                       u 
                                       ) 
                                     
                                   
                                 
                                 ⁢ 
                                 
                                   h 
                                   
                                     v 
                                     j 
                                   
                                   
                                     ′ 
                                     
                                       B 
                                       ⁡ 
                                       
                                         ( 
                                         u 
                                         ) 
                                       
                                     
                                   
                                 
                               
                             
                             ) 
                           
                           
                             1 
                             / 
                             
                               u 
                               
                                 y 
                                 
                                   v 
                                   j 
                                 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 
                                   s 
                                   
                                     u 
                                     
                                       
                                         v 
                                         j 
                                       
                                       ⁢ 
                                       mod 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       2 
                                       ⁢ 
                                       k 
                                     
                                   
                                 
                                 ⁢ 
                                 
                                   g 
                                   
                                     r 
                                     ⁢ 
                                     
                                       
                                         ∑ 
                                         
                                           i 
                                           = 
                                           0 
                                         
                                         
                                           
                                             2 
                                             ⁢ 
                                             k 
                                           
                                           - 
                                           1 
                                         
                                       
                                       ⁢ 
                                       
                                         a 
                                         
                                           
                                             v 
                                             j 
                                           
                                           , 
                                           
                                             i 
                                             
                                               u 
                                               i 
                                             
                                           
                                         
                                       
                                     
                                   
                                 
                               
                               
                                 g 
                                 
                                   r 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         
                                           A 
                                           
                                             v 
                                             j 
                                           
                                         
                                         ⁡ 
                                         
                                           ( 
                                           u 
                                           ) 
                                         
                                       
                                       + 
                                       
                                         
                                           λ 
                                           
                                             v 
                                             j 
                                           
                                         
                                         ⁢ 
                                         
                                           B 
                                           ⁡ 
                                           
                                             ( 
                                             u 
                                             ) 
                                           
                                         
                                       
                                     
                                     ) 
                                   
                                 
                               
                             
                             ) 
                           
                           
                             1 
                             / 
                             
                               u 
                               
                                 y 
                                 
                                   v 
                                   j 
                                 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               s 
                               
                                 u 
                                 
                                   
                                     v 
                                     j 
                                   
                                   ⁢ 
                                   mod 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   2 
                                   ⁢ 
                                   k 
                                 
                               
                             
                             ) 
                           
                           
                             1 
                             / 
                             
                               u 
                               
                                 y 
                                 
                                   v 
                                   j 
                                 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
     The result obtained by decrypting a session key from header information will be briefly described. 
     The decryption result obtained by the session key decryption unit  22  of the user system  2  is branched depending on whether the product set of the invalid user set χ and Uv j  is an empty set (ST 5 - 2 ), the product set of the invalid user set χ and Uv j  is Uv j  (ST 5 - 4 ), or otherwise (ST 6 ). Note that the session key decryption unit  22  of the user system  2  calculates Hv j  according to expression (10) in a decryption sequence common to all the cases without performing this determination. 
     A case wherein the product set of χ and Uv j  is an empty set (YES in step ST 5 - 2 ) will be described. This case is a case wherein all the users belonging to Uv j  are not invalid users, and corresponds to, for example, U 3  in  FIG. 2 . The session key decryption unit  22  performs calculation according to expression (10) (ST 5 - 3 ), and obtains the session key s (ST 8 ). 
     A case wherein the product set of χ and Uv j  is Uv j  (YES in step ST 5 - 4 ) will be described. This case is a case wherein all the users belonging to Uv j  are invalid users, and corresponds to, for example, U 1  in  FIG. 2 . In this case, since the information h vj,yvj  which is an element unique to the specific subgroup Uv j  in the header information Hv j  and based on which a session key is calculated is a wrong value (ST 5 - 5 ), a correct session key cannot be acquired (ST 7 ). 
     A case other than the above cases will be described below (NO in step ST 5 - 4 ). This case is a case wherein at least one of the users belonging to Uv j  is not an invalid user, and at least one of the users is an invalid user, and corresponds to U 2  in  FIG. 2 . 
     The session key s is represented by 
     
       
         
           
             
               
                 
                   
                     
                       
                         s 
                         = 
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 
                                   h 
                                   
                                     
                                       v 
                                       j 
                                     
                                     , 
                                     0 
                                   
                                 
                                 × 
                                 … 
                                 × 
                                 
                                   h 
                                   
                                     
                                       v 
                                       j 
                                     
                                     , 
                                     
                                       
                                         2 
                                         ⁢ 
                                         k 
                                       
                                       - 
                                       1 
                                     
                                   
                                   
                                     u 
                                     
                                       
                                         2 
                                         ⁢ 
                                         k 
                                       
                                       - 
                                       1 
                                     
                                   
                                 
                               
                               
                                 
                                   h 
                                   
                                     v 
                                     j 
                                   
                                   
                                     
                                       A 
                                       
                                         v 
                                         j 
                                       
                                     
                                     ⁡ 
                                     
                                       ( 
                                       u 
                                       ) 
                                     
                                   
                                 
                                 ⁢ 
                                 
                                   h 
                                   
                                     v 
                                     j 
                                   
                                   
                                     ′ 
                                     
                                       B 
                                       ⁡ 
                                       
                                         ( 
                                         u 
                                         ) 
                                       
                                     
                                   
                                 
                               
                             
                             ) 
                           
                           
                             1 
                             / 
                             
                               u 
                               
                                 y 
                                 
                                   v 
                                   j 
                                 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 
                                   s 
                                   
                                     u 
                                     
                                       
                                         v 
                                         j 
                                       
                                       ⁢ 
                                       mod 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       2 
                                       ⁢ 
                                       k 
                                     
                                   
                                 
                                 ⁢ 
                                 
                                   g 
                                   
                                     
                                       ∑ 
                                       
                                         i 
                                         = 
                                         0 
                                       
                                       
                                         
                                           2 
                                           ⁢ 
                                           k 
                                         
                                         - 
                                         1 
                                       
                                     
                                     ⁢ 
                                     
                                       
                                         ( 
                                         
                                           
                                             L 
                                             i 
                                           
                                           + 
                                           
                                             
                                               r 
                                               1 
                                             
                                             ⁢ 
                                             
                                               a 
                                               
                                                 
                                                   v 
                                                   j 
                                                 
                                                 , 
                                                 i 
                                               
                                             
                                           
                                         
                                         ) 
                                       
                                       ⁢ 
                                       
                                         u 
                                         i 
                                       
                                     
                                   
                                 
                               
                               
                                 g 
                                 
                                   r 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         
                                           A 
                                           
                                             v 
                                             j 
                                           
                                         
                                         ⁡ 
                                         
                                           ( 
                                           u 
                                           ) 
                                         
                                       
                                       + 
                                       
                                         
                                           λ 
                                           
                                             v 
                                             j 
                                           
                                         
                                         ⁢ 
                                         
                                           B 
                                           ⁡ 
                                           
                                             ( 
                                             u 
                                             ) 
                                           
                                         
                                       
                                     
                                     ) 
                                   
                                 
                               
                             
                             ) 
                           
                           
                             1 
                             / 
                             
                               u 
                               
                                 y 
                                 
                                   v 
                                   j 
                                 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               s 
                               
                                 u 
                                 
                                   
                                     v 
                                     j 
                                   
                                   ⁢ 
                                   mod 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   2 
                                   ⁢ 
                                   k 
                                 
                               
                             
                             ) 
                           
                           
                             1 
                             / 
                             
                               u 
                               
                                 y 
                                 
                                   v 
                                   j 
                                 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
     If the user u is an invalid user (YES in step ST 6 ), since expression (12) does not hold, the session key s cannot be obtained (ST 7 ). 
     
       
         
           
             
               
                 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         0 
                       
                       
                         
                           2 
                           ⁢ 
                           k 
                         
                         - 
                         1 
                       
                     
                     ⁢ 
                     
                       
                         L 
                         i 
                       
                       ⁢ 
                       
                         u 
                         i 
                       
                     
                   
                   = 
                   
                     0 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     mod 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     q 
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
     Tracking Phase 
     The following is an example of the sequence of a tracking algorithm. The tracking apparatus  30  and an unauthorized user as a tracking target will be briefly described first. When a pirate decryption unit (unauthorized decryption unit) is confiscated, the tracking apparatus  30  is used to specify an unauthorized user (whose user ID), who has illegally produced the pirate decryption unit, by black box tracking. 
     A pirate decryption unit is either produced based on only one authorized decryption unit or produced based on a plurality of authorized decryption units. The unauthorized users of the decryption units in the latter case will be referred to as conspirators. 
     A pirate decryption unit produced based on only one decryption unit can use the same decryption key as that of the decryption unit. A pirate decryption unit produced based on a plurality of decryption units can use each of the same decryption keys as those of the plurality of decryption units. In the latter case, a session key can be obtained unless all the decryption keys for the conspirators are invalidated. 
     Even in a case wherein a plurality of unauthorized users are in conspiracy with each other, the tracking apparatus  30  can execute a test more quickly than in the prior art in which nCk tests are executed, and specifies one or more unauthorized users. 
     Sequence Example 
     A concrete tracking algorithm sequence includes various variations, and is not limited to the following.  FIG. 9  is a flowchart for explaining the operation of the tracking apparatus in a tracking phase. 
     When a pirate decryption unit D is confiscated, an unauthorized user is specified by the following processing. 
     Assume that in the tree structure T, 2k users belongs to each leaf, the respective leaf IDs are assigned 1, . . . , t from the leftmost leaf, and elements of partial sets U 1 , . . . , U t  are labeled according to expression (13).
 
 U   1   ={u   1   , . . . , u   2k   }, U   2   ={u   2k+1   , . . . , u   4k   }     U   t   ={u   n−2k+1   , . . . , u   n }  (13)
 
Note that the number of users belonging to each partial set is not necessarily equal to 2k. For example, the number of users belonging to U 1  may be different from the number of users belonging to U 2 . This applies to each embodiment described below.
 
     The tracking apparatus  30  executes the following processing for j=1, . . . , n (n: the total number of users, j: the user number) (ST 11  to ST 21 ). The control unit  33  repeats the following processing m times with normal decryption count C j =0 and test count z=1 for the same invalid user set χ (ST 12 ). 
     The control unit  33  sets invalid user set χ={u 1 , . . . , u j } (ST 13 ), controls the header generation unit  32 , and generates the header H(χ) (ST 14 ). Note that a header generation method to be used is the same as that in the encryption phase, a random number is randomly selected for every operation. In node selection, log 2 L+1 nodes v j  which satisfy both conditions (1) and (2) given below are selected. (1) The number of elements of a set obtained by removing χ from Uv j  is equal to or more than “1” and is less than “2k”, the product set of Uv j  and χ is an empty set, or the product set of Uv j  and χ is Uv j . (2) The number of nodes where the number of elements of a set obtained by removing χ from Uv j  is equal to or more than “1” and is less than “2k” is one at most. 
     When the header generation unit  32  inputs the header H(χ) to the unauthorized decryption unit D (ST 15 ), the control unit  33  observes an output from the unauthorized decryption unit D. 
     At this time, the control unit  33  determines whether the unauthorized decryption unit D outputs the correct session key s (ST 16 ). If the decryption unit outputs the correct session key s (YES in step ST 16 ), C j  is incremented by “1” (ST 17 ). Otherwise (NO in step ST 16 ), the value of C j  is not changed. 
     Note that when the unauthorized decryption unit D outputs only decrypted contents, it is observed whether a content is correctly decrypted. If the content is correctly decrypted, C j  is incremented by “1”. Otherwise, the value of C j  is not changed. 
     In any case, after C j  is updated, the control unit  33  determines whether a test count z is less than m (ST 18 ). If the test count z is less than m, z is incremented by “1” (ST 19 ), and the flow returns to step S 14  to repeat a test. 
     If it is determined in step S 18  that the test count z is equal to m, the control unit  33  determines whether a user number j of an invalid user is less than a total user count n (ST 20 ). If the user number j is less than n, j is incremented by “1” (ST 21 ), and the flow returns to step ST 12  to repeat a test. 
     If it is determined in step ST 20  that the user number j of the invalid user coincides with the total user count n, the test is terminated. 
     The control unit  33  then calculates C j−1 −C j  with respect to j=1, . . . , n, and detect an integer j by which maximizes C j−1 −C j  (ST 22 ), thereby specifying uj as an unauthorized user and outputting its user ID (ST 23 ). 
     According to this tracking method, as shown in  FIGS. 10 and 11 , the number of candidates for unauthorized users belonging to an invalid user set is increased one by one, and it is checked whether decryption is disabled when the candidates for unauthorized users are invalidated. Performing this test a total of mn times makes it possible to specify one or more unauthorized users. 
     Assume that a set of user IDs is represented by {u 1 , . . . , u n } and user IDs of conspirators of test object decryption units  20 χ are u 2  and U 4 . 
     In this case, when header information generated with user IDs=u 1 , u 2 , and u 3  representing invalid users is supplied, since the test object decryption unit  20 χ corresponds to user ID=u 4 , a correct session key can be obtained. Therefore, after the processing is repeated m times, C 3 =m. 
     When header information generated with user IDs=u 1 , u 2 , u 3 , and u 4  representing invalid users is supplied, a correct session key cannot be obtained from the test object decryption unit. Therefore, after the processing is repeated m times, C 4 =0. 
     Since C 3 −C 4  provides the maximum value m, it is known that the user ID of one of the conspirators of the test object decryption units  20 χ is u 4 . In addition, the user IDs of all the conspirators can be specified by changing the order of labeling of users. 
     In general, when there is at least one integer j which satisfies C j−1 −C j ≧m/n and a user with user ID=u i  is not an unauthorized user, C i−1 −C i &lt;&lt;m/n. Therefore, an unauthorized user ID can be specified by detecting the integer j which maximizes C j−1 −C j . 
     Assume that a test object decryption unit is a smarter unauthorized decryption unit. In this case, upon detecting black box tracking, the test object decryption unit may reject receiving any inputs from the header generation unit  32  after a given time point. In this case, an unauthorized user ID can be specified as u j  by using the value of j at this time point. This applies to each of the following embodiments. 
     Since a header can be calculated by using the public key e, anyone can track an unauthorized user by using the tracking apparatus  30 . 
     As described above, according to this embodiment, since header information does not include the user identification information of any user system, information indicating whose decryption key is invalidated does not leak at the time of black box tracking. This prevents the unauthorized decryption unit from knowing the intention of each input at the time of black box tracking, and hence makes it possible to reliably execute tracking even with respect to a smart unauthorized decryption unit which operates to read the intention of an input and deter the specification of an unauthorized user. 
     According to the conventional black box tracking method, both the key generation polynomials A i (x) and B i (x) are different key generation polynomials for nodes. In contrast to this, according to this embodiment, since one key generation polynomial B(x) is made common to all the nodes, the size of decryption key data to be held in the decryption unit can be reduced to almost half while the transmission overhead is kept almost unchanged. 
     Second Embodiment 
     The second embodiment of the present invention will be described next. This embodiment will exemplify a method of eliminating the limitation of m&lt;2k without increasing the degree of a key generation polynomial in the encryption phase in the first embodiment if it is determined in step ST 2 - 4  in  FIG. 6  that the product set of χ and Uv j  is not Uv j  (NO in step ST 2 - 4 ). This embodiment differs from the first embodiment only in the encryption method to be used when it is determined in step ST 2 - 4  that the product set of χ and Uv j  is not Uv j , and a corresponding decryption method. Therefore, only they will be described below. 
     Assume that q is a prime number, p−1 is divisible by q, and q is equal to or more than n+2k. 
     Decryption Phase 
     A case wherein it is determined in step ST 2 - 4  that the product set of χ and Uv j  is not Uv j  (NO in step ST 2 - 4 ) will be described next. 
     As shown in  FIG. 7 , the header generation unit  15  obtains a partial set as {x 1 , . . . , x m } by removing the invalid user set χ from Uv j . In this case, m represents the total number of users who are not invalid (valid users) of the user set belonging to Uv j  as in the case described above. 
     A header generation unit  15  searches for an integer d which satisfies 2dk≦m≦2dk+2k−1. If 2dk+2k−m−1&gt;0, the header generation unit  15  randomly selects x m+1 , . . . , x 2dk+2k−1  from Zq−(U+{0}). Note that Zq−(U+{0}) means the value obtained by removing the sum of sets U and {0} from Zq. 
     The header generation unit  15  obtains elements L 0 , . . . , L 2dk+2k−1  of Zq satisfying expression (14) with respect to 1≦t≦2dk+2k−1. 
     
       
         
           
             
               
                 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         0 
                       
                       
                         
                           2 
                           ⁢ 
                           dk 
                         
                         + 
                         
                           2 
                           ⁢ 
                           k 
                         
                         - 
                         1 
                       
                     
                     ⁢ 
                     
                       
                         L 
                         i 
                       
                       ⁢ 
                       
                         x 
                         t 
                         i 
                       
                     
                   
                   = 
                   
                     0 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     mod 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     q 
                   
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
     The header generation unit  15  then calculates Hv j  by substituting r 1  into r according to expression (15) (ST 2 - 6 ). 
     
       
         
           
             
               
                 
                   
                     
                       H 
                       
                         v 
                         j 
                       
                     
                     = 
                     
                       ( 
                       
                         
                           h 
                           
                             v 
                             j 
                           
                         
                         , 
                         
                           h 
                           
                             v 
                             j 
                           
                           ′ 
                         
                         , 
                         
                           h 
                           
                             
                               v 
                               j 
                             
                             , 
                             0 
                           
                         
                         , 
                         … 
                         ⁢ 
                         
                             
                         
                         , 
                         
                           h 
                           
                             
                               v 
                               j 
                             
                             , 
                             
                               
                                 2 
                                 ⁢ 
                                 dk 
                               
                               + 
                               
                                 2 
                                 ⁢ 
                                 k 
                               
                               - 
                               1 
                             
                           
                         
                       
                       ) 
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       h 
                       
                         v 
                         j 
                       
                     
                     = 
                     
                       g 
                       r 
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       h 
                       
                         v 
                         j 
                       
                       ′ 
                     
                     = 
                     
                       g 
                       
                         
                           λ 
                           
                             v 
                             j 
                           
                         
                         ⁢ 
                         r 
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       h 
                       
                         
                           v 
                           j 
                         
                         , 
                         i 
                       
                     
                     = 
                     
                       { 
                       
                         
                           
                             
                               
                                 
                                   
                                     g 
                                     
                                       L 
                                       i 
                                     
                                   
                                   ⁢ 
                                   
                                     g 
                                     
                                       ra 
                                       
                                         i 
                                         ⁢ 
                                         
                                             
                                         
                                         ⁢ 
                                         mod 
                                         ⁢ 
                                         
                                             
                                         
                                         ⁢ 
                                         2 
                                         ⁢ 
                                         k 
                                       
                                     
                                   
                                 
                               
                               
                                 
                                   ( 
                                   
                                     
                                       y 
                                       
                                         v 
                                         j 
                                       
                                     
                                     ≠ 
                                     
                                       ⅈ 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       mod 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       2 
                                       ⁢ 
                                       k 
                                     
                                   
                                   ) 
                                 
                               
                             
                             
                               
                                 
                                   
                                     sg 
                                     
                                       L 
                                       i 
                                     
                                   
                                   ⁢ 
                                   
                                     g 
                                     
                                       rc 
                                       
                                         v 
                                         j 
                                       
                                     
                                   
                                 
                               
                               
                                 
                                   ( 
                                   
                                     
                                       y 
                                       
                                         v 
                                         j 
                                       
                                     
                                     ≠ 
                                     
                                       ⅈmod 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       2 
                                       ⁢ 
                                       k 
                                     
                                   
                                 
                               
                             
                           
                           ⁢ 
                           
                             
 
                           
                           ⁢ 
                           
                             y 
                             
                               v 
                               j 
                             
                           
                         
                         = 
                         
                           
                             v 
                             j 
                           
                           ⁢ 
                           mod 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           2 
                           ⁢ 
                           k 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
           
         
       
     
     Note that, as described above, three or more random numbers to be substituted into r may be prepared, and a different random number may be substituted into r every time a case wherein NO is obtained in step ST 2 - 4  occurs. 
     Decryption Phase 
     Consider a user u belonging to the partial set Uv j . In step ST 5 - 6  in  FIG. 8 , expression (16) is calculated by using Hv j . 
     
       
         
           
             
               
                 
                   
                     
                       
                         s 
                         = 
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 
                                   h 
                                   
                                     
                                       v 
                                       j 
                                     
                                     , 
                                     0 
                                   
                                 
                                 × 
                                 … 
                                 × 
                                 
                                   h 
                                   
                                     u 
                                     
                                       
                                         v 
                                         j 
                                       
                                       , 
                                       
                                         
                                           2 
                                           ⁢ 
                                           dk 
                                         
                                         + 
                                         
                                           2 
                                           ⁢ 
                                           k 
                                         
                                         - 
                                         1 
                                       
                                     
                                     
                                       
                                         2 
                                         ⁢ 
                                         dk 
                                       
                                       + 
                                       
                                         2 
                                         ⁢ 
                                         k 
                                       
                                       - 
                                       1 
                                     
                                   
                                 
                               
                               
                                 
                                   ( 
                                   
                                     
                                       h 
                                       
                                         v 
                                         j 
                                       
                                       
                                         
                                           A 
                                           
                                             v 
                                             j 
                                           
                                         
                                         ⁡ 
                                         
                                           ( 
                                           u 
                                           ) 
                                         
                                       
                                     
                                     ⁢ 
                                     
                                       h 
                                       
                                         v 
                                         j 
                                       
                                       
                                         ′ 
                                         
                                           B 
                                           ⁡ 
                                           
                                             ( 
                                             u 
                                             ) 
                                           
                                         
                                       
                                     
                                   
                                   ) 
                                 
                                 
                                   
                                     ∑ 
                                     
                                       t 
                                       = 
                                       0 
                                     
                                     d 
                                   
                                   ⁢ 
                                   
                                     u 
                                     
                                       2 
                                       ⁢ 
                                       kt 
                                     
                                   
                                 
                               
                             
                             ) 
                           
                           
                             1 
                             / 
                             
                               u 
                               
                                 
                                   y 
                                   
                                     v 
                                     j 
                                   
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       
                                         ∑ 
                                         
                                           t 
                                           = 
                                           0 
                                         
                                         d 
                                       
                                       ⁢ 
                                       
                                         2 
                                         ⁢ 
                                         kt 
                                       
                                     
                                     + 
                                     1 
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               
                                 
                                   s 
                                   
                                     u 
                                     
                                       
                                         y 
                                         
                                           v 
                                           j 
                                         
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             
                                               ∑ 
                                               
                                                 t 
                                                 = 
                                                 0 
                                               
                                               d 
                                             
                                             ⁢ 
                                             
                                               2 
                                               ⁢ 
                                               kt 
                                             
                                           
                                           + 
                                           1 
                                         
                                         ) 
                                       
                                     
                                   
                                 
                                 ⁢ 
                                 
                                   
                                     
                                       g 
                                       
                                         
                                           ∑ 
                                           
                                             i 
                                             = 
                                             0 
                                           
                                           
                                             
                                               2 
                                               ⁢ 
                                               dk 
                                             
                                             + 
                                             
                                               2 
                                               ⁢ 
                                               k 
                                             
                                             - 
                                             1 
                                           
                                         
                                         ⁢ 
                                         
                                           
                                             L 
                                             i 
                                           
                                           ⁢ 
                                           
                                             u 
                                             i 
                                           
                                         
                                       
                                     
                                     ⁡ 
                                     
                                       ( 
                                       
                                         g 
                                         
                                           
                                             ∑ 
                                             
                                               i 
                                               = 
                                               0 
                                             
                                             
                                               
                                                 2 
                                                 ⁢ 
                                                 k 
                                               
                                               - 
                                               1 
                                             
                                           
                                           ⁢ 
                                           
                                             
                                               r 
                                               1 
                                             
                                             ⁢ 
                                             
                                               a 
                                               
                                                 
                                                   v 
                                                   j 
                                                 
                                                 , 
                                                 i 
                                               
                                             
                                             ⁢ 
                                             
                                               u 
                                               i 
                                             
                                           
                                         
                                       
                                       ) 
                                     
                                   
                                   
                                     
                                       ∑ 
                                       
                                         t 
                                         = 
                                         0 
                                       
                                       d 
                                     
                                     ⁢ 
                                     
                                       u 
                                       
                                         2 
                                         ⁢ 
                                         kt 
                                       
                                     
                                   
                                 
                               
                               
                                 g 
                                 
                                   r 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   1 
                                   ⁢ 
                                   
                                     ( 
                                     
                                       
                                         
                                           A 
                                           
                                             v 
                                             j 
                                           
                                         
                                         ⁡ 
                                         
                                           ( 
                                           u 
                                           ) 
                                         
                                       
                                       + 
                                       
                                         
                                           λ 
                                           
                                             v 
                                             j 
                                           
                                         
                                         ⁢ 
                                         
                                           B 
                                           ⁡ 
                                           
                                             ( 
                                             u 
                                             ) 
                                           
                                         
                                       
                                     
                                     ) 
                                   
                                   ⁢ 
                                   
                                     
                                       ∑ 
                                       
                                         t 
                                         = 
                                         0 
                                       
                                       d 
                                     
                                     ⁢ 
                                     
                                       u 
                                       
                                         2 
                                         ⁢ 
                                         kt 
                                       
                                     
                                   
                                 
                               
                             
                             ) 
                           
                           
                             1 
                             / 
                             
                               u 
                               
                                 
                                   y 
                                   
                                     v 
                                     j 
                                   
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       
                                         ∑ 
                                         
                                           t 
                                           = 
                                           0 
                                         
                                         d 
                                       
                                       ⁢ 
                                       
                                         2 
                                         ⁢ 
                                         kt 
                                       
                                     
                                     + 
                                     1 
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             ( 
                             
                               s 
                               
                                 u 
                                 
                                   
                                     v 
                                     j 
                                   
                                   ⁢ 
                                   mod 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   2 
                                   ⁢ 
                                   k 
                                 
                               
                             
                             ) 
                           
                           
                             1 
                             / 
                             
                               
                                 u 
                                 
                                   y 
                                   
                                     v 
                                     j 
                                   
                                 
                               
                               . 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
           
         
       
     
     If the user u is an invalid user (YES in step ST 6 ), expression (17) does not hold. Therefore, a session key s cannot be obtained (ST 7 ). 
     
       
         
           
             
               
                 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         0 
                       
                       
                         
                           2 
                           ⁢ 
                           dk 
                         
                         + 
                         
                           2 
                           ⁢ 
                           k 
                         
                         - 
                         1 
                       
                     
                     ⁢ 
                     
                       
                         L 
                         i 
                       
                       ⁢ 
                       
                         u 
                         i 
                       
                     
                   
                   = 
                   
                     0 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     mod 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     q 
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
     As described above, according to the second embodiment, with the arrangement which eliminates the limitation of m&lt;2k, i.e., in a case wherein an invalid user and a valid user who is not an invalid user coexist in a given subgroup Uv j , the number of valid users can be increased by 2dk as compared with the first embodiment (the degree of x t  of expression (14) increases from “2k−1” of expression (8) to “2dk+2k−1”, and the number of elements of header information Hv j  increases from “2k−1” of expression (9) to “2dk+2k−1”, as indicated by expression (15)). 
     In addition to the effects of the first embodiment, the second embodiment can cope with a case wherein NO is obtained in step ST 2 - 4  (NO in step S 2 - 4 ), and the number of valid users exceeds the limitation described in the first embodiment. In addition, with the arrangement configured to eliminate the limitation of m&lt;2k, the same effects as those of the first embodiment can be obtained. 
     Third Embodiment 
     The third embodiment of the present invention will be described next. This embodiment exemplifies a case wherein the first embodiment is combined with the decryption key invalidation method disclosed in JP-A 2003-289296 (KOKAI). 
     For example, as shown in  FIG. 17A  (referring to  FIGS. 17A to 17C , the underlines indicate invalid users), when only users with user IDs=1, 2, and 3 are to be invalidated, a session key can be decrypted only when four given data (shares to be described later) are completely prepared (for the sake of simplicity, assuming that the number of invalid users is equal to the maximum number of conspirators, a session key can be decrypted only when shares equal in number to the number of invalid users+1 are completely prepared). 
     A share (1, g F(1) ) obtained with respect to user ID=1, a share (2, g F(2) ) obtained with respect to user ID=2, and a share (3, g F(3) ) obtained with respect to user ID=3 are written in header information. In addition, information based on which a share (x i , g F(x   i   ) ) is obtained with respect to user ID=x i  is written in the header information. 
     With regard to a user ID other than user IDs=1, 2, and 3, since four necessary shares can be prepared by obtaining the share (x i , g F(x   i   ) ) corresponding to user ID=x i , a correct session key can be acquired. 
     In contrast to this, with regard to invalid user ID=1, even if the share (1, g F(1) ) corresponding to user ID=1 is obtained, since it becomes redundant with the share written in the header information, four necessary data cannot be prepared. Therefore, a correct session key cannot be acquired. This applies to user IDs=2 and 3. 
     When all invalid user IDs=1 to 20 belong to a single subgroup U 1  as shown in  FIG. 17B , the overall subgroup U 1  is invalidated as in the first embodiment instead of using shares corresponding to the total number of invalid users. That is, when, for example, the overall subgroup U 1  is to be invalidated, a wrong value (e.g., a random number) is written in information based on which a session key (corresponding to the subgroup U 1 ) is calculated such that a correction session key cannot be obtained. 
     With regard to a user ID belonging to the subgroup U 1 , since a wrong value is set as information based on which a session key is calculated, a correct session key cannot be obtained. 
     In addition, when user IDs=21, 22, and 23 are to be invalidated while user IDs=1 to 20, i.e., the overall subgroup U 1 , are invalidated, as shown in  FIG. 17C , the method shown in  FIG. 5  is executed in combination with the method shown in  FIG. 17A  and  FIG. 17B . 
     In this case, a share (21, g F(   21) ) obtained with respect to user ID=21, a share (22, g F(   22) ) obtained with respect to user ID=22, and a share (23, g F(   23) ) obtained with respect to user ID=23 are written in header information. With regard to only the subgroup U 1  to be invalidated, a wrong value (e.g., a random value) is written in information based on which a share (corresponding to the subgroup U 1 ) is calculated such that a correction share cannot be obtained. With regard to other subgroups, a correct value is written in information based on which a share (corresponding to the subgroup) is calculated such that a correct share can be obtained. 
     With regard to a user ID other than the user IDs belonging to the subgroup U 1  and user IDs=21, 22, and 23, a correct share can be obtained. With this operation, four necessary data can be prepared, and hence a correct session key can be acquired. 
     With regard to user IDs=21, 22, and 23, even if a correct share can be obtained, since four necessary shares cannot be prepared, a correct session key cannot be acquired. 
     With regard to a user ID belonging to the subgroup U 1 , since information based on which a correct share is calculated is a wrong value, four correct shares cannot be prepared. As a consequence, a correct session key cannot be acquired. 
     A key generation phase, encryption phase, decryption phase, and tracking phase will be described below in the order named. Note that the definitions of parameters and the like are the same as those in the first embodiment, unless otherwise specified. 
     Key Generation Phase 
     This embodiment is the same as the first embodiment except that q is a prime number, p−1 is divisible by q, and q is equal to or more than n+4k−1. 
     Decryption Phase 
     Let E be an invalid user set in the encryption phase. That is, E represents a set of users to be invalidated when header information for distribution in the content distribution system is to be generated. 
     A session key generation unit  13  of a content distribution system  1  selects information s based on which a session key is calculated randomly from Zq, and calculates a session key g s . The header generation unit  15  then selects a node in a tree structure T by the following processing. 
     If the node v j , which is an ancestor node of leaves assigned the user set Uv j  that is equal to E or included in E, exist, node is selected from such nodes such that selected sets Uv j  have no common element, and the sum of the sets is equal to expression (18).
 
∪ v     j     ε{v|vεN,U     v       ⊂ E}  U v     j     (18)
 
     If brother leaves, neither Uv i  which is a user set assigned to the one of the brother leaves nor Uv j  which is a user set assigned to the other of the brother leaves is equal to E or included in E, exist, a pair of such brother leaves is selected. Lastly, other nodes which satisfy the following condition are selected. This condition is that the sets Uv j  of all the selected nodes v j  have no common element, and the sum of the sets Uv j  of all the selected nodes v j  is equal to a total user set U. 
     Let J be the number of nodes selected after the above processing. 
     The header generation unit  15  obtains a partial set (represented by expression (19)) as {x 1 , . . . , x w } by removing the sum of all sets Uv j  equal to or included in the invalid user set E from the invalid user set E.
 
E\U v     j     ε{v|vεN,U     v       ⊂ E} U v     j   .   (19)
 
     For example, referring to  FIG. 17B , since the sum of all sets Uv j  equal to or included in E is U 1 , the partial set obtained by removing U 1  from the invalid user set E is {21, 22, 23}. 
     As described above, w represents the number of users to be individually inhibited from decrypting a session key. 
     The header generation unit  15  then searches for an integer z which satisfies 2k(z−1)+1≦w≦2kz, and sets the number (m) of shares in header information to m=2k(z+1)−1. Note that k represents the maximum number of conspirators, as described above. 
     If the above partial set is an empty set, i.e., there is no user to be individually inhibited from decrypting a session key, m=2k−1 and w=0 are set. 
     If the number (w) of users to be individually inhibited from decrypting a session key is smaller than the above number m (w&lt;m), x w+1 , . . . , x m  are randomly selected from Zq−(U+{0}) to obtain (m−w) shares corresponding to the shortage. Note that Zq−(U+{0}) means the value obtained by removing the sum of sets U and {0} from Zq. 
     The header generation unit  15  randomly generates a polynomial F(x) satisfying expression (20). 
     
       
         
           
             
               
                 
                   
                     
                       F 
                       ⁡ 
                       
                         ( 
                         x 
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           0 
                         
                         m 
                       
                       ⁢ 
                       
                         
                           τ 
                           i 
                         
                         ⁢ 
                         
                           x 
                           i 
                         
                         ⁢ 
                         mod 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         q 
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       τ 
                       0 
                     
                     = 
                     s 
                   
                 
               
               
                 
                   ( 
                   20 
                   ) 
                 
               
             
           
         
       
     
     The header generation unit  15  then selects random numbers r 0  and r 1 . The header generation  15  calculates Hv 0 , . . . , Hv J−1  with respect to 0≦j≦J−1 according to expression (21) with J nodes being represented by v 0 , . . . , V J−1 . 
               H     v   j       =     (         h       v   j     ,       ⁢     h       v   j     ,     ′     ⁢     h       v   j     ,   0         ,   …   ⁢           ,     h       v   j     ,   m       ,         h   ^       1   ,       ⁢           ⁢   …   ⁢           ⁢       h   ^     m         )               where               h     v   j       =     g   r                   h     v   j     ′     =     g       λ     v   j       ⁢   r                     h       v   j     ,   i       =     {               g     r   ⁢           ⁢     a     i   ⁢           ⁢   mod   ⁢           ⁢   2   ⁢     k     g     τ   i                       (       y     v   j       ≠     i   ⁢           ⁢   mod   ⁢           ⁢   2   ⁢   k       )                                   (     21   ⁢   a     )                 g       c     v   j       ⁢   r       ⁢     g     τ   i               (         y     v   j       ≠     i   ⁢           ⁢   mod   ⁢           ⁢   2   ⁢   k       ,       U     v   j       ∉   E       )                                   (     21   ⁢   b     )               g     γ   ⁢           ⁢     v     j   ,   i                 (         y     v   j       ≠     i   ⁢           ⁢   mod   ⁢           ⁢   2   ⁢   k       ,       U     v   j       ⊆   E       )                                   (     21   ⁢   c     )           ⁢     
     ⁢       h   ^     i       =         (       x   i     ,     g     F   ⁡     (     x   i     )           )     ⁢     
     ⁢     F   ⁡     (   x   )         =         ∑     i   =   0     m     ⁢       τ   i     ⁢     x   2     ⁢   mod   ⁢           ⁢   q   ⁢     
     ⁢     y     v   j           =       v   j     ⁢   mod   ⁢           ⁢   2   ⁢   k                   
where Υv j,i  is a random number selected by the header generation unit  15 .
 
     Note that in expression (21), of the calculation expression for information hv j,i  based on which a session key is calculated, expression (21a) corresponds to a case wherein a user to be individually inhibited from decrypting a session key exists in the user set belonging to the node v j , and expression (21b) corresponds to a case wherein all the users belonging to the node v j  are not invalid users, with the node v j  including a unique value cv j . In addition, expression (21c) corresponds to a case wherein all the users belonging to the node v j  are invalid users, with the node v j  including a random number γ vj  different from the unique correct value Cv j  instead of it. 
     Hv 0 , . . . , Hv J−1  obtained by the above repetitive processing are used as header information. In this case, since the header can be calculated by using a public key e, anyone can manage the content distribution system  1 . In addition, as in the first embodiment, the transmission overhead can be further reduced by grouping identical elements of the elements constituting Hv 0 , . . . , Hv J−1  obtained by the above repetitive processing into one and sharing it in the header. Furthermore, various types of methods other than the above node selection method can be used. 
     Decryption Phase 
     Consider a user xo belonging to a partial set Uv j . Upon receiving a header, a user system  2  with user ID=x 0  calculates expression (22) by using Hv j . 
               g     F   ⁡     (     x   0     )         =       ∏     i   =   0     m     ⁢       h       v   j     ,   i       x   0   i       /       (       h     v   j         A     v   j       ⁡     (     x   0     )         ⁢     h     v   j       ′     B   ⁡     (     x   0     )             )         ∑     j   =   0     z     ⁢     x   0     2   ⁢   jk                     
In this case, z=(m+1)/2k−1.
 
     
       
         
           
             
               
                 
                   
                     
                       ∏ 
                       
                         i 
                         = 
                         0 
                       
                       m 
                     
                     ⁢ 
                     
                       
                         h 
                         
                           
                             v 
                             j 
                           
                           , 
                           i 
                         
                         
                           x 
                           0 
                           i 
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       is 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       calculated 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       as 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       follows 
                       ⁢ 
                       
                         : 
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       
                         
                           
                             
                               ∏ 
                               
                                 i 
                                 = 
                                 0 
                               
                               m 
                             
                             ⁢ 
                             
                               h 
                               
                                 h 
                                 
                                   
                                     v 
                                     j 
                                   
                                   , 
                                   i 
                                 
                               
                               
                                 x 
                                 0 
                                 i 
                               
                             
                           
                           = 
                             
                           ⁢ 
                           
                             
                               ∏ 
                               
                                 i 
                                 = 
                                 0 
                               
                               z 
                             
                             ⁢ 
                             
                               
                                 ( 
                                 
                                   
                                     h 
                                     
                                       
                                         v 
                                         j 
                                       
                                       , 
                                       
                                         2 
                                         ⁢ 
                                         
                                             
                                         
                                         ⁢ 
                                         ik 
                                       
                                     
                                   
                                   × 
                                   
                                     h 
                                     
                                       
                                         v 
                                         j 
                                       
                                       , 
                                       
                                         
                                           2 
                                           ⁢ 
                                           ik 
                                         
                                         + 
                                         1 
                                       
                                     
                                     
                                       x 
                                       0 
                                     
                                   
                                   × 
                                   … 
                                   × 
                                   
                                     h 
                                     
                                       
                                         v 
                                         j 
                                       
                                       , 
                                       
                                         
                                           2 
                                           ⁢ 
                                           ik 
                                         
                                         + 
                                         
                                           y 
                                           
                                             v 
                                             j 
                                           
                                         
                                       
                                     
                                     
                                       x 
                                       0 
                                       
                                         y 
                                         
                                           v 
                                           j 
                                         
                                       
                                     
                                   
                                   × 
                                   … 
                                   × 
                                   
                                     h 
                                     
                                       
                                         v 
                                         j 
                                       
                                       , 
                                       
                                         
                                           2 
                                           ⁢ 
                                           ik 
                                         
                                         + 
                                         
                                           2 
                                           ⁢ 
                                           k 
                                         
                                         - 
                                         1 
                                       
                                     
                                     
                                       x 
                                       0 
                                       
                                         
                                           2 
                                           ⁢ 
                                           k 
                                         
                                         - 
                                         1 
                                       
                                     
                                   
                                 
                                 ) 
                               
                               
                                 x 
                                 0 
                                 
                                   2 
                                   ⁢ 
                                   ik 
                                 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           = 
                             
                           ⁢ 
                           
                             
                               ∏ 
                               
                                 l 
                                 = 
                                 0 
                               
                               z 
                             
                             ⁢ 
                             
                               
                                 
                                   ( 
                                   
                                     g 
                                     
                                       r 
                                       ⁢ 
                                       
                                         
                                           ∑ 
                                           
                                             i 
                                             = 
                                             0 
                                           
                                           
                                             
                                               2 
                                               ⁢ 
                                               k 
                                             
                                             - 
                                             1 
                                           
                                         
                                         ⁢ 
                                         
                                           
                                             av 
                                             
                                               j 
                                               , 
                                               i 
                                             
                                           
                                           ⁢ 
                                           
                                             x 
                                             0 
                                             i 
                                           
                                         
                                       
                                     
                                   
                                   ) 
                                 
                                 
                                   x 
                                   0 
                                   
                                     2 
                                     ⁢ 
                                     kl 
                                   
                                 
                               
                               × 
                               
                                 g 
                                 
                                   
                                     ∑ 
                                     
                                       j 
                                       = 
                                       0 
                                     
                                     m 
                                   
                                   ⁢ 
                                   
                                     
                                       τ 
                                       j 
                                     
                                     ⁢ 
                                     
                                       x 
                                       0 
                                       j 
                                     
                                   
                                 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           = 
                             
                           ⁢ 
                           
                             
                               
                                 ( 
                                 
                                   
                                     h 
                                     
                                       v 
                                       j 
                                     
                                     
                                       
                                         A 
                                         
                                           v 
                                           j 
                                         
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           x 
                                           0 
                                         
                                         ) 
                                       
                                     
                                   
                                   ⁢ 
                                   
                                     h 
                                     
                                       v 
                                       j 
                                     
                                     
                                       ′ 
                                       
                                         B 
                                         ⁡ 
                                         
                                           ( 
                                           
                                             x 
                                             0 
                                           
                                           ) 
                                         
                                       
                                     
                                   
                                 
                                 ) 
                               
                               
                                 
                                   ∑ 
                                   
                                     l 
                                     = 
                                     0 
                                   
                                   z 
                                 
                                 ⁢ 
                                 
                                   x 
                                   0 
                                   
                                     2 
                                     ⁢ 
                                     kl 
                                   
                                 
                               
                             
                             × 
                             
                               g 
                               
                                 F 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     x 
                                     0 
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   22 
                   ) 
                 
               
             
           
         
       
     
     In this case, calculated g F(x   0   )  is the share of the user x 0 . The user system  2  obtains a session key by calculating expression (23) by using g F(x   0   )  and m shares  , . . . ,   included in the header. 
     
       
         
           
             
               
                 
                   
                     
                       g 
                       
                         F 
                         ⁡ 
                         
                           ( 
                           0 
                           ) 
                         
                       
                     
                     = 
                     
                       
                         
                           ∏ 
                           
                             j 
                             = 
                             0 
                           
                           m 
                         
                         ⁢ 
                         
                           
                             ( 
                             
                               g 
                               
                                 F 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     x 
                                     j 
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                           
                             μ 
                             j 
                           
                         
                       
                       ⁢ 
                       
                         
 
                       
                       ⁢ 
                       
                           
                       
                       = 
                       
                         g 
                         
                           
                             ∑ 
                             
                               j 
                               = 
                               0 
                             
                             m 
                           
                           ⁢ 
                           
                             
                               μ 
                               j 
                             
                             ⁢ 
                             
                               F 
                               ⁡ 
                               
                                 ( 
                                 
                                   x 
                                   j 
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   where 
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       μ 
                       j 
                     
                     = 
                     
                       
                         ∏ 
                         
                           
                             0 
                             ≤ 
                             1 
                             ≤ 
                             m 
                           
                           , 
                           
                             1 
                             ≠ 
                             j 
                           
                         
                       
                       ⁢ 
                       
                         
                           
                             x 
                             1 
                           
                           
                             
                               x 
                               1 
                             
                             - 
                             
                               x 
                               j 
                             
                           
                         
                         ⁢ 
                         mod 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         q 
                       
                     
                   
                 
               
               
                 
                   ( 
                   23 
                   ) 
                 
               
             
           
         
       
     
     Tracking Phase 
     A tracking algorithm sequence example is the same as that in the first embodiment, and the operation of the tracking apparatus in a tracking phase is the same as that shown in  FIG. 9  except for the following difference. In this case, a header can be calculated by using a public key e, and hence anyone can track an unauthorized user by using a tracking apparatus  30 . 
     In step ST 13  in  FIG. 9 , when u j  is included in E (a set of users to be actually invalidated in the above encryption phase in the content distribution system), a control unit  33  substitutes C j−1  into C j  and increments j by one. A test with χ={u 1 , . . . , u j } may be skipped. In step ST 14 , a session key is g F(x0) =g s , and a header generation method is executed in the following manner. 
     In node selection, a header generation unit  32  selects a node v j  which satisfies both conditions (1) and (2). (1) The number of elements of a set obtained by removing χ from Uv j  is equal to or more than “1” and equal to or less than “2k−1”, the product set of Uv j  and χ is an empty set, or the product set of Uv j  and χ is Uv j . (2) The number of nodes where the number of elements of a set obtained by removing χ from Uv j  is equal to or more than “1” and equal to or less than “2k−1” is one at most. The header generation unit  32  calculates Hv j  of each selected node according to expression (24). 
     
       
         
           
             
               
                 
                   
                     
                       H 
                       
                         v 
                         j 
                       
                     
                     = 
                     
                       ( 
                       
                         
                           h 
                           
                             v 
                             j 
                           
                         
                         , 
                         
                           h 
                           
                             v 
                             j 
                           
                           ′ 
                         
                         , 
                         
                           h 
                           
                             
                               v 
                               j 
                             
                             , 
                             0 
                           
                         
                         , 
                         … 
                         ⁢ 
                         
                             
                         
                         , 
                         
                           h 
                           
                             
                               v 
                               j 
                             
                             , 
                             m 
                           
                         
                         , 
                         
                           
                             h 
                             ^ 
                           
                           1 
                         
                         , 
                         … 
                         ⁢ 
                         
                             
                         
                         , 
                         
                           
                             h 
                             ^ 
                           
                           m 
                         
                       
                       ) 
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       h 
                       
                         v 
                         j 
                       
                     
                     = 
                     
                       { 
                       
                         
                           
                             
                               
                                 
                                   g 
                                   
                                     r 
                                     0 
                                   
                                 
                               
                               
                                 
                                   ( 
                                   
                                     r 
                                     = 
                                     
                                       r 
                                       0 
                                     
                                   
                                   ) 
                                 
                               
                             
                             
                               
                                 
                                   g 
                                   
                                     r 
                                     1 
                                   
                                 
                               
                               
                                 
                                   ( 
                                   
                                     r 
                                     = 
                                     
                                       r 
                                       1 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                           ⁢ 
                           
                             
 
                           
                           ⁢ 
                           
                             h 
                             
                               v 
                               j 
                             
                             ′ 
                           
                         
                         = 
                         
                           { 
                           
                             
                               
                                 
                                   
                                     
                                       g 
                                       
                                         
                                           λ 
                                           
                                             v 
                                             j 
                                           
                                         
                                         ⁢ 
                                         
                                           r 
                                           0 
                                         
                                       
                                     
                                   
                                   
                                     
                                       ( 
                                       
                                         r 
                                         = 
                                         
                                           r 
                                           0 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 
                                   
                                     
                                       g 
                                       
                                         
                                           λ 
                                           
                                             v 
                                             j 
                                           
                                         
                                         ⁢ 
                                         
                                           r 
                                           1 
                                         
                                       
                                     
                                   
                                   
                                     
                                       ( 
                                       
                                         r 
                                         = 
                                         
                                           r 
                                           1 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                               
                               ⁢ 
                               
                                 
 
                               
                               ⁢ 
                               
                                 
                                   h 
                                   ^ 
                                 
                                 i 
                               
                             
                             = 
                             
                               
                                 
                                   ( 
                                   
                                     
                                       x 
                                       i 
                                     
                                     , 
                                     
                                       g 
                                       
                                         F 
                                         ⁡ 
                                         
                                           ( 
                                           
                                             x 
                                             i 
                                           
                                           ) 
                                         
                                       
                                     
                                   
                                   ) 
                                 
                                 ⁢ 
                                 
                                   
 
                                 
                                 ⁢ 
                                 
                                   F 
                                   ⁡ 
                                   
                                     ( 
                                     x 
                                     ) 
                                   
                                 
                               
                               = 
                               
                                 
                                   
                                     ∑ 
                                     
                                       i 
                                       = 
                                       0 
                                     
                                     m 
                                   
                                   ⁢ 
                                   
                                     
                                       τ 
                                       i 
                                     
                                     ⁢ 
                                     
                                       x 
                                       i 
                                     
                                     ⁢ 
                                     mod 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     q 
                                     ⁢ 
                                     
                                       
 
                                     
                                     ⁢ 
                                     
                                       y 
                                       
                                         v 
                                         j 
                                       
                                     
                                   
                                 
                                 = 
                                 
                                   
                                     v 
                                     j 
                                   
                                   ⁢ 
                                   mod 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   2 
                                   ⁢ 
                                   k 
                                 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   24 
                   ) 
                 
               
             
           
         
       
     
     Remaining elements hv j  i are calculated in the following manner. 
     If the product set of Uv j  and χ is an empty set, h vj,i  is calculated according to expression (25). 
               h       v   j     ,   i       =     {             g     r   ⁢           ⁢     a     i   ⁢           ⁢   mod   ⁢           ⁢   2   ⁢   k           ⁢     g     τ   i               (       y     v   j       ≠     i   ⁢           ⁢   mod   ⁢           ⁢   2   ⁢   k       )                 g       c     v   j       ⁢   r       ⁢     g     τ   i               (         y     v   j       =     i   ⁢           ⁢   mod   ⁢           ⁢   2   ⁢   k       ,       U     v   j       ∉   E       )               g     γ       v   j     ,   i               (         y     v   j       =     i   ⁢           ⁢   mod   ⁢           ⁢   2   ⁢   k       ,       U     v   j       ⊆   E       )                   
where γ vj,i  is a random number.
 
     Note that if (1) the number of elements of a set obtained by removing χ from Uv j  is equal to or more than “1” and equal to or less than “2k−1” or (2) the product set of Uv j  and χ is Uv j  and the product set of Uv j  and the partial set obtained by removing the sum of all sets Uv j  equal to or included in E from the invalid user set E is an empty set, r 0  is substituted into r. Otherwise, r 0  or r 1  is randomly substituted into r. 
     If the number of elements of a set obtained by removing χ from Uv j  is equal to or more than “1” and equal to or less than “2k−1”, the sum of the set obtained by removing χ from Uv j  and the partial set obtained by removing the sum of all sets Uv j  equal to or included in E from the invalid user set E is represented by {x 1 , . . . , x w }. If w&lt;m, x w+1 , . . . , x m  are randomly selected from Zq−(U+{0}). Note that Zq−(U+{0}) means the value obtained by removing the sum of sets U and {0} from Zq. With respect to 1≦t≦m, elements L 0 , . . . , L m  which satisfy expression (26) are obtained. 
     
       
         
           
             
               
                 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         0 
                       
                       m 
                     
                     ⁢ 
                     
                       
                         L 
                         i 
                       
                       ⁢ 
                       
                         x 
                         t 
                         i 
                       
                     
                   
                   = 
                   
                     0 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     mod 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     q 
                   
                 
               
               
                 
                   ( 
                   26 
                   ) 
                 
               
             
           
         
       
     
     Subsequently, h vj,i  is calculated by substituting r 1  into r according to expression (27). 
     
       
         
           
             
               
                 
                   
                     h 
                     
                       
                         v 
                         j 
                       
                       , 
                       i 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               g 
                               
                                 
                                   r 
                                   1 
                                 
                                 ⁢ 
                                 
                                   a 
                                   
                                     i 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     mod 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     2 
                                     ⁢ 
                                     k 
                                   
                                 
                               
                             
                             ⁢ 
                             
                               g 
                               
                                 τ 
                                 i 
                               
                             
                             ⁢ 
                             
                               g 
                               
                                 L 
                                 i 
                               
                             
                           
                         
                         
                           
                             ( 
                             
                               
                                 y 
                                 
                                   v 
                                   j 
                                 
                               
                               ≠ 
                               
                                 ⅈmod 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 2 
                                 ⁢ 
                                 k 
                               
                             
                             ) 
                           
                         
                       
                       
                         
                           
                             
                               g 
                               
                                 
                                   c 
                                   
                                     v 
                                     j 
                                   
                                 
                                 ⁢ 
                                 
                                   r 
                                   1 
                                 
                               
                             
                             ⁢ 
                             
                               g 
                               
                                 τ 
                                 i 
                               
                             
                             ⁢ 
                             
                               g 
                               
                                 L 
                                 i 
                               
                             
                           
                         
                         
                           
                             ( 
                             
                               
                                 y 
                                 
                                   v 
                                   j 
                                 
                               
                               = 
                               
                                 ⅈmod 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 2 
                                 ⁢ 
                                 k 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   27 
                   ) 
                 
               
             
           
         
       
     
     If the product set of Uv j  and χ is Uv j , the product set of Uv j  and the partial set obtained by removing the sum of all sets Uv j  equal to or included in E from the invalid user set E is calculated first. 
     If the product set of Uv j  and the partial set obtained by removing the sum of all sets Uv j  equal to or included in E from the invalid user set E is not an empty set, r 1  is substituted into r, and it is determined whether selected nodes include a node v i  where the number of elements of the set obtained by removing χ from Uv i  is equal to or more than “1” and equal to or less than “2k−1”. 
     If the selected nodes include the node v i  where the number of elements of the set obtained by removing χ from Uv i  is equal to or more than “1” and equal to or less than “2k−1”, h vj,i  is calculated according to equation (28). 
     
       
         
           
             
               
                 
                   
                     h 
                     
                       
                         v 
                         j 
                       
                       , 
                       i 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               g 
                               
                                 
                                   r 
                                   1 
                                 
                                 ⁢ 
                                 
                                   a 
                                   
                                     i 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     mod 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     2 
                                     ⁢ 
                                     k 
                                   
                                 
                               
                             
                             ⁢ 
                             
                               g 
                               
                                 τ 
                                 i 
                               
                             
                             ⁢ 
                             
                               g 
                               
                                 L 
                                 i 
                               
                             
                           
                         
                         
                           
                             ( 
                             
                               
                                 y 
                                 
                                   v 
                                   j 
                                 
                               
                               ≠ 
                               
                                 ⅈ 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 mod 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 2 
                                 ⁢ 
                                 k 
                               
                             
                             ) 
                           
                         
                       
                       
                         
                           
                             
                               g 
                               
                                 
                                   c 
                                   
                                     v 
                                     j 
                                   
                                 
                                 ⁢ 
                                 
                                   r 
                                   1 
                                 
                               
                             
                             ⁢ 
                             
                               g 
                               
                                 τ 
                                 i 
                               
                             
                             ⁢ 
                             
                               g 
                               
                                 L 
                                 i 
                               
                             
                           
                         
                         
                           
                             ( 
                             
                               
                                 y 
                                 
                                   v 
                                   j 
                                 
                               
                               = 
                               
                                 ⅈ 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 mod 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 2 
                                 ⁢ 
                                 k 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   28 
                   ) 
                 
               
             
           
         
       
     
     If the selected nodes do not include the node v i  where the number of elements of the set obtained by removing χ from Uv i  is equal to or more than “1” and equal to or less than “2k−1”, the partial set obtained by removing the sum of all sets Uv j  equal to or included in E from the invalid user set E is represented by {x 1 , . . . , x w }. If w&lt;m, x w+1 , . . . , x m  are randomly selected from Zq−(U+{0}). Note that Zq−(U+{0}) means the value obtained by removing the sum of sets U and {0} from Zq. With respect to 1≦t≦m, elements L 0 , . . . , L m  which satisfy expression (26) are obtained. 
     Subsequently, h vj,i  is calculated according to expression (29). 
     
       
         
           
             
               
                 
                   
                     h 
                     
                       
                         v 
                         j 
                       
                       , 
                       i 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               g 
                               
                                 
                                   r 
                                   1 
                                 
                                 ⁢ 
                                 
                                   a 
                                   
                                     i 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     mod 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     2 
                                     ⁢ 
                                     k 
                                   
                                 
                               
                             
                             ⁢ 
                             
                               g 
                               
                                 τ 
                                 i 
                               
                             
                             ⁢ 
                             
                               g 
                               
                                 L 
                                 i 
                               
                             
                           
                         
                         
                           
                             ( 
                             
                               
                                 y 
                                 
                                   v 
                                   j 
                                 
                               
                               ≠ 
                               
                                 ⅈmod 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 2 
                                 ⁢ 
                                 k 
                               
                             
                             ) 
                           
                         
                       
                       
                         
                           
                             
                               g 
                               
                                 
                                   c 
                                   
                                     v 
                                     j 
                                   
                                 
                                 ⁢ 
                                 
                                   r 
                                   1 
                                 
                               
                             
                             ⁢ 
                             
                               g 
                               
                                 τ 
                                 i 
                               
                             
                             ⁢ 
                             
                               g 
                               
                                 L 
                                 i 
                               
                             
                           
                         
                         
                           
                             ( 
                             
                               
                                 y 
                                 
                                   v 
                                   j 
                                 
                               
                               = 
                               
                                 ⅈ 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 mod 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 2 
                                 ⁢ 
                                 k 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   29 
                   ) 
                 
               
             
           
         
       
     
     Note that if L 0 , . . . , L m  have already been generated, already generated L 0 , . . . , L m  are used and are not generated again. 
     If the product set of Uv j  and the partial set obtained by removing the sum of all sets Uv j  equal to or included in E from the invalid user set E is an empty set, r 0  or r 1  is randomly substituted into r, and it is determined whether the selected nodes include a node v i  where (1) the number of elements of a set obtained by removing χ from Uv j  is equal to or more than “1” and equal to or less than “2k−1” or (2) the product set of Uv j  and χ is Uv j  and the product set of Uv j  and the partial set obtained by removing the sum of all sets Uv j  equal to or included in E from the invalid user set E is an empty set. 
     If the selected nodes include the node v i  where (1) the number of elements of a set obtained by removing χ from Uv j  is equal to or more than “1” and equal to or less than “2k−1” or (2) the product set of Uv j  and χ is Uv j  and the product set of Uv j  and the partial set obtained by removing the sum of all sets Uv j  equal to or included in E from the invalid user set E is an empty set, h vj,i  is calculated according to expression (30). 
               h       v   j     ,   i       =     {             g       r   0     ⁢     a     i   ⁢           ⁢   mod   ⁢           ⁢   2   ⁢   k           ⁢     g     τ   i               (         y     v   j       ≠     ⅈmod   ⁢           ⁢   2   ⁢   k       ,     r   =     r   0         )                 g       r   1     ⁢     a     i   ⁢           ⁢   mod   ⁢           ⁢   2   ⁢   k           ⁢     g     τ   i       ⁢     g     L   i               (         y     v   j       ≠     ⅈmod   ⁢           ⁢   2   ⁢   k       ,     r   =     r   1         )               g     γ       v   j     ,   i               (       y     v   j       =     ⅈmod   ⁢           ⁢   2   ⁢   k       )                   
where γv j,i  is a random number.
 
     If the selected nodes do not include the node v i  where (1) the number of elements of a set obtained by removing χ from Uv j  is equal to or more than “1” and equal to or less than “2k−1” or (2) the product set of Uv j  and χ is Uv j  and the product set of Uv j  and the partial set obtained by removing the sum of all sets Uv j  equal to or included in E from the invalid user set E is an empty set, h vj,i  is calculated according to expression (31). 
                     h       v   j     ,   i       =     {             g     r   ⁢           ⁢     a     i   ⁢           ⁢   mod   ⁢           ⁢   2   ⁢   k           ⁢     g     τ   i               (       y     v   j       ≠     ⅈmod   ⁢           ⁢   2   ⁢   k       )               g     γ       v   j     ,   i               (       y     v   j       =     ⅈmod   ⁢           ⁢   2   ⁢   k       )                     (   31   )               
where γ vj,i  is a random number.
 
     If v 0 , . . . , v J− 1 represent the selected nodes, Hv 0 , . . . , Hv J−1  obtained by the above repetitive processing are used as header information. 
     As described above, in addition to the effects of the first embodiment, owing to the arrangement obtained by combining the first embodiment and the decryption key invalidation method disclosed in JP-A 2003-289296 (KOKAI), the third embodiment can cope with a case wherein NO is obtained in step ST 2 - 4  (NO in step S 2 - 4 ), and the number of valid users exceeds the limitation described in the first embodiment. In addition, an increase in transmission overhead when the number of valid users greatly exceeds the limitation described in the first embodiment can be suppressed more than in the second embodiment. Furthermore, the same effects as those of the first embodiment can be obtained by the arrangement obtained by combining the first embodiment and the decryption key invalidation method disclosed in JP-A 2003-289296 (KOKAI). 
     Although all the embodiments described above are mainly expressed in the category of “system”. However, it is obvious that the embodiment is not limited to this, and the embodiments may be expressed in an arbitrary category such as the category of “apparatus”, “method”, “computer-readable storage medium”, or “program”. In addition, obviously, it suffices to extract part of a system and express it in another category as well as changing the overall category of the system. 
     Each of the encryption apparatuses, decryption units, and tracking apparatuses of all the embodiments described above can be implemented as hardware such as a semiconductor integrated device and as software (a program for causing a computer to execute a predetermined means or causing a computer to function as a predetermined means, or causing a computer to implement a predetermined function). Obviously, hardware and software can be implemented in combination with each other. 
     When each device is implemented as a program, the program can be distributed by being stored in storage media such as magnetic disks (floppy (registered trademark) disks and hard disks), optical disks (CD-ROMs, DVDs, and the like), magneto-optical disks (MOs), and semiconductor memories. 
     This storage medium can take any storage forms as long as the storage medium can store programs and is a computer-readable storage medium. 
     In addition, an OS (Operating System) operating on a computer on the basis of commands from programs installed from a storage medium into the computer, MW (middleware) such as database management software or network software, or the like may execute part of the processes for implementing this embodiment. 
     The storage medium in the embodiments includes not only a medium independent of the computer but also a storage medium in which a program sent through a LAN, Internet, or the like is downloaded and stored or temporarily stored. 
     In addition, the number of storage media is not limited to one, and the storage medium of the embodiments also includes a plurality of media used to execute the processes in this embodiment. That is, the embodiment is not limited to any specific storage arrangement. 
     Note that the computer executes the respective processes in this embodiment on the basis of the programs stored in the storage medium, and the embodiment may take any arrangement, e.g., an apparatus consisting of a single device such as a personal computer or a system constituted by a plurality of devices connected to each other through a network. 
     Furthermore, the computer of the embodiments above is not limited to a personal computer, and is a generic name for devices and apparatuses capable of implementing the functions of the embodiments above on the basis of programs, including arithmetic processing units, microcomputers, and the like contained in information processing devices. 
     The respective user systems are assigned to leaves on a tree structure on a subgroup basis, and are classified and identified according to the respective leaves and their ancestor nodes on the tree structure. Therefore, since header information does not include the user identification information of a user system, black box tracking can be reliably executed with respect to even a smart unauthorized decryption unit, which operates to read the intention of each input and deter the specification of an unauthorized user, without allowing the unauthorized decryption unit to know the intention of each input. Introducing a common key generation polynomial common to a plurality of nodes and a plurality of leaves on a tree structure makes it possible to reduce the size of decryption key data to be held by a decryption unit as compared with the conventional method capable of performing similar black box tracking while keeping similar transmission overhead. 
     As described above, according to the above embodiments, black box tracking can be reliably executed even with respect to a smart unauthorized decryption unit without allowing the unauthorized decryption unit to know the intention of each input, and the size of decryption key data to be held by the decryption unit can be reduced.