Key updating system, key management apparatus, communication terminal and key information buildup method in multihop network

The present invention relates to a key update system, a key management device, a communication terminal, and a key information construction method in a multi-hop network. In particular, it relates to a technology for safely updating a key so that a third-party communication terminal outside the network or a communication terminal that wants to be separated from the network cannot identify the updated key. Furthermore, it relates to a technology for securely updating a key so that a communication terminal newly joined to the network cannot identify the key used before.

A multi-hop network is a network in which one or more communication terminals relay data communication between any two communication terminals, and the communication form may be wired or wireless.

Figure 1 shows a general configuration diagram of a multi-hop network system. The multi-hop network system shown in FIG. 1 includes an authentication management device 100 and a plurality of communication terminals 110 that are members of the network, and the communication terminals 110 share the network common key K0. In this multi-hop network, when a certain communication terminal 110 is detached from the network or a new communication terminal 110 is subscribed to the network, the network common key K0 is set so that the communication terminals 110 do not know. It is necessary to update to a new common key K0 ́.

As a method of satisfying the above object, there is a method of using an LKH (Logical Key Hierarchy) key distribution protocol as described in Non-Patent Document 1. The LKH key distribution protocol will be briefly described with reference to FIG. Hereinafter, key information having a hierarchical structure associated with a tree structure, which is a kind of hierarchical structure, is referred to as a "key tree". In the LKH key distribution protocol, the authentication management device manages the key tree for effective key update. Each node (K0, K1, K2, K3, K4, K5, K6) in the key tree represents an encryption key for distributing the key. The authentication management device allocates each communication terminal to the leaves of the key tree (meaning the leaves in the tree structure). At this time, each communication terminal knows all the keys from its own leaf node to the root of the key tree, but does not know the other keys of the key tree. The key K0 located at the root of the tree is a network common key shared by all communication terminals.

Here, suppose that the communication terminal D1 which is a member of the network is to be separated from the network. The authentication management device updates the keys K0, K1, and K3 of the communication terminal D1 among the encryption keys of the key tree managed by itself to K0 ́, K1 ́, and K3 ́, respectively. Then, in order to update the keys K0 and K1 of each communication terminal to K0 ́ and K1 ́, respectively, the authentication management device encrypts E (X, Y) and the message Y using the key X. In terms of meaning, the following key update message is broadcast. E (K4, K1 ́), E (K1 ́, K0 ́), E (K2, K0 ́)

Since the communication terminal D2 knows the key K4, K1 ́ can be obtained from the key update message. Next, the communication terminal D2 can obtain a new network common key K0 ́ by using the key K1 ́ obtained from the key update message. Since the communication terminals D3 and D4 know the key K2, the new network common key K0 ́ can be obtained from the key update message.

On the other hand, the communication terminal D1 does not have the key for decrypting the key update message. Therefore, a new key cannot be obtained. As described above, the LKH key distribution protocol can effectively notify the communication terminal other than the communication terminal D1 that wants to leave the network of the new network common key K0 ́.

<nplcit num="1"><text>"Security of Broadcast Communication in Wired / Wireless Networks" Adrian Perrig, J. Written by D Tyger, translated by Fumio Mizoguchi, Kyoritsu Shuppan pp.120-123</text></nplcit>

<p> However, the above LKH key distribution protocol was not devised assuming a multi-hop network system. In a multi-hop network system, since one or more communication terminals take a communication form of relay relay, the communication load required to deliver the key update message differs for each communication terminal. Until now, there has been no effective method for key update as described above by utilizing the fact that it is a multi-hop network.</p><p> Therefore, the present invention has been made in view of such a problem, and an object of the present invention is a new and improved key update system, key management device, communication terminal, and key information construction method in a multi-hop network. Is to provide.</p>

