Abstract:
Provided are a method of configuring a hierarchical network of user groups and resource groups, and a key distribution center. The method includes the steps of: analyzing hierarchical connection relationships between respective user groups and respective resource groups, comparing redundancy rates of the respective hierarchical connection relationships, and determining a connection mode having a larger redundancy rate; separating the respective user groups and resource groups and hierarchically connecting the user groups with the resource groups, according to the determined connection mode; comparing hierarchical connections between the respective separated user groups and resource groups, and removing an overlapping hierarchical connection; and recombining the separate hierarchical connections except for the overlapping hierarchical connection, and configuring an entire network.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
       [0001]    This application claims priority to and the benefit of Korean Patent Application No. 2006-122877, filed Dec. 6, 2006, and No. 2007-47568, filed May 16, 2007, the disclosure of which is incorporated herein by reference in its entirety. 
       BACKGROUND 
       [0002]    1. Field of the Invention 
         [0003]    The present invention relates to a method of configuring a hierarchical network of a user group and a resource group and a key distribution center. 
         [0004]    The present invention has been produced from the work supported by the IT R&amp;D program of MIC (Ministry of Information and Communication)/IITA (Institute for Information Technology Advancement) [2006-S-019-01, The Development of Digital Cable Transmission and Receive System for 1 Gbps Downstream] in Korea. 
         [0005]    2. Discussion of Related Art 
         [0006]    As networks are developed, a resource group providing data information in a network is connected in a very complicated manner with a user receiving and using the information in the network, and furthermore, a user connected to each resource group is continuously changed. 
         [0007]    In such a complicated network structure, forward secrecy and backward secrecy must be guaranteed in order for network subscribers to freely join, withdraw from and change a group, so that a user and a resource group can have a hierarchical access relationship and safely communicate with each other. Here, the backward secrecy indicates a requirement that a subscriber newly joining a network group must not know communication content between members of the corresponding network before he/she joins, and the forward secrecy indicates a requirement that a subscriber that withdraws from a network group must not know a communication content between members of the corresponding network after he/she withdraws. 
         [0008]    To meet the above requirements, key information for information security between each resource group and a currently connected user must be provided to both the user and the resource group, and used requirement keys must be appropriately managed. Particularly, in a centralized method, a key distribution center (KDC) disposed at a head-end performs the above functions. 
         [0009]    Meanwhile, performance of a requirement key management method can be verified using communication cost and storage cost according to dynamic membership change of subscribers. The communication cost denotes the amount of messages that a KDC sends to subscribers every time a dynamic membership of a subscriber is generated, and the storage cost denotes key storage capacity for the messages. Needless to say, the lower the costs, the better the key management method is. 
         [0010]    Therefore, a method of hierarchically connecting a user group with a resource group has been researched, that is, a method which can minimize key information cost while maintaining both the forward secrecy and the backward secrecy in a relationship where a user group and a resource group are hierarchically connected. 
       SUMMARY OF THE INVENTION 
       [0011]    The present invention is directed to a method and apparatus for configuring a hierarchical network of a user group and a resource group. 
         [0012]    The present invention is also directed to a method and apparatus for configuring a hierarchical network of a user group and a resource group that simplify a network configuration by removing hierarchical connection redundancies from the viewpoint of the user group and the resource group. 
         [0013]    One aspect of the present invention provides a method of configuring a hierarchical network of user groups and resource groups, the method comprising the steps of: (a) analyzing hierarchical connection relationships between the respective user groups and the respective resource groups, comparing redundancy rates of the respective hierarchical connection relationships, and determining a connection mode having a larger redundancy rate; (b) separating the respective user groups and resource groups and hierarchically connecting the user groups with the resource groups, according to the determined connection mode; (c) comparing hierarchical connections between the respective separated user groups and resource groups, and removing an overlapping hierarchical connection; and (d) recombining the hierarchical connections of step (c), except for the overlapping hierarchical connection, and configuring an entire network. 
         [0014]    The redundancy rates may be determined corresponding to a user group set (US) primary redundancy set (UPRS) and a resource group set (RS) primary redundancy set (RPRS). In addition, the UPRS may include elements having the same hierarchical relationship among hierarchical relationships having the respective user groups as their roots, and the elements may not have a common component. In further addition, the RPRS may include elements having the same hierarchical relationship among hierarchical relationships having the respective resource groups as their roots, and the elements may not have a common component. Furthermore, when the elements of the primary redundancy set (PRS) have a common component, only one element having the largest overlap counter (OC) may be included in the PRS. 
         [0015]    In addition, the hierarchical connection method of step (b) may be a star graph method whereby an intermediate node is not generated when the respective user groups and resource groups are hierarchically connected. In further addition, roots of the hierarchical connections may be determined according to the connection mode of step (a) when the user groups and resource groups are hierarchically connected. 
         [0016]    Further, the overlapping hierarchical connection of step (c) may have the same parent node and child node when the user groups and the resource groups are hierarchically connected. Furthermore, the method may further comprise the step of, after removing the overlapping hierarchical connection, integrating the hierarchical relationships between the respective user groups and resource groups to complete hierarchical relationships between the total user groups and resource groups, and aligning roots and end-nodes of the hierarchical relationships. 
         [0017]    Another aspect of the present invention provides a key distribution server managing a centralized network connecting at least one user group with at least one resource group, the key distribution server comprising: means for analyzing a hierarchical connection relationship between each user group and each resource group, comparing redundancy rates of the respective hierarchical connection relationships, and determining a connection mode having a larger redundancy rate; means for hierarchically connecting the user group with the resource group according to the determined connection mode; and means for removing an overlapping hierarchical connection from the hierarchical connection between the user group and resource group. 
         [0018]    The redundancy rates may be determined corresponding to a UPRS and a RPRS. In addition, the UPRS may include elements having the same hierarchical relationship among hierarchical relationships having the respective user groups as their roots, and the elements may not have a common component. In further addition, the RPRS may include elements having the same hierarchical relationship among hierarchical relationships having the respective resource groups as their roots, and the elements may not have a common component. Furthermore, when the elements of the PRS have a common component, only one element having the largest overlap counter may be included in the PRS. 
         [0019]    In addition, the hierarchical connection method may be a star graph method whereby an intermediate node is not generated when each user group and each resource group are hierarchically connected. 
         [0020]    In further addition, a root of the hierarchical connections may be determined according to the connection mode when the user group and resource group are hierarchically connected. In still further addition, the overlapping hierarchical connection may have the same parent node and child node when the user group and the resource group are hierarchically connected. Furthermore, the key distribution server may further comprise means for, after the overlapping hierarchical connection is removed, integrating the hierarchical relationship between each user group and each resource group to complete a hierarchical relationship between the total user groups and resource groups, and aligning a root and an end-node of the hierarchical relationship. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0021]    The above and other objects, features and advantages of the present invention will become more apparent to those of ordinary skill in the art by describing in detail exemplary embodiments thereof with reference to the attached drawings, in which: 
           [0022]      FIG. 1  illustrates an example of hierarchical network connections between user groups and resource groups according to the present invention; 
           [0023]      FIG. 2  illustrates hierarchical access relationships to which the present invention will be applied; 
           [0024]      FIG. 3  illustrates a conventional hierarchical connection method compared to the present invention; 
           [0025]      FIG. 4  shows a configuration of a network using a conventional hierarchical connection method compared to the present invention; 
           [0026]      FIG. 5  is a flowchart showing a method of configuring a hierarchical network of a user group and a resource group according to an exemplary embodiment of the present invention; 
           [0027]      FIG. 6  illustrates a method of configuring a hierarchical network of a user group and a resource group according to an exemplary embodiment of the present invention; and 
           [0028]      FIG. 7  shows a configuration of a network using a method of configuring a hierarchical network of a user group and a resource group according to an exemplary embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS 
       [0029]    Hereinafter, exemplary embodiments of the present invention will be described in detail. However, the present invention is not limited to the embodiments disclosed below, but can be implemented in various forms. The following embodiments are described in order to enable those of ordinary skill in the art to embody and practice the present invention. 
         [0030]      FIG. 1  illustrates an example of hierarchical network connections between user groups and resource groups according to the present invention. 
         [0031]    Referring to  FIG. 1 , connections between user groups  101  and resource groups  105  in a general network  103  are shown. In the network  103 , the user groups  101  and the resource groups  105  can be hierarchically connected. Each user group  101  may be connected with the plurality of resource groups  105 , and also, each resource group  105  may be connected with the plurality of user groups  101 . In the hierarchical connection network  103 , the user groups  101  and the resource groups  105  may communicate with each other. Here, when the user groups  101  freely withdraw from, join and change the resource groups  105 , information security on the withdrawal, joining and change must be ensured. 
         [0032]    Such an information security message may be composed in a very complex manner when the network  103  is activated. Here, when the information security message is provided to each of the user groups  101  or the resource groups  105 , an amount of the information security messages may increase by geometric progression. Thus, it is very important to reduce the amount of the messages and a storage space for the messages. To this end, it is of great importance to efficiently configure the hierarchical network connection relationships between the user groups  101  and the resource groups  105  constituting the network  103 . 
         [0033]    Such a hierarchical network connection method is of great importance when most networks providing a centralized communication system offer a group communication service requiring security. In general, the hierarchical network connection method is mainly administered by a key distribution center (KDC), which manages each network. 
         [0034]      FIG. 2  illustrates hierarchical access relationships to which the present invention will be applied. 
         [0035]    Referring to  FIG. 2 : UGs  241  denotes user groups; Rs  201  denotes resource groups; USs denotes user group sets UG 1 , UG 2 , . . . , and UGn; RSs denotes resource group sets R 1 , R 2 , R 3 , . . . , and Rm; and US(Rm) denotes {UGn|UGn is a US capable of accessing Rm}. In addition, in  FIG. 2 , “A→B” denotes that B is encoded using A, which can be expressed by {B}A. 
         [0036]    In  FIG. 2 , a first layer connected with the resource groups  201  is the layer of session keys (SKs)  211 . The SKs  211  are connected with resource keys (RKs)  221 , respectively. And, the SKs  211  serve to prevent communication cost increase, that is, the amount of data in a message informing of changes when information is updated by periodical changes in encryption. In general, a resource group is directly encoded for information security. Here, when a plurality of lower layers are directly connected with the encoded resource group, communication cost significantly increases because an encryption key must be encoded for each of the connected lower layers and transferred. Therefore, the SKs  211  are connected with the Rs  201 , respectively. 
         [0037]    A second layer is the layer of resource keys (RKs)  221 . The RK layer is connected with the layer of SKs  211 , and also serves to reduce communication cost for encryption of the Rs  201  in combination with the SKs  211 . 
         [0038]    A third layer is the layer of user group keys (UGKs)  231 , which are connected with the UGs  241 , respectively. The UGKs  231  serve to authenticate the members of the UGs  241 . 
         [0039]    A connection network  251  configured using the respective keys is shown in  FIG. 2 . 
         [0040]    Ultimately, such a hierarchical configuration and hierarchical keys minimize communication cost while maintaining forward secrecy and backward secrecy when a UG is connected with an R. 
         [0041]    Here, the forward secrecy indicates that a subscriber withdrawn from a group must not know communication content of members of the group after his/her withdrawal, and the backward secrecy indicates that a subscriber newly joining a group must not know communication content of members of the group before he/she joins. 
         [0042]    A method of distributing a hierarchical encryption key to maintain the forward and backward secrecy will be described with reference to the hierarchical connection diagram. First, it is assumed that a set of all keys used for composing a key distribution message is KS(UGn). In  FIG. 2 , KS(UG 1 ) will be (RK 1 , Sk 1 ). Here, key distribution methods will be described for cases in which a user withdraws from a group, joins a group, and changes a group, respectively. 
         [0043]    First, when a user withdraws from a group, i.e., a user belonging to UGn withdraws from UGn, information of all keys included in KS(UGn) must be updated to ensure the forward secrecy with respect to the withdrawn user. Then, update information is transferred to all members of UGn except for the withdrawn user. 
         [0044]    Second, when a user newly joins a user group, i.e., there is a new subscriber in UGn, members included in existing UGn are provided with newly updated key information, and the key information of KS(UGn) is provided to the new subscriber. 
         [0045]    Third, when a member of a user group is changed, i.e., a subscriber included in UGn moves to UGm, keys not belonging to KS(UGm) among key information belonging to KS(UGn) are updated, and key information is transferred to remaining members of UGn, for the sake of the forward secrecy. In addition, for the backward secrecy, members of existing UGm are provided with newly updated key information, and key information of KS(UGm) is provided to the new subscriber. 
         [0046]    Such key information update and distribution is generally managed by a KDC managing a centralized network, and a subscriber group or resource group also needs equipment or an algorithm capable of transceiving key information managed by the KDC. 
         [0047]      FIG. 3  illustrates a conventional hierarchical connection method compared to the present invention. 
         [0048]    A method described in  FIG. 3  is referred to as an MG technique. First, binary key trees are generated which have respective RKns  311  as their roots and UGKs  315  corresponding to US(Rn) as end-nodes. The total number of key trees to be generated is the same as the number n(RS) of Rs. And, key encryption keys (KEKs)  313  are allocated to intermediate nodes of the binary key trees. In  FIG. 3 , “KEK i−j” denotes a KEK that has lower layer keys UGK i and UGK j. When the RKs  311 , KEKs  313  and UGKs  315  are connected using themselves only once while maintaining the property of n(RS) key trees formed as described above, a connection network is configured. Here, the respective trees are compared with each other, and parts having the same parent node and child node in the trees are merged together upon configuration of the network, thereby removing redundancy. 
         [0049]      FIG. 3  shows reconfiguration of the network connections shown in  FIG. 2 . In particular, the tree structure of a part  320  and the tree structure of a part  330  have the same parent node and child nodes. Therefore, the parts  320  and  330  may be merged together when the connection network is configured. 
         [0050]      FIG. 4  shows a configuration of a network using a conventional hierarchical connection method compared to the present invention. Referring to  FIG. 4 , a network is shown which is formed by combining the binary key trees configured in  FIG. 3 . It can be seen that connections of the network configuration of  FIG. 4  are more simplified than those of the network configuration of  FIG. 2 . 
         [0051]    In particular, it can be seen that a part  403  of KEK  6 - 7  is formed by combining  2  binary key trees as described with reference to  FIG. 3 . 
         [0052]    By the configuration of connections using KEKs  401 , the network configuration is simplified in comparison with the original network configuration shown in  FIG. 2 . In addition, by the simplicity of the network configuration, key message transfer redundancy is removed, thus reducing communication cost. 
         [0053]    However, the method checks only a key tree with respect to US(Ri), and thus cannot remove network redundancy in various ways. 
         [0054]      FIG. 5  is a flowchart showing a method of configuring a hierarchical network of a user group and a resource group according to an exemplary embodiment of the present invention. 
         [0055]    Referring to  FIG. 5 , first, hierarchical connections between user groups and resource groups are set up (step  501 ). Subsequently, hierarchical connection redundancies are determined (step  503 ). Here, the hierarchical connection redundancies are determined using UGs as a reference (step  505 ) and using Rs as a reference (step  507 ). Subsequently, on the basis of the determination results, it is determined which reference results in higher hierarchical connection redundancies (step  509 ), and hierarchical connections according to the determined reference are formed into star graphs (step  511 ). Subsequently, an overlapping part is removed while combining the respective hierarchical connections (step  513 ). Finally, hierarchical connections of the entire network are completed (step  515 ). 
         [0056]    In the hierarchical connection method processed according to an exemplary embodiment of the present invention as described above, it is important to find out which reference results in a higher redundancy. Here, when US(Ri) results in a higher redundancy, a US connection mode may be used, and when RS(UGi) results in a higher redundancy, an RS connection mode may be used. 
         [0057]    Such a redundancy is determined using a redundancy rate, which may be determined by a primary redundancy set (PRS). 
         [0058]    Here, the PRS indicates a set that has, as its elements, USs(Ri) each having at least one US(Rj) including the US(Ri) itself, and the elements do not have a common component, or a set that has, as its elements, RSs(UGi) each having at least one RS(UGj) including the RS(UGi) itself, and the elements do not have a common component. 
         [0059]    Here, the PRS of the former case is defined as a US primary redundancy set (UPRS), and the PRS of the latter case is defined as an RS primary redundancy set (RPRS). 
         [0060]    In addition, when elements have a common component, but there are at least 2 USs(Ri) or RSs(UGi) meeting the definition of a PRS, only an element having the largest overlap counter (OC) is included in the PRS. Here, an OC indicates the number of USs(Rj) or RSs(UGj) including a US(Ri) or an RS(UGi) itself. When there are a plurality of elements having the same OC, an element having a large length, i.e., an element having the largest n(US(Ri)) or n(RS(UGi)), is included in the PRS. 
         [0061]    The above-described process can be expressed as an algorithm below. 
       [Algorithm 1] 
       [0062]      
         [0000]    
       
         
               
             
           
               
                   
               
             
             
               
                 1. Determine UPRS using US mode 
               
               
                 1) Determine candidate elements of UPRS satisfying formula below. 
               
               
                   
               
               
                 
                   
                     
                       
                         
                           W 
                           = 
                           
                             { 
                             
                               
                                 
                                   US 
                                    
                                   
                                     ( 
                                     Ri 
                                     ) 
                                   
                                 
                                  
                                 
                                    
                                   
                                     Φ 
                                     
                                       i 
                                       , 
                                       j 
                                     
                                     UG 
                                   
                                 
                                  
                                 
                                   ≥ 
                                   2 
                                 
                               
                               , 
                               
                                 i 
                                  
                                 
                                     
                                 
                                  
                                 and 
                                  
                                 
                                     
                                 
                                  
                                 j 
                                  
                                 
                                     
                                 
                                  
                                 
                                   { 
                                   
                                     1 
                                     , 
                                     2 
                                     , 
                                     … 
                                      
                                     
                                         
                                     
                                     , 
                                     T 
                                   
                                   } 
                                 
                               
                               , 
                               
                                 i 
                                 ≠ 
                                 j 
                               
                             
                             } 
                           
                         
                         , 
                         here 
                         , 
                         
                           T 
                           = 
                           
                             n 
                              
                             
                               ( 
                               RS 
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                   
               
               
                 2) Check whether elements of W do not have common component 
               
               
                   
               
               
                 
                   
                     
                       
                         
                           
                             if 
                              
                             
                                 
                             
                              
                             X 
                           
                           = 
                           
                             
                               { 
                               
                                 
                                   
                                     Wn 
                                      
                                     
                                        
                                       
                                         Φ 
                                         
                                           i 
                                           , 
                                           j 
                                         
                                         UG 
                                       
                                     
                                   
                                   = 
                                   0 
                                 
                                 , 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   and 
                                    
                                   
                                       
                                   
                                    
                                   j 
                                    
                                   
                                       
                                   
                                    
                                   
                                     { 
                                     
                                       1 
                                       , 
                                       2 
                                       , 
                                       … 
                                        
                                       
                                           
                                       
                                       , 
                                       T 
                                     
                                     } 
                                   
                                 
                                 , 
                                 
                                   i 
                                   ≠ 
                                   j 
                                 
                               
                               } 
                             
                             ≠ 
                             φ 
                           
                         
                         , 
                         here 
                         , 
                         
                           K 
                           = 
                           
                             n 
                              
                             
                               ( 
                               W 
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                   
               
               
                 (a) calculate OCs for {X1, X2, . . . , Xn} 
               
               
                 OC = {π1, π2, π3, . . . , πn} 
               
               
                 P = {Xi | MAX(π1, π2, π3, . . . , πn) = πi} 
               
               
                 (b) if n(P) = 1, let add P to UPRS 
               
               
                 (c) else if n(P) ≠ 1, let add MAX(P) to UPRS 
               
               
                 (d) else let add X1 to UPRS 
               
               
                 Otherwise UPRS = W 
               
               
                 2. Determine RPRS using RS mode 
               
               
                 1) Determine candidate elements of RPRS satisfying a formula below. 
               
               
                   
               
               
                 
                   
                     
                       
                         
                           Y 
                           = 
                           
                             { 
                             
                               
                                 
                                   RS 
                                    
                                   
                                     ( 
                                     UGi 
                                     ) 
                                   
                                 
                                  
                                 
                                    
                                   
                                     Ω 
                                     
                                       i 
                                       , 
                                       j 
                                     
                                     R 
                                   
                                 
                                  
                                 
                                   ≥ 
                                   2 
                                 
                               
                               , 
                               
                                 i 
                                  
                                 
                                     
                                 
                                  
                                 and 
                                  
                                 
                                     
                                 
                                  
                                 j 
                                  
                                 
                                     
                                 
                                  
                                 
                                   { 
                                   
                                     1 
                                     , 
                                     2 
                                     , 
                                     … 
                                      
                                     
                                         
                                     
                                     , 
                                     L 
                                   
                                   } 
                                 
                               
                               , 
                               
                                 i 
                                 ≠ 
                                 j 
                               
                             
                             } 
                           
                         
                         , 
                         here 
                         , 
                         
                           L 
                           = 
                           
                             n 
                              
                             
                               ( 
                               US 
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                   
               
               
                 2) Check whether elements of Y do not have a common component 
               
               
                   
               
               
                 
                   
                     
                       
                         
                           
                             if 
                              
                             
                                 
                             
                              
                             Z 
                           
                           = 
                           
                             
                               { 
                               
                                 
                                   
                                     Yn 
                                      
                                     
                                        
                                       
                                         Ω 
                                         
                                           i 
                                           , 
                                           j 
                                         
                                         R 
                                       
                                     
                                   
                                   = 
                                   0 
                                 
                                 , 
                                 
                                   i 
                                    
                                   
                                       
                                   
                                    
                                   and 
                                    
                                   
                                       
                                   
                                    
                                   j 
                                    
                                   
                                       
                                   
                                    
                                   
                                     { 
                                     
                                       1 
                                       , 
                                       2 
                                       , 
                                       … 
                                        
                                       
                                           
                                       
                                       , 
                                       L 
                                     
                                     } 
                                   
                                 
                                 , 
                                 
                                   i 
                                   ≠ 
                                   j 
                                 
                               
                               } 
                             
                             ≠ 
                             φ 
                           
                         
                         , 
                         here 
                         , 
                         
                           M 
                           = 
                           
                             n 
                              
                             
                               ( 
                               Y 
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                   
               
               
                 (a) calculate OCs for {Y1, Y2, . . . , Yn} 
               
               
                 OC = {ψ1, ψ2, ψ3, . . . , ψn} 
               
               
                 H = {Yi | MAX(ψ1, ψ2, ψ3, . . . , ψn) = ψi} 
               
               
                 (b) if n(H) = 1, let add H to RPRS 
               
               
                 (c) else if n(H) ≠ 1, let add MAX(H) to RPRS 
               
               
                 (d) else let add Y1 to RPRS 
               
               
                 Otherwise RPRS = Y 
               
               
                   
               
             
          
         
       
     
         [0063]    Here, 
         [0000]    
       
         
           
             Φ 
             
               i 
               , 
               j 
             
             UG 
           
         
       
     
         [0000]    denotes the number of elements satisfying {((US(Ri) ∩US(Rj))̂((US(Ri)⊂US(Rj))}, 
         [0000]    
       
         
           
             Φ 
             
               i 
               , 
               j 
             
             R 
           
         
       
     
         [0000]    denotes the number of elements satisfying {((RS(UGi)∩RS(UGj))̂((RS(UGi)⊂RS(UGj))}. Here, i and j are elements of {1, 2, . . . , L}, and L is n(RS) in a case of 
         [0000]    
       
         
           
             
               Φ 
               
                 i 
                 , 
                 j 
               
               UG 
             
             , 
           
         
       
     
         [0000]    and L is n(US) in a case of 
         [0000]    
       
         
           
             
               Φ 
               
                 i 
                 , 
                 j 
               
               R 
             
             . 
           
         
       
     
       And,  
       [0064]    
       
         
           
             
               Ω 
               
                 i 
                 , 
                 j 
               
               UG 
             
              
             
                 
             
              
             and 
              
             
                 
             
              
             
               Ω 
               
                 i 
                 , 
                 j 
               
               R 
             
           
         
       
     
         [0000]    are defined below. 
         [0000]    
       
         
           
             
               
                 - 
                 
                   Ω 
                   
                     i 
                     , 
                     j 
                   
                   UG 
                 
               
               = 
               1 
             
             , 
           
         
       
     
         [0000]    if US(Ri) and US(Rj) do not have a common component, i.e., US(Ri)∩US(Rj)=φ, otherwise 
         [0000]    
       
         
           
             
               Ω 
               
                 i 
                 , 
                 j 
               
               UG 
             
             = 
             0 
           
         
       
     
         [0000]    
       
         
           
             
               
                 - 
                 
                   Ω 
                   
                     i 
                     , 
                     j 
                   
                   UG 
                 
               
               = 
               1 
             
             , 
           
         
       
     
         [0000]    if RS(UGi) and RS(UGj) do not have a common component, i.e., RS(UGi)∩RS(UGj)=φ, otherwise 
         [0000]    
       
         
           
             
               Ω 
               
                 i 
                 , 
                 j 
               
               R 
             
             = 
             0 
           
         
       
     
         [0065]    When the algorithm is applied to the network configuration of  FIG. 2 , the UPRS does not have an element satisfying 
         [0000]    
       
         
           
             
               Φ 
               
                 i 
                 , 
                 j 
               
               UG 
             
             ≥ 
             2 
           
         
       
     
         [0000]    and thus becomes a null set. On the other hand, the RPRS has  3  elements RS(UG 4 )={R 1 , R 2 }, RS(UG 5 )={R 1 , R 3 }, and RS(UG 6 )={R 2 , R 3 } satisfying 
         [0000]    
       
         
           
             
               Φ 
               
                 i 
                 , 
                 j 
               
               R 
             
             ≥ 
             2. 
           
         
       
     
         [0000]    In other words, Y={RS(UG 4 ), RS(UG 5 ), RS(UG 6 )}. Subsequently, it must be checked whether elements of Y do not have a common component. Here, elements of Y have a common component. When elements have a common component like this, OCs for respective elements are calculated. In this example, Y( 1 ), Y( 2 ) and Y( 3 ) all have the same OC of 2. When the PRS cannot be determined using OCs like this, one of Y( 1 ), Y( 2 ) and Y( 3 ) having the largest length is determined as an element of the PRS by the method according to an exemplary embodiment of the present invention. However, in this example, Y( 1 ), Y( 2 ) and Y( 3 ) all have the same length of 2. As a result, any one of Y( 1 ), Y( 2 ) and Y( 3 ) can be selected and included in the RPRS as an element. In this algorithm, Y( 1 ) is selected as an element of the RPRS. In other words, RPRS={RS(UG 4 )}. 
         [0066]    In this way, the UPRS and the RPRS can be determined. And, a redundancy rate is obtained through an algorithm below. 
       [Algorithm 2] 
       [0067]      
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 1. Compare redundancy rates of respective redundancy sets 
               
               
                   
                 √ Overlap count of UPRS 
               
               
                   
                 a) {α 1 , α 2 , . . . , α n } 
               
               
                   
                 b) let Q = Σ{α 1 , α 2 , . . . , α n } 
               
               
                   
                 √ Overlap count of RPRS 
               
               
                   
                 a) {β 1 , β 2 , . . . , β n } 
               
               
                   
                 b) let P = Σ{β 1 , β 2 , . . . , β n } 
               
               
                   
                 √ if Q ≧ P, set mode as US mode, else set mode as RS mode 
               
               
                   
                 2. Configure connection network using the determined mode 
               
               
                   
                   
               
             
          
         
       
     
         [0068]    As a result, in the example of  FIG. 2 , hierarchical connections are made using the RS mode. 
         [0069]    Thus far, a process to the step of determining a redundancy reference (step  509 ) has been described in detail. The remaining steps will be described in detail with reference to  FIGS. 6 and 7 . 
         [0070]      FIG. 6  illustrates a method of configuring a hierarchical network of a user group and a resource group according to an exemplary embodiment of the present invention. 
         [0071]    With reference to  FIG. 6 , the method for hierarchical network connection will be described using the network configuration of  FIG. 2 . First, as illustrated in  FIG. 5 , the RS mode is used in the network configuration of  FIG. 2 . Therefore, a star graph can be composed which has UGKs  601  as its root, and has RKs  603  following the root as an end-node. 
         [0072]    Here, when there is a star graph having the same end-nodes RK 1   613  and RK 2   615  as a star graph composed of requirement keys corresponding to RS(UG 4 )={R 1 , R 2 }  610  included in the RPRS, the end-nodes are replaced by the star graph corresponding to the RPRS. 
         [0073]    In  FIG. 6 , the requirement keys corresponding to RS(UG 4 )={RK 1 , RK 2 }  610  include an RK 1   613  and an RK 2   615  that are their end-nodes in a star graph composed of requirement keys corresponding to RS(UG 7 )={R 1 , R 2 , R 3 }  620 . Therefore, a star graph is recomposed which has a UGK 7   621  as its root key, and has the RK 1   613 , the RK 2   615  and an RK 3   617  as its end-nodes to include them as child nodes of the UGK 7   621 . 
         [0074]      FIG. 7  shows a configuration of a network using a method of configuring a hierarchical network of a user group and a resource group according to an exemplary embodiment of the present invention. Referring to  FIG. 7 , hierarchical connections according to respective star graphs composed in  FIG. 6  constitute a connection network  701 . 
         [0075]    After arranging UGKs  703  and RKs  705 , they are connected with each other according to a hierarchical relationship determined between the RKs  705  and the UGKs  703 , thereby integrating the respective star graphs composed in  FIG. 6 . Here, the star graph composed of requirement keys corresponding to RS(UG 4 ) is a part of the star graph composed of requirement keys of RS(UG 7 ), and thus a UGK 4   711  becomes a lower node of a child node of a UGK 7   713 . In addition, when a connection network is configured using the RS mode, the UGKs  703  become root keys, thus forming a contrary structure of  FIG. 7 . Therefore, the structure is turned upside down to dispose upper keys in an upper part, thereby configuring a complete connection network shown in  FIG. 7 . 
         [0076]    According to the present invention, it is possible to provide a method and apparatus for configuring a hierarchical network of a user group and a resource group. 
         [0077]    In addition, it is possible to provide a method and apparatus for configuring a hierarchical network of a user group and a resource group that simplify a network configuration by removing hierarchical connection redundancies from the viewpoint of the user group and the resource group. 
         [0078]    While the invention has been shown and described with reference to certain exemplary embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims.