Encryption key update method, encryption key update device, and encryption key update program

The present invention focuses on a key update method with respect to a method of managing an encryption key required for performing secure network communication in a network that uses an encryption key and communicates using a plurality of communication devices. The present invention relates to an encryption key update method, an encryption key update device, and an encryption key update program.

In network communication that uses an encryption key to communicate using multiple communication devices, a network that uses a large number of sensor-equipped wireless communication devices (nodes) is generally called a sensor network and is placed within the measurement target area. It is a system that collects the information acquired by the obtained nodes by wireless communication and utilizes the collected information in an application, and is attracting attention as a system that can be used for various purposes. Hereinafter, in the present invention, in network communication in which communication is performed using a plurality of communication devices using an encryption key, a network composed of a server and a node connected to the server as a communication device to be configured. In particular, a sensor network will be described as an example.

In many aspects of sensor network usage, it is possible that a group may be formed by multiple nodes and information may be shared or processed within the group. The group key is a key that is commonly owned only by the nodes belonging to the group, and by generating and using the encryption key and MAC key from the group key, it is possible to use various encryption technologies within the group. Become. In that sense, managing group keys safely and efficiently can be considered to be an important basic technology for constructing realistic sensor network applications. For example, consider the case of performing multicast distribution of secret data for a certain group. Considering the existence of unauthorized persons who eavesdrop on the communication path and nodes outside the group that relay data, the data distributed by multicast needs to be encrypted. At this time, it should be noted that the ciphertext delivered by multicast must be the same for all the nodes in the group. If it is necessary to configure different ciphertexts using different encryption keys for each node, there is no point in performing multicast distribution. The existence of a group key is essential in order to distribute the same ciphertext to a network that can be accessed by an unspecified number of people and to realize a mechanism that allows only members belonging to the group to decrypt it. I can say.

Group key management poses a different difficulty than one-to-one encryption key management. A major feature of group key management is that the composition of the group changes over time. For example, it should be noted that a new node may join a new group, or a node that previously belonged to a group may leave the group for some reason. If there is a change in the group members, it is necessary to update the group key and distribute the updated key correctly. In particular, when forcibly excluding a node from the group, it is necessary to properly control the information so that the excluded node does not continue to own a valid group key.

The most basic key update method with a sensor network in mind is, for example, as shown in Non-Patent Document 1, a key (link key) shared in advance on a one-to-one basis between any node pair including a server. ) Is used (conventional method 1). For example, when one group key is shared by a group composed of a plurality of nodes, a key update is required when excluding a certain node, but in the conventional method 1, a server or the like is required to update the key. The representative node determines a new group key, encrypts the group key using the link key, and unicasts the encrypted group key to other nodes except the node to be excluded.

Further, in Patent Document 1, a plurality of keys are assigned to the extended vertices of the tree structure based on the group key corresponding to a certain group, and then all the nodes to be joined to the plurality of groups are arranged at each vertices of the tree structure. Associated with a key, each node's encryption key is generated as a key string having a key from the root of the tree structure to the position associated with the node in the tree structure, and the generated encryption key is transferred to the corresponding node. The method of delivery is disclosed. (Conventional method 2). Due to such a tree structure, when an exclusion node appears from among multiple nodes, only the key related to the encryption key possessed by the exclusion node is changed, and only the node corresponding to the changed key is changed. The encrypted key can be encrypted and distributed with the key directly under the key.

Further, in Patent Document 2, in a network system configured by grouping a plurality of nodes so that each node belongs to a plurality of groups, each node in the group is directly connected, and each node has its own node. Each node is provided with a node connection means for broadcasting to all other nodes of the group to which the node belongs, and each node receives data received from another node of one of the plurality of groups to which the node belongs. A method of relaying by broadcasting to other nodes of other groups among a plurality of groups to which the group belongs is disclosed. (Conventional method 3). When the conventional method 3 is used, when transmitting common data to a set of nodes, the data is transmitted to the nodes (relay nodes) that straddle each group, and the data is broadcasted. Can be delivered efficiently.

Further, in Patent Document 3, in a communication system composed of a center and a plurality of terminals, in which each terminal forms a group and shares the same secret key in the group, the secret key is obtained by using a surplus calculation such as a secret sharing method. The method of updating is disclosed (conventional method 4). The conventional method 4 aims to reduce the burden of encryption processing on the center side, and can update the private key on the terminal side, which requires the terminal side to perform the remainder calculation based on the secret sharing method.

<p><patcit num="1"><text>Japanese Unexamined Patent Publication No. 11-187013</text></patcit><patcit num="2"><text>Japanese Patent No. 2852586</text></patcit><patcit num="3"><text>Japanese Unexamined Patent Publication No. 2004-343816</text></patcit></p>

<p><nplcit num="1"><text>Zigbee® Sensor Network pp. 118-120, Shiro Sakata et al., Shuwa System, 2005</text></nplcit></p>