<p> In a multi-hop network system that includes a key management device that manages keys in a hierarchical structure and a plurality of communication terminals that obtain the keys, key information having a hierarchical structure that matches the multi-hop network structure is constructed, and the key information is stored. The key management device that manages determines the encryption key for encrypting the key based on the key information, and the communication terminal obtains the key. The key management device constructs and manages the key information. The communication terminal is encrypted, including a key information management unit, an encryption unit that encrypts the key using the key in the key information, and a transmission unit that transmits the key encrypted by the encryption unit. A key including a receiving unit for receiving a key, a key management unit for managing a key to be held by itself, and a decryption unit for decrypting an encrypted key among the keys in the key information. An update system is provided.</p><p> According to this configuration, the key tree management device constructs a key tree that matches the multi-hop network structure, sends an encrypted key to the communication terminal, and the communication terminal receives the encrypted key. Then, the encrypted key is decrypted from the key information that it should hold, and the key is obtained. As a result, according to the key update system according to a certain viewpoint of the present invention, the key can be effectively updated by constructing the key tree according to the multi-hop network structure.</p><p> The key management device may further include a key generation unit that generates a key. According to this configuration, the key generation unit generates a key, and the generated key is given to the key information management unit. As a result, a new key can be generated each time the key needs to be updated in the key tree.</p><p> The key management device may further include a one-way value generator having a one-way function. According to this configuration, the one-way value generator generates one or more new keys using the key generated by the key generator as the initial input value of the one-way function. As a result, every time a key in the key tree needs to be updated, a new key is generated, and based on the new key, it is difficult to guess other group keys in the key tree. , One or more new keys can be derived.</p><p> The communication terminal may further include a transmitter that transmits an encrypted key. According to such a configuration, the transmitter transmits the encrypted key to the communication terminal located at the next hop in the multi-hop network. As a result, keys can be awarded in a multi-hop network.</p><p> The communication terminal may further include a key update message analysis unit that analyzes the destination of the encrypted key. According to this configuration, the key update message analysis unit determines information related to its own key update, information to be relayed to the communication terminal located at the next hop in the multi-hop network, and other information. .. As a result, by analyzing the destination of the encrypted key, the necessary key can be transmitted only to the necessary communication terminal.</p><p> The communication terminal may further include a key update message generator that generates a message for transmitting only an encrypted key destined for the communication terminal after the next hop. According to this configuration, the key update message is generated by concatenating the pair of the encrypted key and the index value of the key used for encryption. As a result, the encrypted key can be decrypted and updated with a new key from the received key update message at the communication terminal after the next hop.</p><p> The communication terminal may further include a one-way value generator having a one-way function. According to this configuration, the one-way value generator converts the key given by the key management unit into a new key by applying a one-way function. As a result, from the received key update message, the encrypted key is decrypted, updated to a new key, and then one or more new keys are derived using the new key as the initial input value of the one-way function. be able to.</p><p> In order to solve the above problem, according to another viewpoint of the present invention, it is a key management device that manages key information having a hierarchical structure suitable for a multi-hop network structure, and is a key for constructing and managing key information. A key management device including an information management unit, an encryption unit that encrypts a key using a key in the key information, and a transmission unit that transmits a key encrypted by the encryption unit. Provided.</p><p> According to this configuration, the key information management unit constructs a key tree that matches the multi-hop network structure, and the encryption unit encrypts the key using the key in the key tree constructed by the key information management unit, and the transmission unit. Sends the encrypted key to the multi-hop network. As a result, the key tree management device according to another aspect of the present invention effectively uses the key in the key tree constructed according to the multi-hop network structure in the communication terminal participating in the multi-hop network. Can be updated.</p><p> The key management device may further include a key generation unit that generates a key. According to this configuration, the key generation unit generates a key, and the generated key is given to the key information management unit. As a result, a new key can be generated each time the key needs to be updated in a multi-hop network.</p><p> The key management device may further include a one-way value generator having a one-way function. According to this configuration, the one-way value generator generates one or more new keys using the key generated by the key generator as the initial input value of the one-way function. As a result, every time a key in the key tree needs to be updated, a new key is generated, and based on the new key, it is difficult to guess other group keys in the key tree. , One or more new keys can be derived.</p><p> In order to solve the above problem, according to another viewpoint of the present invention, it is a communication terminal that obtains a key encrypted by using a key in key information having a hierarchical structure suitable for a multi-hop network structure. It includes a receiving unit that receives the encrypted key, a key management unit that manages the key that it should hold among the keys in the key information, and a decryption unit that decrypts the encrypted key. A communication terminal characterized by the above is provided.</p><p> According to such a configuration, the receiving unit receives the encrypted key, and the decrypting unit decrypts the encrypted key. The key management unit manages all the keys existing in the path from the leaf to the root of the tree, which corresponds to itself in the multi-hop network, together with the position indicating the position of the key on the key tree. As a result, the communication terminal according to another aspect of the present invention can effectively update the key in the multi-hop network by using the key in the key tree constructed according to the multi-hop network structure.</p><p> The communication terminal may further include a transmitter that transmits an encrypted key. According to such a configuration, the transmitter transmits the encrypted key to the communication terminal located at the next hop in the multi-hop network. As a result, keys can be awarded in a multi-hop network.</p><p> The communication terminal may further include a key update message analysis unit that analyzes the destination of the encrypted key. According to this configuration, the key update message analysis unit determines information related to its own key update, information to be relayed to the communication terminal located at the next hop in the multi-hop network, and other information. .. As a result, by analyzing the destination of the encrypted key, the necessary key can be transmitted only to the necessary communication terminal.</p><p> The communication terminal may further include a key update message generator that generates a message for transmitting only an encrypted key destined for the communication terminal after the next hop. According to this configuration, the key update message is generated by concatenating the pair of the encrypted key and the index value of the key used for encryption. As a result, the encrypted key can be decrypted and updated with a new key from the received key update message at the communication terminal after the next hop.</p><p> The communication terminal may further include a one-way value generator having a one-way function. According to this configuration, the one-way value generator converts the key given by the key management unit into a new key by applying a one-way function. As a result, from the received key update message, the encrypted key is decrypted, updated to a new key, and then one or more new keys are derived using the new key as the initial input value of the one-way function. be able to.</p><p> In order to solve the above problem, according to another viewpoint of the present invention, the key information construction method has a hierarchical structure in which communication terminals having the same parent terminal device are grouped in a multi-hop network. A key information construction method is provided, which is characterized by constructing key information.</p><p> According to this configuration, a communication terminal determines whether a terminal having a common parent terminal already exists in the key tree, and if so, a subtree formed from terminals having a common parent terminal. Add the terminal to, otherwise add the terminal to the new subtree. This process is executed until all communication terminals are placed on the leaves of the key tree. As a result, the key tree construction method according to another aspect of the present invention can effectively update the key in the multi-hop network.</p><p> If there is no other communication terminal having a common parent terminal in the communication terminal, the key information having a new hierarchical structure may be constructed by using the communication terminal as an initial member of the group. With such a configuration, the key can be effectively updated in the multi-hop network.</p>

<p> As described above, according to the present invention, it is possible to provide a key update system, a key management device, a communication terminal, and a key information construction method in a multi-hop network.</p>

Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings. In the present specification and the drawings, components having substantially the same functional configuration are designated by the same reference numerals, so that duplicate description will be omitted.

(First Embodiment) FIG. 2 is an explanatory diagram showing an internal configuration of an authentication management device according to the first embodiment of the present invention. As shown in FIG. 2, the authentication management device 100 according to the first embodiment of the present invention is an example of a key management device that manages keys hierarchically, and includes a key update trigger transmission unit 101 and key tree management. It includes a unit 102, a key generation unit 103, an encryption unit 104, a key update message generation unit 105, and a transmission unit 106. In this embodiment, the key hierarchy is represented by using a tree structure.

The key update trigger transmission unit 101 generates a key update start message and gives it to the key tree management unit 102. The key update start message is generated when a new communication terminal joins the network or when a communication terminal that is already a member of the network wants to leave the network, but there are various other situations such as when a certain period of time has passed. It may be generated at various timings. For example, when a new communication terminal joins the network, the key update start message includes the ID information of the communication terminal, the authentication key of the communication terminal, and which communication terminal in the network the communication terminal is connected to. The route information indicating the above is given to the key tree management unit 102. The authentication key of the communication terminal is a key shared by the communication terminal and the authentication management device 100 on a one-to-one basis. For example, when a communication terminal that is already a member of the network wants to be detached from the network, the key update message is sent to the key tree management unit 102 as the ID information of the terminal whose ID information of the communication terminal is to be detached. give.

The key tree management unit 102 is an example of the key information management unit, and manages a key tree in which each communication terminal that is a member of the network is used as a leaf in a tree structure. The key tree management unit 102 manages all the keys existing from the root of the key tree to be managed to each leaf and their positions on the key tree. FIG. 4 is an explanatory diagram showing an example of a multi-hop network system, and FIG. 5 is an explanatory diagram showing an example in which a key tree is constructed using the multi-hop network model shown in FIG. The key tree construction method in the present embodiment is characterized in that a subtree having all communication terminals as leaves is formed in the key tree from the authentication management device 100 toward each communication terminal, in which the parent terminal in front of one hop is common. And.

In FIG. 4, the communication terminals D2, D3, and D4 use the communication terminal D1 as a common parent terminal. In this case, the key tree constitutes a subtree with the communication terminals D2, D3, and D4 as a group, that is, as a group with the key K1. Further, in FIG. 4, the communication terminals D5, D6, D7, and D8 have the communication terminal D2 as a common parent terminal. In this case, the key tree constitutes a subtree with the communication terminals D5, D6, D7, and D8 as a group, that is, as a group with the key K2. In the present embodiment, when there are three or more communication terminals forming each group, a binary tree is created as in the LKH described in the prior art, and a subtree is further formed within the group to assign a key. The present invention is not limited to this configuration. A feature of the key tree construction method in the present invention is that a subtree having a communication terminal having the same parent terminal as a leaf is formed.

The key tree management unit 102 receives a key update start message from the key update trigger transmission unit 101, and determines the location of the key to be updated in the key tree to be managed. For example, when the key update start message recognizes that the communication terminal D5 has left the network, the key from the leaf to the root of the tree corresponding to the communication terminal D5 in the key tree, that is, the key to update K6, K2, and K0. Judge. The key tree management unit 102 gives a key request message to the key generation unit 103 by determining the key to be updated, and receives new key information from the key generation unit 103. Then, the key to be updated in the key tree is replaced with the new key given by the key generator 103, which communication terminal needs to be informed of the updated key, and which group key in the key tree is used for encryption. Judge whether it is effective if it is converted.

For example, in FIG. 5, when the communication terminal D5 is disconnected from the network, the keys K6, K2 and K0 need to be updated with the new keys K6 ́, K2 ́ and K0 ́, respectively. First, it is necessary to teach the update of the key K6 to the key K6 ́ only to the communication terminal D6 holding the key K6. For that purpose, it is understood that the key K6 ́ should be encrypted with the key KD6. Next, in order to effectively teach the update of key K2 to key K2 ́ to the communication terminals D6, D7, D8 holding key K2, key K2 ́ was encrypted with keys KD6 ́ and K7, respectively. Prepare things. Finally, in order to effectively teach all communication terminals other than the communication terminal D5 holding the key K0 to update the key K0 to the key K0 ́, the key K0 ́ is used as the key KD1, K1, K2 ́, K3, Prepare the ones encrypted with K4.

As described above, the key tree management unit 102 selects the key at the deepest position in the key tree as the encryption key in order from the key existing at the deepest position in the key tree among the updated keys. Then, the newly updated key, the encryption key used to encrypt the key, the position of the encryption key in the key tree, and the group to which the encryption key belongs are the hops from the authentication management device 100. A set of index values indicating whether or not they exist is given to the encryption unit 104. In the present invention, the position of each encryption key in the key tree and the method of holding the index value indicating the hop number of the encryption key belonging to the group formed from the communication terminal from the authentication management device 100 are particularly described. Although not limited, the key update system using the key tree constructed in the present invention has a configuration in which each communication terminal can determine to which group each encrypted update key is generated as a destination. It is characterized by.

For example, in the key tree of Fig. 5, when indicating the group having the key K0, the index value "0 (no hop &lt;network common key&gt;)" indicates the group having the key KD1 at the position of the communication terminal D1. In the case of "1-0 (0th group located in the 1st hop)" and the index value, in the case of indicating the group with the key K1, "2-0 (0th group located in the 2nd hop)" ) , To indicate the group with the key K5, the index value 2-0-0 (0th group among the 0th groups located in the 2nd hop) is the communication terminal D6. To indicate the group with the key KD6 at the position of, the index value is "3-0-0-1 (the first group in the 0th group in the 0th group located in the 3rd hop)". Is conceivable.

When the key generation unit 103 receives the key request message from the key tree management unit 102, the key generation unit 103 generates a bit string having a random predetermined length and gives the generated key string to the key tree management unit 102. The key generator 103 may include a random number generator.

The encryption unit 104 is given a set of a newly updated key, an encryption key used for encrypting the key, and an index value of the encryption key by the key tree management unit 102. The newly updated key is encrypted using the encryption key, and the index value of the encryption key and the generated encrypted update key are paired and given to the key update message generation unit 105. In the present embodiment, the encryption method used by the encryption unit 104 is not particularly limited, but it is necessary to use a secure encryption method when using this system. Examples of secure encryption methods include AES encryption and 3-DES encryption.

The key update message generation unit 105 is given one or more pairs of the encrypted update key and the index value of the key used for encryption by the encryption unit 104, concatenates the plurality of pairs, and updates the key. Generate a message. The key update message generation unit 105 gives the generated key update message to the transmission unit 106.

The transmission unit 106 broadcasts the key update message given by the key update message generation unit 105 to a communication terminal existing in the network. Various patterns can be considered as the transmission method, such as broadcast, multicast, unicast, broadcast request to the child terminal of the parent terminal, multicast request to the child terminal of the parent terminal, and unicast request to the child terminal of the parent terminal. However, the transmission method is not particularly limited in the present invention. One of these methods may be used, or a combination of multiple of these methods may be used according to the network structure so that the amount of traffic related to key update is minimized. Good.

The internal configuration of the authentication management device according to this embodiment has been described above with reference to FIG. Next, the internal configuration of the communication terminal according to the present embodiment will be described with reference to FIG.

FIG. 3 is an explanatory diagram showing an internal configuration of a communication terminal according to the first embodiment of the present invention. As shown in FIG. 3, the communication terminal 110 according to the first embodiment of the present invention includes a transmission unit 111, a key update message generation unit 112, a reception unit 113, a key update message analysis unit 114, and a terminal. It includes an information management unit 115, a key tree update processing unit 116, a key management unit 117, and a decryption unit 118.

The receiving unit 113 receives the key update message transmitted by the authentication management device 100 or the key update message via another communication terminal 110, and gives the received key update message to the key update message analysis unit 114.

The terminal information management unit 115 shares information indicating which group it belongs to in the key tree with the authentication management device 100. For example, the authentication management device 100 provides information on how many hops it exists from the authentication management device 100 and information indicating which leaf, that is, at which position it exists in the key tree managed by the authentication management device 100. Shared with. How to express this information shall be specified in advance with the authentication management device 100. An index value may be used to represent this information as described in the key tree management unit 102 of FIG. For example, in the case of the communication terminal D6 in FIG. 5, an index value such as "3-0-0-1 (the first communication terminal in the 0th group in the 0th group located at the 3rd hop)". You may use. The terminal information management unit 115 gives this information to the key update message analysis unit 114. It is assumed that the information managed by the terminal information management unit 115 is synchronized with the information of the key tree managed by the authentication management device 100.

The key update message analysis unit 114 is based on the key update message given by the receiving unit 113, the number of hops from its own authentication management device 100 given by the terminal information management unit 115, and its position on the key tree. From the received key update message, the information related to the own key update, the information to be relayed to the communication terminal of the next hop, and other information are determined. The key update message analysis unit 114 checks the index value of the encrypted key, which is paired with the encrypted update key, included in the given key update message in order, and updates its own key in it. The information related to is given to the key tree update processing unit 116, and the information to be relayed to the communication terminal of the next hop is given to the key update message generation unit 112.

For example, in FIG. 5, the communication terminal D1 uses 1-0 E (KD1, K0 ́) || 2-0 E (K1, K0 ́) || 3-0- as the key update message. 0-1 "E (KD6, K6 ́) ||" 3-0-0 "E (K6 ́, K2 ́) ||" 3-0-1 "E (K7, K2 ́) ||" 3-0 " "E (K2 ́, K0 ́) ||" 3-1 "E (K3, K0 ́) ||" 3-2 "E (K4, K0 ́)" is given. Terminal Information Management Department By comparing the information given by 115, that is, the index value "1-0 (0th terminal of the 1st hop)" with the index value included in the key update message, the information corresponding to the key held by itself. Judges that only "1-0" E (KD1, K0 ́) "is used. Therefore," 1-0 "E (KD1, K0 ́)" is updated from the key update message. It is given to the processing unit 116. Next, from the key update messages, the message generated for the first hop communication terminal, which is the number of hops from the own authentication management device 100, is specified, and the other messages are keyed. It is given to the update message generator 112. In the above case, the message "1-0" (KD1, K0) Since it can be seen that all information other than ́) is addressed to the communication terminal after the second hop, all information other than the message 1-0 (KD1, K0 ́) is given to the key update message generator 112. ..