<p num="0011"> However, in the communication equipment constituting the network, in the network communication where the computational resources are limited, such as the miniaturization of the chip and the memory is desired, it is necessary to securely perform the communication and update the encryption key, and the key. It is required to reduce the amount of communication in updating and the amount of calculation by updating the key.</p><p num="0012"> On the other hand, in the conventional method 1, the amount of communication transmitted from the server to the network is O (N) when the number of nodes in the group is N. That is, there is a problem that the amount of communication for key update increases in proportion to the number of nodes. On the other hand, in the conventional method 2, this communication amount is O (log N). That is, there is a problem that the amount of communication for key update increases in proportion to the logarithm of the number of nodes. Although it is more efficient than the conventional method 1, the same problem may occur in that the amount of communication from the server for key update becomes a problem when the number of nodes increases. Especially in an environment such as a sensor network where the number of nodes is expected to increase by an order of magnitude compared to conventional systems, this problem is expected to become apparent even if the amount of communication is proportional to the logarithm of the number of nodes. Will be done.</p><p num="0013"> On the other hand, although it is conceivable to use the conventional method 3 as a communication means for delivering the encryption key, there is a problem that it cannot be dealt with when the relay node is excluded. Also, considering the possibility that the relay node is a node outside the group, there is a risk that the encryption key information will be leaked to the relay node.</p><p num="0014"> Further, the conventional method 4 is a key update method based on the secret sharing method, and a large amount of calculation using a remainder calculation under a huge prime number p or a large number of remainder operations is indispensable. In the method of updating the group key using such a remainder calculation, the amount of calculation is generally very large as in the public key method. However, especially in the computational resources used for communication equipment on the node side such as sensor networks, the conventional method is used because the amount of calculation on the node side is limited in an environment where the computational capacity and storage capacity that can be implemented are limited. A method that requires a large number of remainder calculations such as 4 cannot be used.</p><p num="0015"> Therefore, the present invention solves the above-mentioned problems, and prepares for a case where the composition of a group in a communication device changes according to the progress of time in a network communication in which communication is performed using a plurality of communication devices by using an encryption key. It provides a mechanism for updating the group key, which is an encryption key, and securely distributing the updated key within the group, and aims to reduce the amount of communication and the amount of calculation in key update.</p>

<p num="0016"> According to the present invention, in a network composed of a server and a large number of nodes, when d types of attributes exist in the nodes, it is considered that the nodes belong to d groups at the same time, and for each group defined in this way. When there is a change in the group members regarding the method of associating the group key with each other, sharing the group key only with the nodes belonging to the group, and performing encrypted communication for each group, the server A method of updating the group key and correctly distributing the updated group key so that when a node is forcibly excluded from the group, the excluded node will not continue to own a valid group key. , Controls group key distribution, and when the node to be excluded is a group head node, the group head node which is the node to be excluded and other nodes in the minimum group to which the group head belongs By exchanging roles in, the node to be excluded is made a node that is not a group head node, and the updated group key is transferred to a node other than the node to be excluded in the corresponding group via the group head node. By sending, the group head node exclusion step of excluding the node to be excluded is provided, and the minimum group is the product of a plurality of groups obtained as a result of extracting one group having an arbitrary attribute value for each attribute. It is a group that is a set and is a non-empty minimum set, and the group head node is a node belonging to a group that includes exactly one node in a product set with an arbitrary minimum group. An encryption key update method is provided. Further, according to the present invention, in a network composed of a server and a large number of nodes, when d types of attributes exist in the nodes, it is considered that the nodes belong to d groups at the same time, and each group defined in this way. When there is a change in the group members regarding the method of associating the group key with the server, sharing the group key only with the nodes belonging to the group, and performing encrypted communication for each group. A way for the server to update the group key and deliver the updated key correctly, so that if a node is forcibly removed from the group, the excluded node will not continue to own a valid group key. Assuming that the group key distribution is controlled and the attribute is the division of all node sets N, (Condition 1) GiN, (Condition 2) If i j, GiGj is an empty set (Condition). 3) G1G2. .. .. Family of sets {G1, G2, which satisfy the three conditions of Gm = N. .. .. , Gm} is called an attribute, and d attributes A1,. .. .. , Ad, Ai = {Gi, 1,. .. .. , Gi, mi} (mi is the number of elements of Ai), and if Gi, j is a set of nodes having the jth attribute value for the attribute i, k integers 1 i1,. .. .. , Ik, d and k groups Gi1, j1,. .. .. , Gik, jk (however, for 1 a k, Gia, ja Aia) exists, and G = Gi1, j1. .. .. When the node set G such as Gik and jk is a group of order k, d attributes constituting group C (minimum group) of order d, which is a minimum set in the inclusion relationship between structured groups. In addition to (Condition 4), CG0,1 includes exactly one node (group head) for any minimum group C, and (Condition 5) A group other than G0,1 in any minimum group C, A0. A special attribute A0 = {G0,1,. That is configured so that CG0, j contains at most one node (group member) with respect to G0, j. .. .. , G0, m0} (where m0&gt; 0) is introduced, and d + 1 attribute sets A0, A1,. .. .. , Ad Since the nodes belong to exactly one minimal group and A0 is a division of the node set N, d + 1 integer set j0, j1,. For any node n. .. .. , Jd exists, and G0, j0G1, j1. .. .. It can be expressed as Gd, jd = {n}, and the d + 1 character set (j0, j1, ..., jd) is treated as the identifier (ID) of the node n. A0, A1,. .. .. Considering the case where Ad defines a d-dimensional group structure, at this time, the server is a node belonging to a group Gi, j (0 i d, 1 j mi) of order 1 and a group key ki, j ( (Called an element key) is shared in advance, and the group G = Gi1, j1. .. .. Gik, jk (i1 &lt;... &lt;ik), h (ki1, j1 || ... || kik, jk) (h is a hash function, || is a key concatenation) on the server and node The information that can be calculated is the group key k (G) of G. Only the node belonging to G knows the group key k (G) of the group G of the rank k. At this time, the server or the node belonging to G encrypts the data to be transmitted to G by k (G). Multicast the obtained ciphertext to the G node and distribute it. Assuming that the ID of the node n is (j0, j1, ..., jd), n is d + 1 element keys k0, j0 ,. .. .. , Kd, jd, and by using these d + 1 keys, n can calculate kn = h (k0, j0 || ... || kd, jd), and this value kn is n. And since only the server is a calculable value, the server uses kn as the key shared between n and the server (node key), and the server encrypts the data for each node with its own node key. Safely send in a unicast manner In order to enable a secure one-to-one message exchange between the group head and each group member of the smallest group to which the group head belongs, the server has each of the group head and each group member. A unique key (member key) common to the node key is encrypted and sent in a unicast manner. When the server wants to add the node n to the group Gi, j of the order 1, if the code statement obtained by encrypting the data x with the key k is written as Ek (x), the node addition means provided in the server is , C = Eh (ki, j) (ki'i, j) is calculated for the nodes that have belonged to Gi, j for a long time, and c is multicast-distributed to the nodes belonging to Gi, j, and for n. By encrypting the new key k'i, j in a unicast manner with the node key shared only by the server and its node and transmitting it from the server, the new key k'i, j is transmitted while ensuring backward security. In the new group Gi, j, When the server excludes the node n from the group Gi, j of rank 1, if the set obtained by removing n from Gi, j is written as G'i, j, G'i, j will remain in the group even after the exclusion of n. All nodes belonging to G'i, j must be able to obtain new keys k'i, j, and the node n to be excluded is excluded in order to ensure forward security. Since it is necessary not to know k'i and j, the main node exclusion means provided in the server cooperates with the sub-node exclusion means provided in the group head that always exists in the minimum group, and the node exclusion means. Perform the processing of When the server excludes the node n from the group Gi, j of rank 1, if the exclusion node n is not the group head and i 0 for the element groups Gi, j excluding n, the main node exclusion means of the server. First, when ki and j are the element keys of Gi and j and k'i and j are the element keys of the new Gi and j, k = h (k0,1 || ki, j) is calculated and x. = Ek (k'i, j) is obtained, and a 4-character set (i, j, IDn, x) is multicast-transmitted to a node (group head) belonging to Gi, jG0,1 (IDn is excluded). The ID of the node n), and then the sub-node exclusion means of the node (group head) belonging to Gi, jG0,1 decodes x to obtain the new keys k'i, j of Gi, j, and finally. In addition, when the sub-node exclusion means of the node (group head) belonging to Gi, jG0,1 does not include the exclusion node n in the minimum group C to which the own node belongs, k (C) (the minimum group C to which the own node belongs). K'i, j is encrypted using the group key of), and Ek (C) (k'i, j) is multicast-distributed to the group members of C, while the exclusion node is distributed to the minimum group C to which the group head belongs. When n is included, the subnode exclusion means of the group head unicastly encrypts k'i and j using the member key and transmits them to the group members of C other than n. When the server excludes the node n from the group Gi, j of rank 1, if the exclusion node n is not the group head and i = 0 and j 1 for the element groups Gi, j excluding n, the server The main node exclusion means calculates x1 = Eh (k0, j) (k'0, j) and x2 = Eh (k0,1) (x1), and obtains a 4-character set (0, j, IDn, x2). Multicast distribution is performed to the set G0,1 of the group heads, and the subnode exclusion means of each group head decodes x2 to obtain x1 (since the group head does not know k0, j, x1 cannot be decoded). , G0, j and the minimum group C to which it belongs include one node n', and if n n', the subnode exclusion means of the group head is uni-node to n'with a member key. Encrypt x1 as a cast and send it When the server excludes the node n from the group Gi, j of rank 1, when i = 0 and j = 1, that is, the exclusion node n is the group head, the main node exclusion means provided in the server excludes n. Performs the process of exchanging the roles of the group heads n of the groups Gi and j and the nodes n'in the minimum group to which the group heads belong, and performs the node exclusion process when the exclusion node is not the group head after the role exchange process is completed. An encryption key renewal method characterized by enforcement is provided. Further, according to the present invention, in a network composed of a server and a large number of nodes, when d types of attributes exist in the nodes, it is considered that the nodes belong to d groups at the same time, and each group defined in this way. When there is a change in the group members regarding a system in which a group key is associated with a node, the server shares the group key only with the nodes belonging to that group, and encrypted communication is performed for each group. A system in which the server updates the group key and correctly distributes the updated group key, and when a node is forcibly excluded from the group, the excluded node continues to own a valid group key. If the node to be excluded is a group head node, the server controls the group key distribution so that the group head node, which is the node to be excluded, and other nodes in the minimum group to which the group head belongs. By exchanging roles with the node, the node to be excluded is changed to a node that is not a group head node, and the updated group key is transferred to a node other than the node to be excluded in the corresponding group. It has a group head node exclusion means for excluding the node to be excluded by sending via, and the minimum group is a plurality of groups obtained as a result of extracting one group having an arbitrary attribute value for each attribute. A group that is a product set of and is a non-empty minimum set, and the group head node is a node belonging to a group that includes exactly one node in the product set with an arbitrary minimum group. An encryption key update system characterized by is provided.</p>

<p num="0017"> According to the present invention, in network communication in which an encryption key is used to perform communication using a plurality of communication devices, the group key, which is an encryption key, is updated in case the network configuration changes with the progress of time. , It is possible to provide a mechanism to securely distribute the updated key. In addition, the amount of communication and the amount of calculation in key update can be reduced.</p>

<figref num="1">It is a figure which shows the structure of one Embodiment for carrying out this invention.</figref><figref num="2">It is a figure explaining the Example in this invention.</figref><figref num="3">It is a flow chart which shows the outline operation which excludes n from group Gi, j.</figref><figref num="4">It is a flow chart which shows the operation which excludes n from a group Gi, j (i 0).</figref><figref num="5">It is a flow chart which shows the operation which excludes n from a group Gi, j (i = 0 and j 1).</figref><figref num="6">It is a flow chart which shows the operation which excludes n from a group Gi, j (i = 0 and j = 1).</figref><figref num="7">It is a figure which shows the example of the case where n is excluded from the group Gi, j (i 0).</figref><figref num="8">It is a figure which shows the example of the case where n is excluded from the group Gi, j (i = 0 and j 1).</figref><figref num="9">It is a figure which shows the example of the case where n is excluded from the group Gi, j (i = 0 and j = 1).</figref>

Hereinafter, the best mode for carrying out the present invention will be described in detail with reference to the drawings.

Generally, it is considered that one sensor node has a plurality of attributes. For example, the production lot number, firmware version, installation location, type of sensor to be equipped, etc. can all be attributes. The sensor node is considered to have some attribute value for each attribute.

In the present invention, it is assumed that one group is composed of a set of nodes having the same attribute value for a certain attribute, a group key is associated with each group defined in this way, and the group key is assigned to the group. This is an encryption key management method that is distributed only to the nodes that belong to.

Therefore, if there are d types of attributes, the nodes belong to d groups at the same time. Consider associating a group key with each group defined in this way and distributing the group key only to the nodes belonging to that group.

The present invention is a method of updating the group key and correctly distributing the updated key when there is a change in the group members, and particularly when a node is forcibly excluded from the group. This is an encryption key update method that appropriately controls group key distribution so that the node to be used does not continue to own a valid group key.

FIG. 1 shows an overall configuration in an embodiment of the encryption key management method of the present invention. Referring to FIG. 1, in the present embodiment, in a network represented by a sensor network, a set N consisting of all nodes and a server 101 not belonging to N are configured, and the server 101 operates by program control and adds a node. The means 103, the main node exclusion means 105, and the key storage means 107 are provided, and the node includes the sub-node exclusion means 109 and the key storage means 111. As for the node, only node 1 is typically described. The difference between the key storage means 107 of the server and the key storage means 111 of the node is the difference of the key (secret information) that is stored and managed in the key storage means. Manages only the group key that is valid only in the group to which it belongs and the processing key (member key described later) that is required for the processing of joining and excluding the group of nodes.

Nodes also operate by program control in operations related to keys.

Hereinafter, the data encryption operation using symmetric key encryption will be used, but it is assumed that the network participants understand the algorithm used for encryption, and the server and each node can perform encryption and decryption. In particular, it is assumed that the information encrypted with the key owned by each of the server and each node can be decrypted with an appropriate key and the decryption result can be obtained.

Also, assume that the attribute is a division of the set N consisting of the entire node, and in particular, GiN. .. .. (Condition 1) If i j, then GiGj is the empty set. .. .. (Condition 2) G1G2. .. .. Gm = N. .. .. (Condition 3) Family of sets {G1, G2, ... .. .. , Gm} is called an attribute.

In addition, d attributes A1, ... .. .. , Ad, Ai = {Gi, 1,. .. .. , Gi, mi} (mi is the number of elements of Ai), and if Gi, j is a set of nodes having the jth attribute value for the attribute i, k integers 1 i1,. .. .. , Ik d and k groups Gi1, j1,. .. .. , Gik, jk (however, for 1 a k, Gia, ja Aia) exists, and G = Gi1, j1. .. .. When the node set G such as Gik and jk is a group of order k, d attributes constituting group C (minimum group) of order d, which is a minimum set in the inclusion relationship between structured groups. In addition to For any minimal group C, CG0,1 includes exactly one node (group head) (condition 4), CG0, j includes at most one node (group member) for groups G0, j other than G0, 1 in any minimal group C, A0 (condition 5). A special attribute A0 = {G0,1,. .. .. , G0, m0} (where m0&gt; 0) is introduced, and d + 1 attribute sets A0, A1,. .. .. The group key is updated and managed in a d-dimensional group structure composed of , Ad.

In addition, since the nodes belong to exactly one minimum group and A0 is a division of all node sets N, d + 1 integer set j0, j1,. For any node n. .. .. , Jd exists, G0, j0 G1, j1 . .. .. It can be expressed as Gd, jd = {n}, and the d + 1 character set (j0, j1, ..., jd) is treated as the identifier (ID) of the node n.

In addition, A0, A1, ... .. .. Considering the case where Ad defines a d-dimensional group structure, at this time, the server is a node belonging to a group Gi, j (0 i d, 1 j mi) of order 1 and a group key ki, j ( (In particular, it is called an element key) is shared in advance, and the group G = Gi1, j1 . .. .. Gik, jk (i1 &lt;... &lt;ik), h (ki1, j1 || ... || kik, jk) (h is to set the length of the concatenated key such as a hash function to a predetermined value. The information that can be calculated by the server and the node as the function of, || is the key concatenation) is the group key k (G) of G.

Further, only the node belonging to G knows the group key k (G) of the group G of the digit k, and at this time, the server or the node belonging to G encrypts the data to be transmitted to G by k (G). The obtained ciphertext is multicast and distributed to the G node.

If the ID of the node n is (j0, j1, ..., jd), n is d + 1 element keys k0, j0 ,. .. .. , Kd, jd, and by using these d + 1 keys, n can calculate kn = h (k0, j0 || ... || kd, jd), and this value kn is n. And because only the server is a calculable value, the server uses kn as the key shared between n and the server (called the node key), and the server gives each node data with its own node key. Encrypt and send in a unicast manner.

In addition, in order to enable safe one-to-one message exchange between the group head and each group member of the micro group to which the group head belongs, the server sends the group head and each group member to each other. A unique key (member key) common to each node key is encrypted and transmitted in a unicast manner.

The means for adding the node n to the group Gi, j of the order 1 (node addition means) is as follows. Such cases can occur, for example, when you want to add a new node to a running sensor network, or when the attribute values of an existing node are changed for some reason. In any case, the node n who newly joins the group does not have the right to know the key used as the group key of Gi, j before joining. Conversely, in the process of adding n as a member of a group, n must not know the previous group key. This property is called backward security in the group key.

Further, when the server wants to add the node n to the group Gi, j of the order 1, if the code sentence obtained by encrypting the data x with the key k is written as Ek (x), the node addition means provided in the server. Calculates c = Eh (ki, j) (k'i, j) for the nodes that have previously belonged to Gi, j, multicasts c to the nodes that belong to Gi, j, and sets it to n. On the other hand, by encrypting the new key k'i, j in a unicast manner with the node key shared only by the server and its node and transmitting it from the server, the new key k'i, while ensuring backward security, Share j with new groups Gi, j.

The means for excluding the nodes belonging to the groups Gi and j from Gi and j (node exclusion means) are as follows. Cases of excluding a node from the group include cases where the attribute value of the node changes, a node that has stopped due to a failure, etc. is excluded from the network, and a node may be hijacked by an unauthorized person. Conceivable. Especially in the last case, it is possible that confidential information may be leaked through the hijacked node, or the hijacked information may attack other nodes or communication infrastructure, so eliminate the node as soon as possible. Is strongly required. It should be noted that nodes excluded from the group may continue to try to retain the group key by improper means. In the protocol for excluding nodes, the new keys k'i, j are reliably delivered to the nodes that continue to Gi, j, and k'i, j (and are used thereafter) for the excluded users. The group key) must not be passed. This property is called forward security in the group key.

Ensuring forward safety is more technically difficult than ensuring backward safety. In fact, there is no essential difference in key knowledge between the nodes that remain in Gi, j and the nodes n that are excluded. For example, both the nodes remaining in Gi, j and n themselves know the group keys ki, j that have been used in Gi, j so far. Therefore, it is difficult to ensure forward security by a simple method such as distributing the new keys k'i, j using the old group keys ki, j as in the node addition in the previous section.

Further, when the server excludes the node n from the group Gi, j of rank 1, if the set obtained by removing n from Gi, j is written as G'i, j, G'i, j will be after the exclusion of n. Is a set of nodes that remain in the group, and all nodes belonging to G'i, j must be able to obtain new keys k'i, j, and are excluded to ensure forward security. Since it is necessary to prevent n from knowing k'i and j, the main node exclusion means provided in the server cooperates with the sub-node exclusion means provided in the group head that always exists in the minimum group to eliminate the nodes. Perform the processing of.

When the server excludes the node n from the group Gi, j of the order 1, the main node exclusion means provided in the server is for the group Gi, j of the order 1 that excludes n when the exclusion node n is not the group head. , I 0 and i = 0 (in the latter case, j 1 automatically because n is not a group head), the subnode exclusion means provided by the node that becomes the group head. Branches the process.

When the server excludes the node n from the group Gi, j of the order 1, if the exclusion node n is not the group head and i 0 for the group Gi, j of the order 1 that excludes n, the order 1 The groups Gi and j of are divided into several minimum groups, and the node n to be excluded belongs to one of the minimum groups. Therefore, as a basic idea, Gi, j G0,1 The new keys k'i, j are delivered to the node to which they belong (group heads belonging to Gi, j), and the keys k'i, j are transferred from each group head to the group members.

That is, when the server excludes the node n from the group Gi, j of rank 1, if the exclusion node n is not the group head and i 0 for the element groups Gi, j excluding n, the main node of the server. As the exclusion means, first, when ki and j are the element keys of Gi and j and k'i and j are the element keys of the new Gi and j, k = h (k0,1 || ki, j) is calculated. , X = Ek (k'i, j) is obtained, and the 4-character set (i, j, IDn, x) is multicast-transmitted to the node (group head) belonging to Gi, j G0,1 (IDn is excluded). The ID of the node n to be generated), and then the subnode exclusion means of the node (group head) belonging to Gi, j G0,1 decodes x to obtain the new key k'i, j of Gi, j. Finally, when the subnode exclusion means of the node (group head) belonging to Gi, j G0,1 does not include the exclusion node n in the minimum group C to which the own node belongs, k (C) (K'i, j is encrypted using (the group key of the smallest group C to which it belongs), and Ek (C) (k'i, j) is multicast-distributed to the group members of C, while the group head When the exclusion node n is included in the minimal group C to which it belongs, the subnode exclusion means of the group head unicastly encrypts k'i and j for all group members of C other than n using the member key. And send.

When the server excludes the node n from the group Gi, j of order 1, if the exclusion node n is not the group head and i = 0 and j 1 for the element groups Gi, j excluding n, then Gi, Since j = G0, j, the groups Gi and j cannot be divided into extremely small groups. Also, since the set G0,1 and Gi, j of the group head are relatively prime (do not have an intersection), the new element keys k'i, j must not be exposed to the group head.

That is, when the server excludes the node n from the group Gi, j of rank 1, the exclusion node n is not the group head, and i = 0 and j 1 for the element groups Gi, j excluding n. , The main node exclusion means of the server calculates x1 = Eh (k0, j) (k'0, j) and x2 = Eh (k0,1) (x1), and is a 4-character set (0, j, IDn, Multicast x2) to the group head set G0,1 and the subnode exclusion means of each grouphead decodes x2 to obtain x1 (because the grouphead does not know k0, j, decode x1). If the product set of G0, j and the minimal group C to which it belongs contains one node n'and n n', the subnode exclusion means of the group head is a member of n'. X1 is encrypted with a key in a unicast manner and transmitted.

Further, when the server excludes the node n from the group Gi, j of the order 1, when i = 0 and j = 1, that is, the exclusion node n is the group head, the main node exclusion means provided in the server sets n. Performs a process of exchanging roles between the group heads n of the groups Gi and j to be excluded and the node n'in the minimum group to which the group head belongs, and eliminates the node when the excluded node is not the group head after the role exchange process is completed. Enforce the process.

Further, when the server excludes the node n from the group Gi, j of rank 1, when i = 0 and j = 1, that is, the exclusion node n is the group head, the role exchange processing of the node is performed by the group head n, And the node n' G0, j (j 1) belong to the same minimal group, and the main node exclusion means of the server first updates the element key of G0,1 and the new element key k'0, 1 is delivered to the node set G'0,1 = G0,1 \ {n} obtained by removing n from G0,1, and then the element keys of G0, j are updated and new element keys k'0, j are used. Deliver to the node set G'0, j = G0, j \ {n'} excluding n'from G0, j, and finally send k'0,1, k'0, j to n', n, respectively. It consists of three processes.

Further, when the server excludes the node n from the group Gi, j of the order 1, when i = 0 and j = 1, that is, the exclusion node n is the group head, the main node exclusion means provided in the server is first G0. , 1 to update the element key and distribute the new element key k'0,1 to the node set G'0,1 = G0,1 \ {n} obtained by removing n from G0,1. The keys k'0 and 1 are unicastly distributed from the server to each node belonging to, 1.

Here, G0,1 may be structured by a method such as the conventional method 2, and k'0,1 may be distributed to each node belonging to G'0,1.

Further, when the server excludes the node n from the group Gi, j of rank 1, when i = 0 and j = 1, that is, the exclusion node n is the group head, the main node exclusion means provided in the server is G0, In order to update the element key of j and distribute the new element keys k'0, j to the node set G'0, j = G0, j \ {n'} excluding n'from G0, j, x1 = Ek0, j (k'0, j) and x2 = Ek'0,1 (x1) are calculated, x2 is multicast distributed to the nodes of G'0,1 and the nodes belonging to G'0,1 ( The sub-node exclusion means of the group head) decodes x2 to obtain x1, and if the node of G'0, j exists in the minimum group to which the node belonging to G'0,1 (group head) belongs, the group The sub-node exclusion means of the head unicastly encrypts x1 with the member key and transmits it to the node exclusion means of the nodes of G'0 and j.

For the node n'that leaves G0, j due to the role exchange, the element key of G0,1 is updated, and the new element key k'0,1 is a node set G'0,1 obtained by removing n from G0,1. Since there is no corresponding group head (holding a valid key k'0,1) at the time of distribution to = G0,1 \ {n}, it is not possible to receive distribution of a new key k'0, j. Can not. As a result, the element keys of G0, j are updated, and the new element keys k'0, j are distributed to the node set G'0, j = G0, j \ {n'} excluding n'from G0, j. The process has been realized correctly.

Further, when the server excludes the node n from the group Gi, j of the order 1, when i = 0 and j = 1, that is, the exclusion node n is the group head, the main node exclusion means provided in the server is k'. In order to transmit 0, 1, k'0, j to n', n, respectively, k'0, 1, k'0, j are unicastly encrypted with the node key and transmitted to n', n. ..

<p> Next, examples of the present invention will be described in detail with reference to the drawings. It is assumed that the nodes form a network of a cluster tree topology as shown in FIG. Here, the cluster tree topology refers to a tree in which a server is a root node and at most one internal node exists in its children for all internal nodes other than the root node. In the cluster tree, one cluster is composed of one internal node and a set of nodes consisting of leaf nodes among the children of the internal node. On the cluster tree topology, as attributes of each node, information on which trunk belongs to the cluster tree, depth from the root node, and order information on which node in the cluster can be defined. Considering the order information in the cluster as the special attribute A0 = {G0,1, G0,2, G0,3, G0,4}, the trunk attribute A1 = {G1,1, G1,2, G1,3} , Depth attribute A2 = {G2,1, G2,2} can be defined as a two-dimensional group structure that can be specified. The cluster becomes a minimum group in the two-dimensional group structure.</p><p> At this time, the flowchart when the node n is excluded from the groups Gi and j is as shown in FIG. When i 0 in S31 of FIG. 3, from the set of nodes having any of the attribute values of G1, 1, G1, 2, G1, 3, G2, 1, G2, 2 among the attributes of A1 and A2. A process for excluding the node n is performed. At this time, since the node to be excluded is not the group head, the new key k'i, j is delivered to the node belonging to Gi, jG0,1 (the group head of Gi, j), and each group head is sent to the group member. On the other hand, k'i and j are transferred (S32). The specific processing flow is shown in FIG. First, the server calculates E h (k0,1 || ki, j) (k'i, j) and multicasts the calculation result (S311). After that, only the group heads in Gi and j can decode the calculation result, and obtain k'i and j by decoding (S312). Finally, k'i, j is encrypted and unicast only to the node whose group head is G'i, j = Gi, j \ {n} with the member key shared with the group members (S313). ), Finish the process.</p><p> Next, when i = 0 in S31 of FIG. 3, and j 1 in S33, the node from the set of nodes having the attribute values of G0, 2 or G0, 3 or G0, 4 among the attributes of A0. A process for eliminating n is performed. At this time, Gi, j = G0, j, and since the group head sets G0, 1 and Gi, j do not have disjoint elements (intersection), each group does not expose k'i, j to the group head. Transfer k'i and j from the head to the group members (S34). The specific processing flow is shown in FIG. First, the server calculates x1 = Eh (k0, j) (k'0, j) (j 1) and multicasts x2 = Eh (k0,1) (x1) (S341). Then, only the group heads in G0 and j can decode x2, and obtain x1 by decoding (S342). The group head cannot decode x1. After that, x1 is encrypted with the member key and unicast only to the nodes belonging to the node set G'0, j = G0, j \ {n} in which the group head excludes n from G0, j (S343). Finally, the node of G'0, j decodes x1 using k0, j (S344), and finishes the process.</p><p> Finally, when i = 0 in S31 of FIG. 3 and j = 1 in S33, the process of excluding the node n from the set of nodes having the attribute values of G0 and 1 among the attributes of A0 is executed. .. At this time, n is a group head, and the process of exchanging the roles of the group head n and the group members n' G0, j (j 1) in the minimum group to which the group head belongs is executed, and then the above-mentioned process is executed. Perform key update (when the exclusion node is not the group head) (S35). A specific processing flow is shown in FIG. First, the server encrypts k'0,1 with the node key unique to the server and each node, and everything included in the node set G'0,1 = G0,1 \ {n} excluding n from G0,1. Unicast to the node of (S351). And the server is x1 = Eh (k0, j) (k'0, j) is calculated (j 1), and x2 = Eh (k'0,1) (x1) is multicast (S352). Then, the group head belonging to G'0,1 decodes x2 to obtain x1 (S353), encrypts x1 to the node of G'0, j = G0, j \ {n'} and unicasts it. (S354). After that, the node of G'0, j decodes x1 using k0, j (S355). Finally, the server encrypts k'0, 1, k'0, j for n', n with the node key and unicasts (S356), and ends the role exchange process. At this point, the group head n changes its role with the group member n'and becomes a group member (it no longer owns the key of the set G0,1 of the group head). After that, when the exclusion node shown in FIG. 5 is not a cluster head, a node exclusion process is performed to eliminate n (S357), and the process ends.</p><p> FIG. 7 shows, as an example of the key update process 1 shown in FIG. 4, a certain node (group G2, 2 and group 0, i (i 0)) among all the nodes of the groups G2 and 2 other than the group head node (example). As a diagram, an example is shown in which i = 4) and the nodes of groups 1 and j (for example, j = 3) are excluded from the groups G2 and 2.</p><p> Referring to FIG. 7, first, the new keys k'2 and 2 are encrypted by the hash value of the key obtained by connecting the keys k0 and 1 and the keys 2 and 2, and this is multicast (FIG. 4). Step 311). Information that the key of node n (nodes belonging to groups 0 and 4 and groups G1 and 3 and groups 2 and 2) is not updated is added to the key to be multicast.</p><p> Then, the group head nodes of the groups 2 and 2 having the keys k0 and 1 and the keys 2 and 2 receive this and obtain the keys k'2 and 2 (step 312 in FIG. 4). Next, the group head node transfers the key k'2, 2 to the node under its own control, but does not transfer the key k'2, 2 to the node specified by the additional information described above, as an exception. (Step S313 in FIG. 4).</p><p> The process for excluding a certain node from groups 2 and 1 and the process for excluding a certain node from groups 1 and j (j = 1 to 3) are the processes in the case of FIG. 7 (nodes from groups 2 and 2). Since it is the same as (the process for excluding the above) (key update process 1), the description thereof will be omitted.</p><p> FIG. 8 shows, as an example of the key update process 2 shown in FIG. 5, a node in the group G0,3 (for example, a node belonging to the group G0,3 and the group G1,1 and the group G2, 1) is grouped G0, It is a figure which shows the example which excludes from 3.</p><p> Referring to FIG. 8, first, the new key k'0,3 is encrypted with the hash value of the key k0,3 to obtain x1 (the first half of step S341 in FIG. 5). Next, x1 is encrypted with the hash value of the keys k0 and 1 to obtain x2. Then, x2 is multicast (the latter half of step S341 in FIG. 5). Information that the key of the node n (nodes belonging to the groups G0, 3 and the group G1, 1 and the group G2, 1) is not updated is added to the multicast x2.</p><p> Then, the group head node holding the keys k0 and 1 receives this and obtains x1 (step S342 in FIG. 5).</p><p> Next, the group head multicasts x1 to the nodes under its control. However, the node specified by the additional information is not multicast (step S343).</p><p> Then, the node of the group G0,3 having the key k0,3 receives x1 and acquires k'0,3 (step S344 in FIG. 5). However, although the node specified by the additional information belongs to the groups G0 and 3, it cannot acquire k'0 and 3 because it is excluded from the target of multicast.</p><p> The process for excluding a node from groups G0 and 2 and the process for deleting a node from groups G0 and 4 are the same as the process operation in FIG. 8 (key update process 2). The explanation is omitted.</p><p> FIG. 9 shows the group head nodes n of the groups G1 and 3 and the groups G2 and 2 as an example of the key update process 3 shown in FIG. 6 (an example of excluding the group head nodes (nodes belonging to the groups G0 and 1)). It is a figure which shows the example which excludes (the node which belongs to group G1,3 and group G2,2 and group 0,1).</p><p> Referring to FIG. 9, first, the group head node n of the groups G1 and 3 and the group G2 and 2 is exchanged with another node n'of the group (for example, a node belonging to the groups G0 and 3). This exchange process includes steps S351, S352, S353, S355, S356.</p><p> First, the new keys k'0 and 1 are encrypted and unicast to each of the group head nodes of the five groups other than the groups G1 and 3 and the groups G2 and 2 (step S351 in FIG. 6).</p><p> Next, x1 is generated by encrypting the new key k'0,3 with the hash value of the key k0,3 (the first half of S352 in FIG. 6), and further, x1 is hashed with k'0,1. By encrypting with a value, x2 is generated and x2 is multicast (the latter half of S352 in FIG. 6).</p><p> Then, since the group head nodes of the five groups other than the groups G1 and 3 and the groups G2 and 2 have the keys k'0 and 1, x1 can be decoded (step S353 in FIG. 6). ). On the other hand, since the group heads of the groups G1 and 3 and the groups G2 and 2 do not have the keys k'0 and 1, x1 cannot be decoded.</p><p> The group head nodes of five groups other than the groups of groups G1 and 3 and groups G2 and 2 that were able to decode x1 transmit x1 to the subordinate nodes (step S354 in FIG. 6), but the key is 0. Only the node having, 3 (the node belonging to G0, 3) can decode x1 to obtain k'0, 3 (step S355 in FIG. 6). On the other hand, in groups G1 and 3 and groups G2 and 2, since the group head node cannot decode x1, the nodes in this group cannot obtain k'0 and 3.</p><p> Next, the keys k'0 and 1 are unicast to the node n'which became the group head node d, and the keys k'0 and 3 are unicast to the node n which is no longer the group head node d (step in FIG. 6). S356).</p><p> After that, the method shown in FIG. 8 is carried out in order to eliminate the node n (step S357 in FIG. 6).</p>

Therefore, according to the present invention, the amount of communication at the time of key update at the time of node exclusion can be significantly reduced as compared with the conventional method. For example, in the group key update process, communication from the server requires only one multicast distribution to the group head, and unicast communication from the group head at most (the number of nodes in the smallest group to which the group head belongs-1). You can update the key with. Since the minimum group is the minimum in the inclusion relationship of the node set, it is possible to perform processing very efficiently.

Further, according to the present invention, by using the role exchange process, it is possible to update the key by eliminating the node corresponding to the group head.

Further, according to the present invention, it is possible to update the key with a smaller amount of calculation as compared with the conventional method. Therefore, even in an environment where computational resources are limited, such as a sensor network, the amount of calculation associated with key update can be reduced, and key update can be performed safely.

As described above, the present invention is a network in which a server and a node connected to the server are configured as a constituent communication device in a network communication in which communication is performed using a plurality of communication devices using an encryption key, particularly. The explanation has been given using a sensor network as an example, but it goes without saying that the description is not limited to such a network and can be applied to various network communications.

101 server 103 Node addition means 105 Main node exclusion means 107 Key storage means 109 Secondary node exclusion means 111 Key storage means