The key tree update processing unit 116 refers to the index value from the set of one or more encrypted update keys given by the key update message analysis unit 114 and the index value of the encryption key. Then, the pair that exists in the deeper position in the key tree is identified, and the decryption work of the encrypted update key is guided in order from the key that exists in the deeper position. The key tree update processing unit 116 gives the index value of the set to the key management unit 117 in order from the selected set, and obtains the decryption key corresponding to the index value from the key management unit 117. Then, the pair of the encrypted update key, the decryption key obtained from the key management unit 117, and the index value indicating the node one depth higher than the position in the key tree indicated by the index value is sent to the decryption unit 118. give. The index value indicating the node one depth higher than the position in the key tree indicated by the index value is, for example, "3-" when the index value of the encryption key is "3-0-0-1". "0-0" corresponds to this. The index value given to the decryption unit 118 indicates the position where the decrypted key exists on the key tree managed by the authentication management device 100.

The decryption unit 118 is given a set of an encrypted update key, a decryption key for decrypting the encrypted update key, and an index value by the key tree update processing unit 116, and uses the given decryption key. Then, the encrypted update key is decrypted to obtain the newly updated key, and the obtained key and the index value are paired and given to the key management unit 117. Here, the decryption method used by the decryption unit 118 needs to correspond to the encryption method of the encryption unit 104 of the authentication management device 100 described with reference to FIG. For example, when the encryption unit 104 of the authentication management device 100 described with reference to FIG. 2 adopts an encryption method using AES encryption, the decryption unit 118 adopts a decryption method using AES encryption.

In the key tree managed by the authentication management device 100, the key management unit 117 manages all the keys existing in the path from the leaf corresponding to itself to the root of the tree together with the index value indicating the position of the key on the key tree. It is a thing. In the key tree, the key existing in the leaf corresponding to itself represents the authentication key shared one-to-one with the authentication management device 100, and the key existing in the root of the tree is held by all communication terminals in the network. Represents a network common key. The key management unit 117 is given an index value indicating the position in the key tree by the key update message analysis unit 114, and among the keys to be managed, the key of the key tree corresponding to the index value is the key tree update processing unit. Reply to 116. In addition, the key management unit 117 is given an index value indicating a position in the key tree and a new key set by the decryption unit 118, so that the given key exists at the position in the key tree indicated by the index value. Manage as a new key. It is assumed that the information managed by the key management unit 117 is synchronized with the information of the key tree managed by the authentication management device 100.

The key update message generator 112 is given one or more pairs of an encrypted update key and an index value of the key used for encryption, and concatenates the plurality of pairs to generate a key update message. is there. The key update message generation unit 112 gives the generated key update message to the transmission unit 111.

The transmission unit 111 broadcasts the key update message given by the key update message generation unit 112 to the communication terminal (node) of the next hop. Various patterns such as broadcast, multicast, and unicast can be considered as the transmission method, but the transmission method is not particularly limited in the present invention. One of these methods may be used, or a plurality of these methods may be combined and implemented according to the structure of the network.

The internal configuration of the communication terminal according to the first embodiment of the present invention has been described above with reference to FIG. Next, a method of constructing a key tree according to the first embodiment of the present invention will be described with reference to FIG.

FIG. 6 is a flow chart showing a method of constructing a key tree according to the first embodiment of the present invention. When the key tree construction process starts, the first communication terminal is first selected (S100). The communication terminal determines whether a terminal having a common parent terminal already exists in the key tree (S110). If a terminal with a common parent terminal already exists in the key tree, add that terminal to the subtree formed from the terminals with a common parent terminal (S120). When a terminal is added, a key tree is constructed in the subtree and placed as a leaf (S130). As a structure for constructing a key tree, a structure such as a binary tree or maybe a tree can be used. In S110 above, if a terminal with a common parent terminal does not already exist in the key tree, a new subtree is created and placed as a leaf (S140).

It is determined whether or not all the communication terminals are placed on the leaves of the key tree (S150), and if all the communication terminals are placed on the leaves of the key tree, the process ends. If the placement is not completed, the process returns to S110 and continues until all communication terminals are placed on the leaves of the key tree.

As described above, the method of constructing the key tree according to the first embodiment of the present invention has been described with reference to FIG. Next, the operation of the key update system according to the first embodiment of the present invention will be described with reference to FIGS. 7 to 12.

FIG. 7 is an explanatory diagram showing the operation performed by the authentication management device 100 when the communication terminal D5 is detached in the multi-hop network model shown in FIG. The internal configuration of the communication terminals D1 to D16 has the same configuration as that of the communication terminal 110.

In order to disconnect the communication terminal D5, the key update trigger transmission unit 101 first gives a key update start message for disconnecting the communication terminal D5 from the network to the key tree management unit 102.

The key tree management unit 102 uses the keys K6, K2, and K0 existing in the path from the leaf corresponding to the communication terminal D5 to the root of the key tree as random values K6 ́, K2 ́, K0 ́ generated by the key generation unit 103. Update to each. Also, to determine from the key tree which communication terminal should be informed of the updated key and which key in the key tree should be used for encryption, and to encrypt the updated key and that key. The encryption key to be used, the position of the encryption key in the key tree, and the index value indicating which subtree it belongs to are paired and given to the encryption unit 104. Which subtree belongs to is, in other words, the key existing in the subtree formed by the communication terminal located at which hop from the authentication management device 100.

In the encryption unit 104, the update key given by the key tree management unit 102 is encrypted with the encryption key also given by the key tree management unit 102, and the generated encryption update key is obtained from the key tree management unit 102. It is given to the key update message generation unit 105 in combination with the given index value.

The key update message generation unit 105 concatenates one or more encryption update keys given by the encryption unit 104 and a set of index values to generate a key update message, and transmits the key update message to the communication terminal through the transmission unit 106. To do. FIG. 8 is an explanatory diagram showing an example of the generated key update message. Figure 8 shows an example in which a set of key update messages addressed to the terminal of the first hop, the terminal of the second hop, and the terminal of the third hop is shown. An index value is added to each encryption update key included in the key update message, and the communication terminal that received the key update message has the number of hops from which the encryption update key is from the authentication management device 100 based on this index value. It is a mechanism that can identify which key in the key tree is the key used for encrypting the encryption update key and whether it was generated for the communication terminal of.

FIG. 9 is an explanatory diagram showing the operation performed by the authentication management device 100 when the communication terminal D17 is subscribed in the multi-hop network model shown in FIG. The communication terminal D17 has the same configuration as the communication terminal 110.

In order to subscribe the communication terminal D17, first, the key update trigger transmission unit 101 gives a key update start message for joining the communication terminal D17 to the network to the key tree management unit 102.

The key tree management unit 102 generates keys K12, K1, K0 existing in the path from the leaf corresponding to the communication terminal D17 to the root of the key tree, and the key generation unit 103 generates random values K12 ́, K1 ́, K0 ́. Update to each. Since the subsequent processing flow is the same as the processing when the communication terminal D5 in FIG. 7 is separated from the network, the description thereof will be omitted.

FIG. 10 is an explanatory diagram showing an outline of how the communication terminal that has received the key update message relays the key update message to the communication terminal of the next hop. The communication terminal that received the key update message determines the hop number of the communication terminal from the authentication management device 100 that one or more encrypted update key and index value pairs included in the key update message are generated. Can be grasped. In the present embodiment, each communication terminal that has received the key update message refers to the information on the hop position from the authentication management device 100 and the index value included in the key update message, and after the next hop. It is characterized in that only the information generated to the communication terminal of is transferred as a key update message.

For example, the communication terminal D1 located on the first hop from the authentication management device 100 refers to the index value included in the key update message addressed to the terminal on the first hop among the key update messages sent from the authentication management device 100. , Only the information generated for the communication terminals after the second hop is transferred to the communication terminals D2, D3, D4 of the second hop. The second hop communication terminals D2, D3, and D4 refer to the index value included in the key update message addressed to the second hop terminal, and only the information generated for the third and subsequent hop communication terminals is displayed for three hops. Transfer to the eye communication terminal.

Next, with reference to FIGS. 11 and 12, in the key update operation when the communication terminal D5 is separated from the network in the multi-hop network model of FIG. 4, the operation performed by the communication terminal D6 when receiving the key update message will be described. ..

Figure 11 shows the operation of distinguishing the information required for own key update, the information to be transferred to the next hop, and the other information among the information contained in the key update message received by the communication terminal D6. It is explanatory drawing.

The key update message is given to the key update message analysis unit 114 from the reception unit 113. Then, the information "3-0-0-1" indicating the position on the key tree and the number of hops from the authentication management device 100 is also given to the key update message analysis unit 114 from the terminal information holding unit. From the own information "3-0-0-1" given by the terminal information holding unit, the fact that it is located in the third hop from the authentication management device 100 and the key on the key tree that it holds are ". It can be seen that they are "3-0-0-1", "3-0-0", "3-0" and "0 (common network key)". The key update message analysis unit 114 compares the index value of the encrypted update key included in the key update message with its own information "3-0-0-1" to obtain "3-0-0-1", It is judged that the encryption update key having the index values of "3-0-0" and "3-0" is the information necessary for the key update held by itself. Then, the encryption update key having the index values of "3-0-0-1", "3-0-0", and "3-0" is given to the key tree update processing unit 116.

Then refer to the other information contained in the key update message. Since it is located at the 3rd hop from the authentication management device 100, the encryption update key generated for the communication terminal after the 4th hop is given to the key update message generation unit 105. In the case of FIG. 11, since the communication terminal after the 4th hop does not exist, the corresponding message does not exist, but if it exists, the key update message generator 105 gives the encryption update key and the index value. The key update message is generated by concatenating the pairs of, and transferred to the communication terminal of the next hop. The remaining information in the key update message given by the receiving unit 113 is information generated for a communication terminal that is located in the third hop from the same authentication management device 100 as itself, but whose parent terminal is different.

FIG. 12 is an explanatory diagram showing the processing of the encryption update key and the index value given to the key tree update processing unit 116.

The key tree update processing unit 116 refers to the index value of the given encryption update key, and performs processing from the set with the deepest position in the key tree. As a result, the processing order is "3-0-0-1", "3-0-0", and "3-0". The following processing is performed in order for each set.

The index value representing the key used to encrypt the encryption update key is given to the key management unit 117 (S200, S220, S240), and the decryption key corresponding to the index value is received from the key management unit 117. (S202, S222, S242).

The key tree update processing unit 116 gives the encryption update key, the key received from the key management unit 117, and the index value indicating the position one position higher than the position of the key tree indicated by the index value to the decryption unit 118. (S204, S224, S244). This index value indicates the position of the newly updated key on the key tree. This is because the updated key is encrypted using a key that is one step deeper than the key in the key tree. The decryption unit 118 decrypts the encryption update key and obtains the newly updated key.

The decryption unit 118 sets the index value with the newly updated key and gives it to the key management unit 117 (S206, S226, S246). Then, the key management unit 117 holds the key given by the decryption unit 118 as a key on the key tree indicated by the index value also given by the decryption unit 118 (S208, S228, S248).

As described above, in the first embodiment of the present invention, the authentication management device manages the key tree by grouping all communication terminals having a common parent terminal in a multi-hop network structure, and the communication terminal. However, when relaying the key update message, only the information generated for the communication terminal with a larger number of hops than itself is extracted from the information contained in the key update message and sent to the communication terminal of the next hop. It is characterized by.

Compared with the conventional method for constructing a key tree such as a binary tree, the method for constructing a key tree according to the first embodiment of the present invention includes all terminals having a common parent terminal in a multi-hop network. To build a subtree and place the subtree under the root of the key tree. Therefore, as the total number of parent terminals increases, the number of subtrees branching from the root of the key tree increases, so the number of communication terminals targeted by one encryption update key decreases, and as a result, the size of the key update message. Becomes larger. On the other hand, the number of keys in the key tree (the number of all keys existing in the route from a leaf to the root) that each communication terminal should hold for key update depends on the total number of communication terminals participating in the network. It depends only on the total number of child terminals connected to a common parent terminal. As described above, the size of the key update message and the number of keys held by the communication terminal have a trade-off relationship, but the key tree is constructed according to the key tree construction method according to the first embodiment of the present invention. Therefore, the size of the key update message can be reduced for each relay because the information to be transmitted to the next hop and the information that is not required to be transmitted to the next hop can be separated for each communication terminal that relays the key update message. be able to.

As described above, in the first embodiment of the present invention, by constructing a key tree according to the multi-hop network structure, the number of keys that each communication terminal should hold for key update is set to a common parent terminal. It is possible to provide a mechanism to suppress the traffic volume of the entire network due to the delivery of the key update message while relying only on the number of connected child terminals.

(Second Embodiment) FIG. 13 is an explanatory diagram showing an internal configuration of the authentication management device according to the second embodiment of the present invention. As shown in FIG. 13, the authentication management device 200 according to the second embodiment of the present invention is an example of the key management device, which includes a key update trigger transmission unit 201, a key tree management unit 202, and a key generation unit. It includes 203, an encryption unit 204, a key update message generation unit 205, a transmission unit 206, and a one-way value generation unit 207. Also in this embodiment, the key hierarchy is represented by using a tree structure. Since the operations of the components other than the key tree management unit 202 and the one-way value generation unit 207 are the same as those of the authentication management device 100 according to the first embodiment, detailed description thereof will be omitted. Here, the key tree management unit 202, which operates differently from the first embodiment, and the one-way value generation unit 207, which is a new component, will be described.

The key tree management unit 202 is an example of the key information management unit, and is basically the same as the operation described in the first embodiment. The difference is the method of generating the update key and the number of keys to be taught to each communication terminal. In the second embodiment, among the keys determined to be updated, the key at the deepest position in the key tree is updated, and the key existing in the route from there to the root of the tree is a one-way function. It is characterized by being generated by using it.

Similar to the first embodiment, the key tree management unit 202 gives a key request message to the key generation unit 203, receives new key information from the key generation unit 203, and updates the key in the key to be updated. Set to the key that exists at the deepest position in the key tree. Next, when updating a key that exists closer to the root of the key tree than the currently updated key, the key tree management unit 202 gives the currently updated key to the one-way value generation unit 207, and gives the one-way value. The key returned from the generation unit 207 is used as the new key. Similarly, when updating a key that exists near one root in the key tree, the output value of the one-way function that inputs the newly updated key is set as the new key.

For example, in Fig. 5, when the keys K6, K2, K0 are updated to the new keys K6 ́, K2 ́, K0 ́ when the communication terminal D5 leaves the network, K2 ́ = f (K6 ́), K0 The relationship of ́ = f (K2 ́) holds. Here, f () indicates a one-way function. Next, in the second embodiment, the number of keys to be taught to each communication terminal is different. When there are multiple keys to be taught to a group of communication terminals, only the key at the deepest position in the key tree is taught among those keys. For example, in Fig. 5, the communication terminal is taught. When D5 leaves the network, the communication terminal D6 is notified only of the update of key K6 to key K6 ́. In addition, the communication terminals D7 and D8 are notified only of the update of the key K2 to the key K2 ́. The other communication terminals are notified of the update of key K0 to key K0 ́.

The one-way value generation unit 207 applies a one-way function to the bit example given by the key tree management unit 202 to generate a bit string having a specified length. The generated bit string is given to the key tree management unit 202. The one-way function held by the one-way value generator 207 must match the one-way function held by the communication terminal, which will be described later. The one-way function used here is not particularly specified, but it is necessary to use a safe method when using the present invention. As an example, a cryptographic hash function SHA-1 (Secure Hach Algorithm-1), a one-way function using a block cipher such as AES, a random number generator, etc. can be used.

FIG. 14 is an explanatory diagram showing an internal configuration of a communication terminal according to a second embodiment of the present invention. As shown in FIG. 14, the communication terminal according to the second embodiment of the present invention includes a transmission unit 211, a key update message generation unit 212, a reception unit 213, a key update message analysis unit 214, and terminal information. It includes a management unit 215, a key tree update processing unit 216, a key management unit 217, a decoding unit 218, and a one-way value generation unit 219. Since the operations of the components other than the key tree update processing unit 216, the key management unit 217, and the one-way value generation unit 219 are the same as those of the communication terminal according to the first embodiment, detailed description thereof will be omitted. Here, the key tree update processing unit 216 and the key management unit 217, which operate differently from the first embodiment, and the one-way value generation unit 219, which is a new component, will be described.

The key tree update processing unit 216 is basically the same as the operation described in the first embodiment. The difference from the first embodiment is that the key update message analysis unit 214 gives only one encrypted update key and a pair of the index value of the encrypted update key. Is.

The key management unit 217 is basically the same as the operation described in the first embodiment. The difference from the first embodiment is that the key given by the decryption unit 218 is managed as a new key existing at the position in the key tree indicated by the index value, so that the position of the new key on the key tree Therefore, the key existing up to the root of the key tree is obtained by using the one-way value generator 219. The key management unit 217 is given a new key by the decryption unit 218, and manages the key as a new key existing at the position in the key tree indicated by the index value. Next, when the index value corresponding to the key is not the root in the key tree, the new key currently given to the decryption unit 218 is given to the one-way value generation unit 219. Then, when the key is given by the one-way value generation unit 219, the key exists at a position close to one root of the position in the key tree indicated by the index value of the key given to the one-way value generation unit 219. Manage as a new key. By repeating this operation up to the root of the key tree, it is possible to obtain an updated key that exists in the root from the leaf to the root corresponding to itself in the key tree.

The one-way value generation unit 219 applies a one-way function to the bit string given by the key management unit 217 to generate a bit string having a specified length, and gives the generated bit string to the key management unit 217. The one-way function held by the one-way value generator 219 must match the one-way function held by the authentication management device 200 described above.

Next, the key update system according to the second embodiment of the present invention will be described with reference to FIGS. 15 and 16. FIG. 15 is an explanatory diagram showing the operation performed by the authentication management device 200 when the communication terminal D5 is detached in the multi-hop network model shown in FIG. The internal configuration of the communication terminals D1 to D16 has the same configuration as that of the communication terminal 210.

In order to disconnect the communication terminal D5, first, the key update trigger transmission unit 201 gives a key update start message for disconnecting the communication terminal D5 from the network to the key tree management unit 202.

The key tree management unit 202 generates a random value of the key K6 existing at the deepest position among the keys existing in the path from the leaf corresponding to the communication terminal D5 to the root of the key tree by the key generation unit 203. Update to K6 ́. Next, the updated key K6 ́ is given to the unidirectional value generator 207, and the key located one level higher in the key tree is used by using the random value f (K6 ́) returned from the unidirectional value generator 207. Set K2 to K2 ́. Similarly, all the keys existing in the route to the root of the key tree are updated to the random values generated by the one-way value generator 207.

Next, if there are multiple keys to be taught to a group of communication terminals, only the key at the deepest position in the key tree is taught among those keys. In the case of FIG. 15, only the update of the key K6 to the key K6 ́ is performed on the communication terminal D6, and only the update of the key K2 to the key K2 ́ is performed on the communication terminals D7 and D8 to the other communication terminals. Teach the update of key K0 to key K0 ́.

The key update message generation unit 205 concatenates one or more encryption update keys given by the encryption unit 204 and a set of index values to generate a key update message, and transmits the key update message to the communication terminal through the transmission unit 206. To do. FIG. 16 is an explanatory diagram showing an example of the generated key update message. Similar to the key update message in the first embodiment, the key update message is an example in which the key update message addressed to the first hop terminal, the second hop terminal, and the third hop terminal is a set. Is shown.

FIG. 17 is an explanatory diagram showing a procedure from the encryption update key and the index value given to the key tree update processing unit 216 to the update of the key managed by the key management unit 217. Similar to the first embodiment, in the multi-hop network model of FIG. 4, in the key update operation when the communication terminal D5 is separated from the network, the operation in which the communication terminal D6 receives the key update message is taken as an example.

In the key tree update processing unit 216, an index value representing the key used when encrypting the update key is given to the key management unit 217 (S300), and the key management unit 217 gives the decryption key corresponding to the index value. Receive (S310). In the present embodiment, the index value "3-0-0-1" is given to the key management unit 217, and the corresponding key KD6 is received from the key management unit 217.

The key tree update processing unit 216 gives the encryption update key, the key received from the key management unit 217, and the index value indicating the position one level higher than the position of the key tree indicated by the index value to the decryption unit 218 ( S320). This index value indicates the position of the newly updated key on the key tree. This is because the updated key is encrypted using a key that is one step deeper than the key in the key tree. The decryption unit 218 decrypts the encrypted update key and obtains the newly updated key. In this embodiment,

The decryption unit 218 sets the newly updated key and the index value and gives them to the key management unit 217 (S330). In this embodiment, the newly updated key K6 ́ and the index value 3-0-0 are paired and given to the key management unit 217. The key management unit 217 holds the key given by the decryption unit 218 as a key on the key tree indicated by the index value also given by the decryption unit 218 (S340). In this embodiment, the key corresponding to the index value 3-0-0 is updated from K6 to K6 ́ and held.

The key management unit 217 obtains and updates the key existing in the path from the position on the key tree of the updated key to the root of the key tree by using the one-way value generation unit 219. In the present embodiment, first, the updated key K6 ́ is given to the unidirectional value generator 219 (S350). The one-way value generator 219 returns f (K6 ́) with K6 ́ as an input value to the key management unit 217 as K2 ́ (S360). The key management unit 217 updates and holds the key corresponding to the index value 3-0 from K2 to the key K2 ́ given by the one-way value generation unit 219 (S370). Furthermore, the updated key K2 ́ is given to the one-way value generator 219 (S380), and the one-way value generator 219 returns f (K2 ́) with K2 ́ as an input value to the key management unit 217 as K0 ́. (S390). The key management unit 217 updates and holds the key corresponding to the index value 0 from K0 to the key K0 ́ given by the one-way value generation unit 219 (S400). In this way, the key existing in the path to the root of the key tree can be obtained and updated by using the one-way value generator 219.

As described above, also in the second embodiment of the present invention, by constructing the key tree according to the multi-hop network structure, the number of keys that each communication terminal should hold for key update is common. It is possible to provide a mechanism to suppress the traffic volume of the entire network due to the delivery of the key update message while relying only on the number of child terminals connected to the parent terminal of.

(Third Embodiment) In the third embodiment, the parent terminal in the multi-hop network further reduces the size of the key update message by managing the information of the child terminals connected via itself. It is characterized by that. The description of the third embodiment will be described based on the second embodiment. The authentication management device 300 according to the third embodiment is an example of the key management device. Since the authentication management device 300 has the same components as the authentication management device 200 according to the second embodiment, the description thereof will be omitted. Also in this embodiment, the key hierarchy is represented by using a tree structure.

FIG. 18 is an explanatory diagram showing an internal configuration of a communication terminal according to a third embodiment of the present invention. As shown in FIG. 18, the communication terminal according to the third embodiment of the present invention includes a transmission unit 311, a key update message generation unit 312, a reception unit 313, a key update message analysis unit 314, and terminal information. It includes a management unit 315, a key tree update processing unit 316, a key management unit 317, a decryption unit 318, a one-way value generation unit 319, and a child terminal information management unit 320.

Here, only the operations of the key update message generation unit 312, which operates slightly differently from the communication terminal according to the second embodiment, and the child terminal information management unit 320, which is a new internal configuration, will be described.

The child terminal information management unit 320 manages which subtree the terminal at its hop destination belongs to in the key tree, such as a child terminal whose parent terminal is itself and a child terminal whose parent terminal is its child terminal. To do. The method of expressing the information that manages which subtree belongs to is defined in advance with the authentication management device. For example, in the key tree shown in Fig. 5, the information managed by the communication terminal D2 is an index value such as "group label of child terminal:" 3-0 "(0th group located at the 3rd hop)". The child terminal information management unit 320 gives the information managed by itself to the key update message generation unit 312. The information managed by the child terminal information management unit 320 is the key managed by the authentication management device 300. It is assumed that it is synchronized with the information of the tree.

The key update message generation unit 312 is basically the same as the operation described in the first embodiment. The difference from the first embodiment is that the child terminal information management unit 320 gives information on which subtree the terminal at its hop destination belongs to in the key tree, and the key is based on the given information. To generate an update message. The key update message generation unit 312 is given by the child terminal information management unit 320 whether or not the pair of the encrypted update key and the index value given by the key update message analysis unit 314 should be sent to the next hop. Judge by information. When it is determined that the information should be sent to the next hop, the pair of the encryption update key and the index value given by the key update message analysis unit 314 is included in the key update message, and the information should not be sent to the next hop. Does not include the pair of encryption update key and index value given by the key update message analysis unit 314 in the key update message.

For example, in the communication terminal D2 shown in FIG. 5, from the key update message analysis unit 314, "" 3-0-0-1 "E (KD6, K6 ́)", "" 3-0-1 "E (K7, Given the index value "K2 ́)", "" 3-1 "E (K3, K0 ́)", "" 3-2 "E (K4, K0 ́)" and the encryption update key, When the index value "" 3-0 "" is given by the child terminal information management unit 320, it is the information generated to the group to which its own child terminal belongs, "" 3-0-0 ". -1 Generate a key update message from "E (KD6, K6 ́)" and "3-0-1" E (K7, K2 ́) ".

Next, the key update method of the key update system according to the third embodiment of the present invention will be described with reference to FIGS. 19 and 20.

FIG. 19 is an explanatory diagram showing an outline of how the communication terminal that has received the key update message relays the key update message to the communication terminal of the next hop. The communication terminals D1 to D16 shown in FIG. 19 have the same internal configuration as the communication terminal 310. As shown in FIG. 19, the communication terminal that received the key update message has one or more encrypted update key and index value pairs included in the key update message, which is the hop number of the communication terminal from the authentication management device 300. It is possible to grasp whether it was generated to the address.

The communication terminal knows the index value indicating the group of child terminals that pass through itself, so that one or more encrypted update key and index value pairs included in the key update message can be sent to the child that goes through itself. It is possible to grasp whether it was generated for the terminal group. In the present embodiment, each communication terminal that has received the key update message has information on the hop position from the authentication management device 300, information on the child terminal group that exists ahead via itself, and information on the child terminal group that exists ahead of the communication terminal. It is characterized by referring to the index value included in the key update message and transferring only the information generated to the communication terminal after the next hop via itself as the key update message.

In FIG. 19, when the communication terminal D1 receives the key update message addressed to the first, second, and third hop terminals from the authentication management device 300, the child terminal information management unit 320 of the communication terminal D1 itself. Is the communication terminal that exists in the first hop from the authentication management device 300, and is addressed to the communication terminals D2, D3, and D4, which are the child terminals of the communication terminal D1, to the second hop terminal via the communication terminal D1. And the key update message addressed to the third hop terminal via the communication terminal D1. When the communication terminal D2 receives the key update message from the communication terminal D1 to the second hop terminal via the communication terminal D1 and the key update message to the third hop terminal via the communication terminal D1, it communicates. The child terminal information management unit 320 of the terminal D2 confirms that it is a communication terminal existing in the second hop from the authentication management device 300, and the communication terminals D5, D6, D7 and D8 which are the child terminals of the communication terminal D2. Sends a key update message to the third hop terminal via the communication terminal D2.

FIG. 20 is an explanatory diagram showing a key update message generation procedure in the communication terminal D2 when the communication terminal D5 is separated from the network in the multi-hop network model shown in FIG.

The key update message generation unit 312 of the communication terminal D2 is given only the information addressed to the communication terminal after the next hop by the key update message analysis unit 314. In addition, the child terminal information management unit 320 gives information on which subtree the terminal at its hop destination belongs to in the key tree.

In the key update message generation unit 312, it is paired with the index value of the child terminal group "3-0" that exists earlier via itself and the encryption update key given by the key update message analysis unit 314. The index values are compared, and it is determined that the information that should be passed to the next hop is the encryption update key having the index values of "3-0-0-1" and "3-0-1".

Then, the key update message generation unit 312 generates a key update message containing only the information to be passed to the next hop, and gives it to the transmission unit 311. The transmission unit 311 transmits a key update message to the communication terminal located in the next hop of the communication terminal D2.

As described above, according to the third embodiment of the present invention, from the first and second embodiments, the parent terminal in the multi-hop network manages the information of the child terminal via itself. The feature is that only the information to be transmitted to the terminal of the next hop is determined from the information contained in the received key update message, the key update message is generated from the information, and the key update message is transmitted to the terminal of the next hop. ..

Therefore, in the case of the first and second embodiments, the number of hops from the own authentication management device is known, and only the key update message addressed to the terminal after the next hop is transmitted. In the case of the third embodiment, the child terminal information via itself is further managed, and the key update message is transmitted only to the terminal after the next hop via itself. The size of the can be reduced. Therefore, there is an effect that the traffic volume of the entire network due to the transmission of the key update message can be further suppressed as compared with the first and second embodiments.

Although the preferred embodiments of the present invention have been described above with reference to the accompanying drawings, it goes without saying that the present invention is not limited to such examples. It is clear that a person skilled in the art can come up with various modifications or modifications within the scope of the claims, which naturally belong to the technical scope of the present invention. Understood.

For example, in the present invention, communication terminals having the same parent terminal form a group in a multi-hop network to construct a subtree, but the method of constructing the subtree within this group is not particularly limited. A feature of the present invention is that communication terminals having the same parent terminal form a subtree as a group, and the formed subtree is arranged in the key tree.

Further, in the third embodiment of the present invention, it has been described as an extension of the second embodiment, but it may be an extension of the first embodiment. That is, the communication terminal may have a child terminal information management unit and not a one-way value generation unit.

Further, in the third embodiment of the present invention, each communication terminal has information on a child terminal that leads to self-confidence, and based on this, only the key update message required for its own child terminal is extracted and relayed. As described above, the authentication management device may have information on the child terminals connected to each communication terminal. In this case, the authentication management device may generate a necessary key update message for each of the first hop terminal that leads to self-confidence and all the communication terminals connected below it, and send it to the corresponding communication terminal.

Further, in the network model used for the explanation of the present invention with reference to FIG. 4, the example described in which the authentication management device broadcasts the key update message and each communication terminal broadcasts the key update message has been described. It is not limited to the configuration. When the authentication management device generates only the key update message required for a certain communication terminal and sends it to that communication terminal by unicast, or only the key update message required for a group of child terminals connected to a common parent terminal. May be used in various patterns and combinations, such as when a parent terminal is requested to send a key update message to its child terminals.

The present invention is applicable to a key information construction method, a key update system, a key management device, and a communication terminal in a multi-hop network.

<figref num="1">It is explanatory drawing which shows the general configuration of a multi-hop network system.</figref><figref num="2">It is explanatory drawing which shows the internal structure of the authentication management apparatus which concerns on 1st Embodiment of this invention.</figref><figref num="3">It is explanatory drawing which shows the internal structure of the communication terminal which concerns on 1st Embodiment of this invention.</figref><figref num="4">It is explanatory drawing which shows the multi-hop network model which concerns on 1st Embodiment of this invention.</figref><figref num="5">It is explanatory drawing which shows the structure of the key information which has the hierarchical structure associated with the tree structure which concerns on 1st Embodiment of this invention.</figref><figref num="6">It is explanatory drawing which shows the construction method of the key information which has the hierarchical structure associated with the tree structure which concerns on 1st Embodiment of this invention.</figref><figref num="7">It is explanatory drawing which shows the operation of the authentication management apparatus at the time of leaving a communication terminal which concerns on 1st Embodiment of this invention.</figref><figref num="8">It is explanatory drawing which shows the example of the key update message which concerns on 1st Embodiment of this invention.</figref><figref num="9">It is explanatory drawing which shows the operation of the authentication management apparatus at the time of joining a communication terminal which concerns on 1st Embodiment of this invention.</figref><figref num="10">It is explanatory drawing which shows the outline of the relay method of the communication terminal which received the key update message which concerns on 1st Embodiment of this invention.</figref><figref num="11">It is explanatory drawing which shows the operation of the communication terminal which received the key update message which concerns on 1st Embodiment of this invention.</figref><figref num="12">It is explanatory drawing which shows the processing of the encryption update key and the index value given to the key tree update processing part which concerns on 1st Embodiment of this invention.</figref><figref num="13">It is explanatory drawing which showed the internal structure of the authentication management apparatus which concerns on 2nd Embodiment of this invention.</figref><figref num="14">It is explanatory drawing which shows the internal structure of the communication terminal which concerns on 2nd Embodiment of this invention .</figref><figref num="15">It is explanatory drawing which shows the operation of the authentication management apparatus at the time of leaving a communication terminal which concerns on 2nd Embodiment of this invention.</figref><figref num="16">It is explanatory drawing which shows the example of the key update message which concerns on 2nd Embodiment of this invention.</figref><figref num="17">It is explanatory drawing which shows the procedure until the key managed by the key management part is updated which concerns on 2nd Embodiment of this invention.</figref><figref num="18">It is explanatory drawing which showed the internal structure of the communication terminal which concerns on 3rd Embodiment of this invention.</figref><figref num="19">It is explanatory drawing which shows the outline of the relay method of the communication terminal which received the key update message which concerns on 3rd Embodiment of this invention.</figref><figref num="20">It is explanatory drawing which shows the key update message generation procedure at the time of leaving a communication terminal which concerns on 3rd Embodiment of this invention.</figref><figref num="21">It is explanatory drawing which showed the LKH key distribution protocol.</figref>

Code description

100,200,300 Authentication management device 101,201 Key update trigger transmission unit 102,202 Key tree management unit 103,203 Key generation unit 104,204 Encryption unit 105,205 Key update message generation unit 106,206 Transmission unit 110,210,310 Communication terminal 111,211,311 Transmission unit 112,212,312 Key update message generation unit 113,213,313 Reception unit 114,214,314 Message analysis unit 115,215,315 Terminal information management unit 116,216,316 Key tree update processing unit 117,217,317 Key management unit 118,218,318 Decryption unit 207,219,319 One-way value generation unit 320 Child terminal information management unit