Method of managing user key for broadcast encryption

The present invention relates to a broadcast encryption method, and more particularly to an efficient user key management method for broadcast encryption.

Broadcast Encryption (hereinafter referred to as BE) is a method of efficiently transmitting information only to the users desired by the destination (that is, the broadcasting center) among all users, and a set of users who receive the information It should be used efficiently when it changes voluntarily and dynamically. The most important property of BE is the exclusion or exclusion of unwanted users (eg, illegal or expired users).

Figure 1 shows the network structure of a general broadcast encrypted data transmission system. As shown in the figure, the content producer 100 produces various valid data including audio or video data, and provides the produced data to the service provider 110. The service provider 110 pays the cost for the data from the content producer via various wireless communication networks (for example, mobile DRM (Digital Right Management) network 140, smart home DRM network 150). )).

That is, the service provider 110 can transmit data via the satellite 120 to a user device such as a set-top box 141 equipped with various satellite receivers, and also to the mobile communication terminal 142 via the mobile communication network. Can be transmitted. Further, it can be transmitted to the terminals 150, 151,152,153,154,155 of the smart home network 150 via the Internet network 130.

On the other hand, at this time, the illegal user 160 who has not paid a legitimate cost for the corresponding data encrypts the data by broadcast encryption in order to prevent the use of the data.

It can be said that the stability of such an encryption and decryption system depends on the system that manages the encryption key. And the most important thing in the encryption key system is how to generate the encryption key and how to manage and update the generated encryption key.

After many changes since the concept of BE was proposed in 1991, BE now assumes a stateless receiver. This concept means that the password of each user cannot be changed or updated by changing the session. In terms of stability, the term "k-resilient" is used, which means that even if k of the excluded users make a collusion attack, the information cannot be completely recovered. .. Since r roughly indicates the number of excluded users, "r-resilient" means that it is safe for all excluded users to come together and make a collusion attack.

On the other hand, BE attaches great importance to the amount of transmission, the amount of storage, and the amount of calculation, but the amount of headers to be transmitted from each transmission side, the amount of password keys that the user must store, and the user obtains the session key. It means the amount of calculation required to do so. Of these, reducing the amount of transmission can be said to be the biggest issue. The amount of transmission was initially proportional to the N value, which is the number of all users, but now it is mainly proportional to r, which is the number of excluded users, and is decreasing. Since the advent of technology in which the transmission amount is proportional to r, reducing the transmission amount to less than r has become a major issue in BE.

Based on this BE problem, the "Subset Difference (SD) Method" published by "Naor-Naor-Lotspiech" has given excellent results among the results published so far. In the SD method, if all users are n, O (log)^3/2It requires a conserved quantity of n) and a transmission quantity of O (2r-1).

However, even based on such an SD method, there is a problem that an efficient limit remains for use by a large number of users.

As mentioned above, various algorithms have been presented since Berkovits first published a paper on BE in 1991. When the algorithms are organized, secret sharing methods, Subset Cover-Free Model methods, and tree-based methods have been proposed.

First, a model based on password key sharing will be outlined. The secret key sharing model was first proposed by "S. Berkovits" in 1991, and "M. Noar" and "B. Pinkas" in 2000 were improved more efficiently in the paper "Efficient Trace and Revoke Schemes". S. Berkovits' "How to Broadcast a Secret" presented a method using polynomial interpolation and a method using vector based secret sharing.

According to the polynomial interpolation method, a point (x) from the center (broadcasting center or destination) to each user's password channel_i, Y_i) Is transmitted. In addition, x_iAre all different values, (x_i, Y_i) Is the password key for each user. Then, in order to broadcast the secret information S to the legitimate user t name of each session, a random integer j and a polynomial P of degree t + j + 1 are selected. Polynomial P is a valid user password key for t names (x)_i, Y_i) And any j points (x, y) and (O, S) that are not the password keys of another user. Then, at the center, t + j points different from the above points on the polynomial P are transmitted. Then, since the legitimate user of the t name knows one point (own password key) other than t + j, the polynomial P having the degree t + j + 1 can be recovered, and the password information S is also Can be sought. However, the excluded user cannot recover the absolute polynomial P because he only knows t + j points.

In such a method, the transmission amount is O (t + j + 1), the conserved amount is O (1), and the calculation amount is about t.³It is the multiplication of numbers. In addition, it has the advantages of being easy to dispose of, preventing collusion, and being able to track collusion. However, it is inefficient for a large number of users and is not safe for repeated use, so there is a problem that it cannot be actually used.

For "Efficient Trace and Revoke Schemes" by M. Noar and B. Pinkas, the threshold password sharing method using Lagrange's interpolation formula is used. In the Noar-Pinkas method, it is possible to recover an r-degree polynomial if it knows the points on r + 1 polynomials, but it uses the property that it cannot be recovered with r points that are missing one. That is, the center selects an arbitrary t-degree polynomial P and provides each user with different points on it as a password key. When the r-name user is excluded, the center sums the excluded r-name password key and the arbitrarily selected tr points to broadcast information for a total of t points. As a result, the excluded user still knows only t points even if his secret information is added, while the excluded user knows t + 1 points, so the polynomial P can be recovered. Become. The session key P (0) value can be obtained using this polynomial.

Since such a method is easy to dispose of and can prevent collusion, collusion tracking is also possible. In particular, it has a great advantage that a new user can be added (add), and has the efficiency that the transmission amount is O (t) and the conserved amount is O (1). However, according to such a method, there is a problem that it is not possible to exclude more users than the initially defined t. Furthermore, the number of points to be transmitted and the amount of calculation required to calculate the polynomial depend on t, which is inefficient. Further, as t becomes larger, the calculation time increases, which is inconvenient when a large number of users are included.

Second, the subset cover-free system model defines the concept of a subset cover-free system with a set of subsets of S as elements, assuming that the set of all users is S. If such a system can be found, BE can be performed using that system. However, there is a disadvantage that the storage amount and the transmission amount are about O (r log n), which is not efficient. He also introduced how to extend the 1-resilient model to a k-resilient model. Such an extension seems meaningful because it is easy to devise an efficient 1-resilient method, but the methods presented so far have the problem that their efficiency drops in the process of expansion.

Thirdly, the method using a tree structure has recently attracted attention. In 1998, CK Wong, M. Gouda, and GSLam proposed the LTH (Logical-tree-hierarchy) method, but it is difficult to exclude many users from one session. Furthermore, since the user's password key changes together with the change of session, there is a sense of distance from the modern BE that assumes an uncontrolled receiver (stateless receiver). Then, in 2001, D.Naor, M.Naou, and J.Lotspiech proposed "Complete Subset (CS) Cover Scheme" and "Subset Difference (SD) Scheme". Both methods assume that the number of users is n and the number of excluded users is r, the center creates a binary tree with a height log n, and all nodes have it. Assign the corresponding password key. Then, one user is assigned to each leaf node.

First, to explain the CS Cover method, each user receives and stores the password keys of all the nodes located on the route from the root node to his leaf node from the center. Here, a complete subtree that does not include any excluded users from the subtree is called "complete Subtree (CS)", but if such CS are properly collected, only users that are not excluded can be included. it can. If the session key is encrypted and transmitted with the password key corresponding to the root node of the used CS, the legitimate user can recover the session key, but the excluded user can be used for any CS used above. Since it is not included, the session key cannot be recovered.

FIG. 2 is a drawing showing the concept of broadcast encryption in which keys are assigned in a conventional tree structure. As shown in the figure, each user 220 whose data is provided via the broadcast encryption method has its own unique key value (32 to 47), and at the same time, each node connected to itself on the tree structure. Will have the key value of.

For example, the 34th user has the key value of the 17th node 209, the key value of the 8th node 204, the key value of the 4th node 202, and the key value of the 2nd node 201 together with the 34th key value of the user. At this time, the key value of the 17th node 209 owned by the 34th user is also shared with the 35th user. Similarly, the key value of the 8th node 204 owned by the 34th user is also shared by the 32nd, 33rd, and 35th users.

On the other hand, when the 32nd to 47th users are all legitimate users, it is preferable to include the 2nd node 201 key value in the header part of the data to be transmitted and transmit the same to all users to ensure security. Data transmission is performed.

However, if the user holding the key of the 36th user 221 is an illegal user (revoked user) who is not a legitimate user, it is shared by another user having the key value of the node associated with the 36th user 221. Therefore, a process to update the corresponding key value is required. That is, the key values of the 18th node 210, the 9th node 205, the 4th node 202, and the 2nd node 201 must be updated. In addition, in order to update the key value, it is performed in the order of the lower node to the upper node.

First, since the key value of the 18th node 210 is shared by the 37th user, the updated key value of the 18th node 210 is encrypted by the 37th user's key value and transmitted to the 37th user from the server. Then, since the key value of the 9th node 205 is shared by the 37th user and the 38th user and the 39th user under the 19th node 211, the updated key value of the 9th node 205 is the 37th user. It is encrypted and transmitted to the user with the key value of the 18 node 210 updated in advance, and is encrypted and transmitted to the 38th and 39th users with the key value of the 19th node 211.

In the same way, the key value of node 202 is shared by users 32,33,34,35 under node 204 and users 37,38,39 under node 205. Therefore, the updated key value of the 4th node 202 is encrypted and transmitted to the 32nd to 35th users with the key value of the 8th node 204, and is pre-updated to the 37th, 38th, and 39th users. It is encrypted with the key value of node 205 and transmitted.

Finally, the key value of node 201 is shared by users 32 to 39 under node 202 except 36 user 221 and is shared by users 40 to 47 under node 203. Since the users share it together, the updated key value of node 201 is encrypted with the key value of node 202 that has been updated in advance for users 32, 33, 34, 35, 37, 38, 39. It is encrypted and transmitted to the 40th to 47th users by encrypting it with the key value of the 5th node 203. Through such a key update process, it is possible to block the access of illegal (or obsolete) users.

The transmission amount in the above method (that is, the CS model) is O (r log (n / r)), which is the number of CSs including only the users who are not excluded, and the storage overhead is O (log n).

On the other hand, the SD (Subset difference) model is a modification of the CS model described above, and is O (log).²The conserved quantity of n) and the transmission quantity of O (2r-1) were required to dramatically improve the transmission capacity. In the SD model, we devise a subtree that is obtained by subtracting a subtree rooted from another node w included in the corresponding serve tree from a subtree rooted at one node v. The leaf nodes below this subtree are legitimate users, and the leaf nodes below the subtree rooted in w are excluded users. Such a method can be covered by one subset, unlike the CS model, which always requires two or more subsets, when there are excluded users with a reasonable number of legitimate users. .. In the SD method, the hash value starting from the hash value of the key assigned to the node v and ending with the node w is obtained, and the value corresponding to that value is used as the session key. Each user has a hash value for a sibling node for each node on the path from the roots node to his leaf node as a password key. Therefore, due to the one-way hash function, only a legitimate user can recover the session key. The transmission amount of the SD model is O (2r-1), and the conserved amount is O (log).²It is n), and the amount of calculation reaches only the hash of the maximum O (log n).

Then, in 2002, an improved LSD model of the SD model was proposed. In the LSD model, the storage amount is O (log) using a layer for each subtree.^3/2Instead of reducing it to n), the transmission amount was double that of the SD model.

Among the BE models mentioned above, the one that showed excellent efficiency was the model that used a tree structure such as LSD and SD. However, the method using the tree structure cannot be expected to be further improved because the number of subsets required for broadcasting largely depends on the position of the user. Further, in the case of the tree structure, there is a disadvantage that maintenance also requires a considerable cost, so there is a fact that a more efficient BE technology other than the above-mentioned tree structure is required.

<p num="0031"><patcit num="1"><text>Japanese Unexamined Patent Publication No. 15-273858</text></patcit><patcit num="2"><text>Japanese Unexamined Patent Publication No. 07-005808</text></patcit><patcit num="3"><text>Japanese Unexamined Patent Publication No. 14-124952</text></patcit></p>

<p num="0032"> The present invention has been devised to solve the above-mentioned problems, and an object of the present invention is a broadcast cipher that sequentially forms a one-way key chain for each node and distributes key values using a linear structure. The purpose is to provide a user key management method for conversion.</p><p num="0033"> Furthermore, an object of the present invention is a user key for broadcast encryption that uses a linear structure to select each c-th node from nodes on a straight line, set it as a special node, and generate a special node chain starting with a special node key. It is to provide a management method.</p><p num="0034"> Furthermore, an object of the present invention is to provide a user key management method for broadcast encryption capable of setting a transmission section by adding a section including one excluded user and reducing the transmission amount. is there.</p>

<p num="0035"> The key management method according to the present invention for achieving the above-mentioned object is a step of giving a node path ID (Node Path ID) to each node arranged in sequence, and an arbitrary seed key (arbitrary seed key) according to the node path ID to each node. A step of giving a seed value key), a step of repeatedly applying a hash function to any given seed key to generate a key value, and a step of generating a key value. A step of sequentially giving the generated key value to each of the nodes is included.</p><p num="0036"> Preferably, the encryption key for the section consisting of N nodes among the sequentially arranged nodes is obtained by repeatedly applying the hash function N-1 times to the seed key given to the first node in the section. It is characterized by making it a generated key value.</p><p num="0037"> Further, the section is characterized by being a continuous section composed of authenticated nodes. Further, the interval includes one or more excluded nodes, and the hash function is applied independently to each of the excluded nodes.</p><p num="0038"> On the other hand, the key management method according to the present invention includes a step of giving an arbitrary seed key to each node arranged in sequence and a step of repeatedly applying a first hash function to the given arbitrary seed key to generate a key value. , The step of sequentially giving the generated key value to each of the nodes, the step of setting a special node according to a certain interval among the sequentially arranged nodes, and an arbitrary special seed key for each of the special nodes. It includes a step of giving, a step of repeatedly applying a second hash function to the given special seed key to generate a key value, and a step of sequentially giving the generated key value to each of the special nodes.</p><p num="0039"> Preferably, when the first special node of the special nodes is given a special node key of K, the second special node separated from the first special node by the fixed interval is given the second hash function to K. It is characterized in that the applied key value is given.</p><p num="0040"> Further, the encryption key for the section consisting of N nodes among the sequentially arranged nodes is generated by repeatedly applying the hash function N-1 times to the seed key given to the first node in the section. It is characterized by making it a key value.</p><p num="0041"> Further, the section is characterized by being a continuous section composed of authenticated nodes.</p><p num="0042"> Further, the interval includes one or more excluded nodes, and each of the excluded nodes independently applies a new hash function.</p><p num="0043"> On the other hand, the key management method according to the present invention includes a step of giving a node path ID to each node forming a circular group, a step of giving an arbitrary seed key to each node according to the node path ID, and the given arbitrary. It includes a step of repeatedly applying a hash function to the seed key of the above to generate a key value, and a step of sequentially giving the generated key value to each node forming the circular group.</p><p num="0044"> Preferably, the encryption key for the circular section consisting of N nodes in the circular group is generated by repeatedly applying the hash function N-1 times to the seed key given to the first node in the section. It is characterized by making it a key value.</p><p num="0045"> Further, the circulation section is characterized in that it is a continuous section composed of authenticated nodes.</p><p num="0046"> Further, it is characterized in that a hierarchical structure of an annular group is formed by linking a node forming a new annular group below each node forming the annular group as a substructure.</p><p num="0047"> The hierarchical structure is characterized by having 16 layers, and the number of nodes forming each of the annular groups is the same.</p><p num="0048"> Further, a circular section consisting of N nodes in the circular group includes one or more excluded nodes, and each of the excluded nodes applies an independent hash function.</p><p num="0049"> Further, the number of nodes forming the circular group is N, and 0 to N-1 are given as the node path IDs.</p><p num="0050"> Further, a node having at least one excluded child node in the hierarchical structure is considered as an excluded node.</p><p num="0051"> On the other hand, in the key management method according to the present invention, a step of giving an arbitrary seed key to each node forming a circular group and a first hash function are repeatedly applied to the given arbitrary seed key to generate a key value. A step of sequentially giving the generated key value to each node forming the circular group, a step of setting a special node according to a certain interval among the nodes forming the circular group, and the above. Each special node is given an arbitrary special seed key, a second hash function is repeatedly applied to the given special seed key to generate a key value, and the generated key value is applied to each special. Includes steps to give to nodes sequentially.</p><p num="0052"> Preferably, when the first special node of the special nodes is given a special node key of K, the second special node separated from the first special node by the fixed interval is given the second hash function to K. It is characterized in that the applied key value is given.</p><p num="0053"> Further, the encryption key for the circular section consisting of N nodes in the circular group is generated by repeatedly applying the hash function N-1 times to the seed key given to the first node in the circular section. It is characterized by making it a key value.</p><p num="0054"> Further, the circulation section is characterized in that it is a continuous section composed of authenticated nodes.</p><p num="0055"> Further, the circulation section includes one or more excluded nodes, and each of the excluded nodes independently applies a new hash function.</p>

<p num="0056"> According to the present invention, the most important transmission amount in broadcast encryption can be reduced to less than r. Further, the embodiment of the present invention has an advantage that the transmission amount can be significantly reduced as compared with SD which has been known as a preferred method.</p><p num="0057"> Further, according to the present invention, even if a large number of users collude, a new key cannot be created, and when an illegal decoder is created, the colluded user key is used as it is, so that there is an advantage that it can be tracked. Finally, you can freely add as many users as you want at the end of the sequence.</p>

<figref num="1">It is a drawing which shows the network structure of the data transmission system by general broadcast encryption.</figref><figref num="2">It is a drawing which shows the concept of broadcast encryption which is a conventional tree structure and assigns a key.</figref><figref num="3">It is a flowchart which shows the procedure which maps a unidirectional key chain to each node of the linear structure which concerns on embodiment of this invention, and gives a key value.</figref><figref num="4">It is a drawing which shows the method of giving an arbitrary seed key to each node of the linear structure which concerns on embodiment of this invention.</figref><figref num="5">It is a drawing which shows the method of mapping a unidirectional key chain to each node of the linear structure which concerns on embodiment of this invention.</figref><figref num="6">It is a drawing which shows the method of making a key value correspond to each node of the linear structure which concerns on embodiment of this invention.</figref><figref num="7">It is a drawing which shows the result which the key value corresponds to each node of the linear structure which concerns on embodiment of this invention.</figref><figref num="8">It is a flowchart which shows the session key transmission procedure to the section with the illegal user which concerns on embodiment of this invention.</figref><figref num="9">It is a drawing which shows the definition of the section in the linear structure which concerns on embodiment of this invention.</figref><figref num="10">It is a section of the linear structure which concerns on embodiment of this invention, and is the drawing which shows the method of transmitting a session key.</figref><figref num="11">It is a flowchart which shows the procedure which the user of each node which concerns on embodiment of this invention decodes data by the received session key.</figref><figref num="12">It is a drawing which shows the definition of the special node in the linear structure which concerns on the modified 1st Embodiment of this invention.</figref><figref num="13">It is a drawing which shows the method of making a key value correspond to each node in the linear structure which concerns on the modified 1st Embodiment of this invention.</figref><figref num="14">It is a figure which shows the method of dividing the section for the session key transmission which concerns on the modified 1st Embodiment of this invention.</figref><figref num="15">It is a drawing which shows the method of transmitting a session key when it is divided into a large number of sections which concerns on the modified 1st Embodiment of this invention.</figref><figref num="16">It is a drawing which shows the section setting method which concerns on the modified 2nd Embodiment of this invention.</figref><figref num="17">It is a drawing which shows the method of making a key value correspond to each node in the linear structure which concerns on the modified 2nd Embodiment of this invention.</figref><figref num="18">It is a drawing which shows the result which the key value corresponded to each node of the ring structure which concerns on the modified 4th Embodiment of this invention.</figref><figref num="19">It is a drawing which shows the hierarchical structure of each node group of the ring structure which concerns on one Embodiment of this invention.</figref>

Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings. &lt;Basic embodiment&gt;

FIG. 3 is a flowchart showing a procedure for mapping a one-way key chain to each node of the linear structure according to the embodiment of the present invention and giving a key value. As shown in the figure, first, a node path ID is given to each node (S301). Here, the node path ID is an ID for classifying the user corresponding to each node.

Then, for each node on the linear structure, an arbitrary seed value key is given according to the node path ID (S302). In carrying out the present invention, any seed key can be determined independently and randomly.

Then, a key value that is the result of substituting an arbitrary seed key given for each node into the one-way hash function is generated. Further, by repeatedly substituting the generated key value into the one-way hash function, the key value is continuously generated, and each predetermined key chain is generated according to each arbitrary seed key (S303).

Here, the one-way hash function is a function that compresses an input value of an arbitrary length as an output value of a predetermined length, and has the following properties. On a one-way hash function, it is not possible to calculate an input value for a given output value, and it is not possible to calculate a further input value that gives a given input value. In addition, it is not possible to calculate any two different input values that give the same output value on the one-way hash function.

A hash function that satisfies the above-mentioned properties is one of the important functions applied in data integrity, authentication, non-repudiation, etc., and the one-way hash function for implementing the present invention is "HBES SHA". It can be -1 ".

The key value generated for each seed key in S303 is given sequentially from the node following the node to which each seed key is given (S304,305). In practicing the present invention, the method by which the key value is given should be constant at each node.

Hereinafter, the procedure in which the above-mentioned key value is given to each node will be described in detail based on FIGS. 4 to 6.

FIG. 4 shows a method of giving an arbitrary seed key to each node of the linear structure according to the embodiment of the present invention. As shown in the figure, any seed key for each node can be sequentially mapped to each linear node from the front.

For example, suppose N nodes are arranged in the same space, and each node has a randomly selected seed key value of K.₁, K₂, ... K_NValues are corresponded one by one. That is, K is attached to the first node 401.₁Value, K for second node 402₂Value, K for third node 403₃Value, K for 4th node 404₄Value ..., K for node 405_N-1Value, K for Nth node 406_NA randomly selected seed value of the value is matched.

At this time, a one-way key chain is generated from each of the above-mentioned seed keys using a one-way hash function. The method of generating the one-way key chain is as follows.

If h is {0,1}¹²⁸→{0,1}¹²⁸For a one-way hash function that is, the one-way keychain of length c from K is {K, h (K), h (h (K)) = h⁽²⁾(K), ... h^(c-1)It becomes (K)}. The generated one-way key chain value corresponds to each linear node sequentially from the front.

FIG. 5 is a drawing showing a method of mapping a one-way key chain to each node of the linear structure according to the embodiment of the present invention. As shown in the figure, h, which is a one-way hash function, is used to generate and map a one-way key chain having a length c starting at each node. Here, c means the size of the chain.

That is, the seed key value K for the in-node 501₁The value is mapped and h (K) is assigned to the i + 1 node 502._i) Value is mapped and h (h (K)) is assigned to the i + 2 node 503._i)) Values are mapped, ..., h to i + c-1 node 504^(c-1)(K_i) Values are mapped.

On the other hand, in the embodiment of the present invention, the c value is set in advance as a value for determining the length of the one-way key chain, and the number of keys that each user must store is determined according to the c value. is there. Therefore, a one-way keychain having a length c can be generated from all the seed keys given to each node, and the generated one-way keychain value is given to each node.

As a result, each node is given c key values. However, a smaller number of keys are assigned to some nodes at the beginning and end of the straight line. That is, the conserved quantity of each user is O (c).

FIG. 6 illustrates a method of associating a key value with each node of the linear structure according to the embodiment of the present invention. As shown in the figure, the in-node 601 has its own seed key, K._iGiven a value, the i + 1 node 602 is K_iIs a one-way hash function operation value h (K_i) And K, which is your key value given in advance._{i + 1}Is given. Further, the i + 2 node 603 is given a value obtained by performing a one-way function operation on the key value given to the i + 1 node 602 and its own key value given in advance.

That is, K_iH (h (K)), which is the value obtained by calculating the one-way hash function twice._i)) And K_{i + 1}Is the value obtained by calculating the one-way hash function of h (K)._{i + 1}) And K, which is my seed key value_{i + 2}Is given. Based on the same method, the cth node i + c-1 node 605 is h^(c-1)(K_i), H^(c-2)(K_{i + 1}), H^(c-3)(K_{i + 2}), ... K_{i + c-1}Is given.

Therefore, the user corresponding to each node will be given one to c keys as the user's password key according to the position of each user.

In addition, K_{i, i}= K_iAnd K in i j_i,_j= h^(ji)(K_{i, j}), User u_iThe key set saved by is as shown in the following formula.

<maths num="1"><img id="000002" he="11" wi="77" file="JP6139965B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

The key values assigned to each node based on the above number 1 are as shown in the table shown in FIG. FIG. 7 shows the results in which the key values correspond to each node of the linear structure according to the embodiment of the present invention.

Refer to the figure, user u_cIt can be seen that the key value 701 of is assigned c key values as shown in the figure. At the same time, in the present invention, a method is used in which the entire user is divided into one or more small subsets, and the session key is transmitted to each of the divided subsets using one image.

FIG. 8 is a flowchart showing the session key transmission procedure to the section between illegal users according to the embodiment of the present invention. With reference to the figure, first, a contiguous array of legitimate users located between two revoked users was defined as an interval and excluded to convey the session key. Set the interval between users (S801). Then, the session key is transmitted by making each of the set sections into a subset (S802).

At this time, one section is created between the two excluded users, except when the excluded users are continuously located. Therefore, the session key is transmitted using a maximum of r + 1 intervals. However, according to the embodiment of the present invention, when the maximum length per section is limited to c, a larger transmission amount is required for a section in which the section length is larger than c.

To explain how to set a continuous array interval of legitimate users with an example, first, U₁Or U₁₀There are up to U users out of them₅If is an excluded user and limits the maximum length of one interval to 5, then U₁Or U₄One section up to and U₆Or U₁₀One section up to is set.

In addition, U₁Or U₁₀There are up to U users out of them₁And U₁₀If is an excluded user and limits the maximum length of one interval to 5, then U₂Or U₆One section up to and U₇Or U₉One section up to is set.

FIG. 9 is a drawing showing the definition of a section in the linear structure according to the embodiment of the present invention. Referring to the figure, a group of continuously applied users (privileged users) located between two revoked users 901 and 903 is defined as an interval 902.

On the other hand, after setting the above-mentioned section, U_iNode key K_iCheck the one-way keychain starting from (S803), h^(S)(K_i) Is used as the key to encrypt and send the session key (SK) (S804). Eventually, the encrypted message is transmitted (S805).

More specifically, the interval {u_i, U_{i + 1}, U_{i + 2}, ... u_{i + S}} (However, if s is less than c), the center is u to convey the session key (SK)._iNode key K corresponding to_iUse a one-way keychain starting from. From the value of the one-way keychain, u_{i + S}The key value corresponding to h^(s)(K_i) Is used as a key to encrypt and transmit the session key. That is, when E (K, M) is a password key cryptographic algorithm with K as the key, E (h)^(s)(K_i), SK) messages are transmitted to all users.

On the other hand, as described above, the user who can decrypt the transmitted message by the key value given in advance is the key h.^(s)(K_i) Only the user who can ask. Therefore, the interval {u_i, U_{i + 1}, U_{i + 2}, ... u_{i + S}Only the users included in} can request the corresponding key.

That is, the users included in the section are K._iI know the value of one of the one-way keychains starting from, and that value is h^(s)(K_iSince it is located on the left side of), by applying the one-way function h to its own value, h^(s)(K_i) Seems.

On the other hand, among the users not included in the section, the user located on the left side of the section is K._iSince it is not possible to obtain the value related to, h^(s)(K_i) Is not required either. Further, a user located on the right side of the interval can obtain a partial value of the one-way keychain, but cannot obtain the left side value of the one-way keychain due to the one-way property of the one-way function.

As a result, even if any user who is not included in the relevant section colludes, h^(s)(K_i) Is not possible, and the session key cannot be recovered.

FIG. 10 is a section of a linear structure according to an embodiment of the present invention, and shows a method of transmitting a session key. With reference to the figure, the session key (SK) can be simultaneously transmitted to the users included in one section according to the embodiment of the present invention as described above.

That is, the excluded users are located at the i-node 1001 and the i + t + j node 1005, and t + 1 applied users 1002, 1003, 1004 are placed between the two excluded users. Assuming there is, one password key can be transmitted for the applied user. That is, if E (K, m) is a password key encryption method using K as a key, the user u_i, ... u_{i + t}The session key header for is expressed as in Equation 2 below.

<maths num="2"><img id="000003" he="11" wi="77" file="JP6139965B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

FIG. 11 is a flowchart showing a data decoding procedure by the session key received by the user of each node according to the embodiment of the present invention. As shown in the figure, only the user applied by the key value transmitted based on the method described above can decode the received data. That is, when each user who receives the message including the encrypted header (S1101) is a user in the corresponding section (S1102), the key value possessed by the user is used as h.^(s)(K_i) Is calculated and decoded (S1103). On the other hand, if the user is not within the relevant section, the above h^(s)(K_i) Cannot be calculated, so the received data cannot be decoded (S1104).

Specifically, user 1002 before the inode is K_iSince we don't know the value of, we can't find the key value, and users since i + t, even K_iI know the back part of the one-way keychain, but it's the one-way property of the one-way hash function.^(s)(K_i) Cannot be obtained.

On the other hand, all legitimate users included in the section have K among their own key values._iBy repeatedly applying h to the value created from, h^(s)(K_i) The value can be calculated.

In the above-described embodiment of the present invention, the transmission amount when r excluded users are included from all N users is calculated as follows.

First, each user should save up to c key values. At that time, the transmission amount is r + (N-2r) / c in the worst case, which is the case where all excluded users are gathered on one side of the straight line and the rest are gathered only by legitimate users. ..

Furthermore, since the transmission amount decreases when two or more excluded users appear consecutively, consider the case where the excluded user and the legitimate user are located in a police box. At this time, the reason why N / c is additionally required is that the maximum length of the section in which the key can be transmitted in one transmission is set as c.

In addition, the amount of calculation by the user is a maximum of one-way function calculation of number c and one password key encryption algorithm, and when this is calculated in the situation where N = 1,000,000 and r = 50,000, the following result values are obtained. Is acquired.

<tables num="1"><img id="000004" he="27" wi="154" file="JP6139965B2_D0001.tif" img-format="tif" img-content="drawing" /></tables>

Hereinafter, a modified example of the above-described embodiment of the present invention will be described. First, the modified first embodiment performs one transmission for a long section in order to supplement that the transmission amount becomes larger than r by setting the section length as c in the above-described embodiment. It is a method of transmitting the key value only by itself.

Further, the modified second embodiment is a method of applying a new one-way function from the excluded user position in order to reduce the transmission amount from r. At the same time, the modified third embodiment is a method in which the modified first embodiment and the modified second embodiment are combined.

&lt;Transformed First Embodiment&gt; The reason why the transmission amount is larger than r in the above-described embodiment is that the length of the section is limited to c. Therefore, in order for the transmission amount to approach r, the required transmission amount must be reduced according to the above-mentioned section limitation. Therefore, by extending the above-mentioned basic concept, we propose an extended embodiment in which the key can be transmitted in one transmission for a long section.

In the modified first embodiment of the present invention, special nodes are set according to a certain interval (for example, every c-th node) among the nodes on the straight line.

For each special node, a special seed key independent of the existing seed key is randomly selected again and associated with each other to generate a special node chain starting from the special node key.

FIG. 12 defines a special node in the linear structure according to the modified first embodiment of the present invention. With reference to the figure, special nodes 1201, 1202, 1203 are set for each c-th node 1204 and 1205. A special seed key is given to each of the special nodes 1201, 1202, 1203 set for each set c-th node, and c × c in length from the key.₂A one-way chain is constructed.

More specifically, for each special node 1201, 1202, 1203, a special seed key independent of the existing seed key is randomly selected and associated again, and a new one-way hash function is used for each special seed key. Form a special node chain starting from the special seed key.

At this time, c₂Is a new constant, the special node chain is c × c as described above.₂Has a length of.

Hereinafter, a method of associating a special node chain with a special node will be described based on FIG.

FIG. 13 illustrates a method of associating key values with each node in the linear structure according to the modified first embodiment of the present invention. The method of forming the chain in the modified first embodiment is basically based on the same method as the above-mentioned basic embodiment. But the next section {u_i, U_{i + 1}, U_{i + 2}, ... u_{i + S}If} is an interval whose length starts from a special node exceeds c, the key transmission for the interval is u._iIt is done by a special node chain starting from. At this time, the method of encrypting the SK is the same as that of the above-mentioned basic embodiment. That is, u_iChain u starting from_{i + s}SK is encrypted and transmitted using the value corresponding to.

Based on FIG. 13, when the special node key K is assigned to the first special node 1301 which is the c node, the K is newly added to the second special node 1302 which is the second c node whose length c is exceeded. Directional function h₂One-way function operation in 1304 h₂(K) special node key 1305 is assigned. Similarly, the third special node 1303, which is the third c node, has the above K as a new one-way function h.₂One-way function operation twice in 1304 (ie h₂⁽²⁾1306) h₂⁽²⁾(K) is given.

Therefore, in the c + 1 node, the special seed key K of the c node is given a one-way function operation by h (K), and in the c + 2 node, the special seed key K of the c node is given twice by h. Directional function calculated h⁽²⁾(K) is given. Similarly, in the 2c + 1 node, the h given to the 2c node₂H (h) which is a one-way function operation of (K) by h₂(K)) is given, and in the 3c + 1 node, h given to the 3c node₂⁽²⁾H (h) which is a one-way function operation of (K) by h₂⁽²⁾(K)) is given.

At this time, for 1 t &lt;c, the c + t th user has his / her seed key and h.₂Save (K) together. Therefore, c for each node₂The keys are added and saved.

As mentioned above, in the modified first embodiment of the present invention, the number of key values stored in each node is increased, but the size of the session key to be transmitted is reduced.

FIG. 14 illustrates a method of dividing sections for session key transmission according to a modified first embodiment of the present invention. As shown in the figure, when a large number of applied users (privileged users) are gathered, the session key can be transmitted by dividing into only two sections 1401 and 1402.

FIG. 15 illustrates a method of transmitting a session key when divided into a large number of sections according to a modified first embodiment of the present invention. As shown in the figure, when it is divided into four sections 1501, 1502, 1503, 1504, E (h)⁽²⁾h₂⁽²⁾By constructing a session key and transmitting it as in (K), SK), it is realized so that only the applied user can be decoded.

Therefore, h according to the modified first embodiment of the present invention.₂The amount of calculation can be reduced by using a function. In other words, at this time, the maximum c + c₂Calculation of one-way function operation is required.

According to the modified first embodiment described above, the storage amount of the user is slightly increased as compared with the basic embodiment, but when the number of excluded users is small, the transmission amount is significantly reduced. ..

&lt;Transformed second embodiment&gt; As a result of the modified embodiment described above, a result approximated to the transmission amount r could be obtained. It can be seen that this is a considerably improved result when compared with the transmission amount of 2r-1 in the case of SD among the methods known so far. In the modified second embodiment described later, a method of reducing the transmission amount from r is proposed.

The basic concept of the modified second embodiment is as follows. Excluded users (revoked user) When a set of users located between two people is used as an interval, the total number of intervals cannot be less than r in the worst case. Since transmission is performed once for each section, it is unlikely that the transmission amount will be smaller than r when considering only such a section. Therefore, there may be cases where it is necessary to add various types of sections to the basic section.

Therefore, in a modified second embodiment of the present invention, a transmission section is set by adding a section including one or more excluded users. Hereinafter, an example in which a section including one excluded user is added will be described, and the case where a section including two or more excluded users is added based on the same method can be extended and applied. For example, since one section is created by a total of three excluded users, the transmission amount can ideally be reduced to r / 2.

FIG. 16 is a drawing showing a method of setting a section according to a modified second embodiment of the present invention. In the modified second embodiment of the present invention, the transmission amount is reduced and the storage amount is increased by setting the section so as to include the excluded user in the section. That is, the key can be transmitted at once for the two excluded users.

As shown in FIG. 16, there are two cases in which one excluded user is added. Of the above two cases, the case (1) can be solved by the above-mentioned basic embodiment, and the case (2) can be solved efficiently by the modified second embodiment described later.

The session key is transmitted to the section as described in (2) as follows. A modified second embodiment of the present invention requires a new one-way hash function, the g-function. That is, the interval {u_i, U_{i + 1}, U_{i + 2}, ... u_{i + S}} Excluded users u_{i + j}When it is assumed that the section includes, (assuming that the length of the entire section does not exceed c), the center is h.^(sj)gh^(j-2)(K_i) Is used to encrypt the SK.

Although FIG. 16 describes a form in which one excluded user is added, the present invention can be applied in the same manner even when a plurality of excluded users are added as described above.

FIG. 17 is a drawing showing a method of associating a key value with each node in the linear structure according to the modified second embodiment of the present invention. As shown in the figure, 1701,1702,1703,1704 are excluded by applying the hash function h to the right along the same one-way key chain as in the basic embodiment before the excluded users appear. User u_{i + j}At position 1705, the one-way keychain is deformed by using a further one-way hash function, g, instead of the one-way hash function h.

Then, after passing through the excluded users, the key values are generated again using the one-way hash function h in 1706 and 1707 to create a one-way key chain. Then, when transmitting the session key, SK is encrypted with a value corresponding to the position of the last user and transmitted.

Since the two one-way functions h and g are all public functions, the user located on the left side of the excluded user can easily calculate the key used for encryption. But excluded users u_{i + j}Is gh^(j-1)(K_iIf you do not know the value of), you cannot calculate the value after that, so at the center, gh^(j-1)(K_i) Is kept secret.

On the other hand, in the case of a user located on the right side of the excluded user, a value corresponding to his / her position from the chain must be added and saved. If the length of the section is set as c, the number will be 1 + 2 + 3 + ... + (c-2). Therefore, each user should add the keys (c-1) (c-2) / 2 and save.

According to the modified second embodiment of the present invention described above, the total conserved quantity is c + (c-1) (c-2) / 2, that is, O (c).²), But the transmission amount is r / 2 + (N-2r) / c, and it can be seen that the previous r part has been reduced to r / 2. Further, the amount of calculation is the calculation of the one-way operation up to c times as in the basic embodiment.

When calculating for the cases where N = 1,000,000 and r = 50,000 described above, the results shown in Table 2 below are obtained.

<tables num="2"><img id="000005" he="21" wi="158" file="JP6139965B2_D0001.tif" img-format="tif" img-content="drawing" /></tables>

According to Table 2 above, it can be seen that in the transmission amount, the front r portion decreased as shown in r / 2, but the (N-2r) / c added later increased.

On the other hand, the method of the modified second embodiment described above is a general case and can be extended. That is, the conserved quantity is O (c)³), And it is embodied so that the key can be transmitted in one transmission in the section including the three excluded users. Therefore, as described above, it can be applied not only to one section but also to a section including a plurality of excluded users.

&lt;Transformed Third Embodiment&gt; As a final embodiment, the modified third embodiment of the present invention is an embodiment in which the above-mentioned modified first embodiment and the second embodiment are simultaneously applied. In such a case, the worst case is a case where each user excluded in the section having the length c is included. The reason is that if two or more excluded users are included in a section whose length is less than c, the two excluded users are once excluded based on the modified second embodiment described above. This is because it can be solved by the transmission of. The amount of transmission in such a worst case is r / 2 + (N-2r) / 2 (c-2), and the conserved quantity is c + c.₂+ (C-1) (c-2) / 2.

The formula for this transmission amount applies when r is greater than N / c. Further results are obtained if r is less than N / c. For example, if r = 0, the required transmission amount is N / (c × c).₂). It should be noted that the method in the first embodiment in which one transmission is required for the section having the length c including the excluded users while r gradually increases, and the remaining portion is modified. Is applied, so roughly r + (N-cr) / (c × c₂) Is required.

That is, N / (c × c₂) Is the initial value, and a straight line with a gradient of 2 is formed. In the same way, the increased transmission volume changes toward r / 2 + (N-2r) / 2 (c-2) at the turning point when r is N / c.

According to the above-described modified third embodiment, the storage amount of the user is slightly increased as compared with the basic embodiment, but when the number of excluded users is small, the transmission amount is significantly reduced.

&lt;Transformed Fourth Embodiment&gt; The modified fourth embodiment of the present invention is a method in which the basic embodiment in the linear structure described above and the modified first embodiment to the modified third embodiment are applied in an annular structure.

First, the straight line structure in the above-described embodiment can be easily reconstructed with an annular structure. That is, u₁From u_NWhen considering a straight line L having up to N users, if the two end points of the L are connected, the straight line becomes an annular shape.

All one-way keychain methods such as the basic embodiments described above can be applied to the preset section from the ring. For example, user u_NA one-way keychain is constructed starting from the node.

In the basic embodiment having the linear structure, the user u_NThe one-way keychain starting from the node is K_{N, N}Has one key. On the other hand, in the annular structure according to the modified fourth embodiment of the present invention, the above u_NAnd u₁Connect to form a one-way keychain, so user u_NA one-way keychain starting from a node has c key values such as the number 3 below.

<maths num="3"><img id="000006" he="10" wi="158" file="JP6139965B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Generalize this to u_iA one-way keychain starting from a node can be represented by the following number 4.

<maths num="4"><img id="000007" he="11" wi="158" file="JP6139965B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

That is, in the modified fourth embodiment, assuming that the maximum length of the section consisting of consecutive legitimate users is c, in the linear structure, 1 to c keys are stored according to the position of each user. However, in a circular structure, each user should store c keys.

FIG. 18 is a drawing showing the result corresponding to the key value for each ring node according to the modified fourth embodiment of the present invention. As shown in the figure, in the modified fourth embodiment, the number of nodes constituting the circular group is 10, and the maximum length of the section composed of consecutive legitimate users is 5. In this case, you can see that each node stores 5 keys.

Thereby, even in the annular structure, in order to supplement that the transmission amount becomes larger than r by setting the section length in the above-described modified first embodiment as c, once for a long section. A method in which the key value can be transmitted only by transmission is applicable. At the same time, in the annular structure as well, in order to reduce the transmission amount in the above-described modified second embodiment from r, a method of applying a new one-way function from the position of the excluded user is applicable. Further, the application is also possible based on the combined method of the modified first embodiment and the modified second embodiment in the above-mentioned modified third embodiment.

&lt;Transformed Fifth Embodiment&gt; A modified fifth embodiment of the present invention proposes an annular structure having a hierarchical structure.

FIG. 19 shows a hierarchical structure of a ring-shaped node group according to an embodiment of the present invention.

With reference to the figure, the node group of each circular structure on the hierarchical structure consists of c nodes. At this time, each user corresponds to each point in all the nodes (that is, the annular structure) of the hierarchical structure. If the hierarchical structure is composed of 16 layers excluding the roots node, the hierarchical structure is c.¹⁶Will be able to handle the users of.

Therefore, it is possible to construct an annular structure having a key chain as described above for each group node in each layer. At this time, the user corresponding to each of the nodes has all the key values assigned to his / her parent node.

From the structure, each node having a child node containing at least one excluded user is considered as an excluded node. Therefore, when encrypting, the center first displays the excluded nodes. Then, in the center, the parent nodes of the excluded nodes are displayed according to the hierarchical structure.

This process is completed up to the roots node, and if there is at least one excluded node, the roots node becomes the excluded node.

After confirming the excluded nodes, the center sets the section in each hierarchy. As shown, only one node is included above the 0th hierarchy.

First, in the center, a circulation section is set from the circular group of the 0th layer, and the session key is encrypted as the section key for each of the set circulation sections. Then, the center considers only the circular group corresponding to the child node of the node excluded in the 0th layer for the 1st layer. The above process proceeds up to the 15th level.

For example, if there is one excluded user, one excluded node will be generated from all the hierarchies in the display process. Further, since there is one excluded node in the 0th layer in the encryption step, the session key is encrypted as the section key for the circulation section excluding one node in the center. On the other hand, for the first layer, the center considers only one circular group corresponding to the child node of the excluded node in the 0th layer.

Each node constituting the circular group corresponding to the child node of the authenticated node can obtain the session key given by the parent node. As a result, the center can perform encryption processing for the entire hierarchical structure by encrypting 16 times.

In the modified fourth embodiment described above, it is possible to perform encryption processing for a larger number of users than in the previous embodiment, but a larger number of keys are required. However, the transmission overhead (TO) can be significantly reduced as compared with the second embodiment described above.

That is, assuming that the hierarchy of the modified fourth embodiment is k hierarchy and the number of nodes included in each ring group is c, the storage overhead of each user in the modified fourth embodiment is assumed. Is kc + (c-1) (c-2) / 2, and (k-1) c keys are incremented.

On the other hand, the transmission overhead is c^k-1If / 2 &lt;r, it is about r / 2 + 3N / 4c. It can be seen that when r &lt;N / 6, the modified fourth embodiment has less transmission overhead than the above-mentioned modified second embodiment.

Further, in the previous description, the section (1-punctured) including one excluded user is applied, but in the modified second embodiment, as described above, a plurality of excluded users are applied. It is self-evident that it can also be applied to the included interval (p-punctured). Further, the section setting and transmission method for the excluded users can be used for more layers in the above-mentioned hierarchical structure.

Although each embodiment of the present invention has been described above, it is difficult for all users to join at the initial stage of the system when this embodiment is actually applied to broadcast encryption. That is, the center should have pre-configured keys for future users, but such keys should basically be maintained in an excluded state. Otherwise, the newly subscribed user may recover the message transmitted in the past.

For most broadcast encryption, this can be a heavy burden on the center, given that the amount of transmission depends on r. Therefore, the ability to add a new user's key later without creating it in advance is extremely important. The embodiment proposed above can be easily solved by adding a new node to the right of the straight line each time a new user is added. At this time, the amount of calculation is added by selecting a new random value and performing the operation of the one-way function several times, so that users can be added efficiently. Of course, it has no effect on the keys of other users.

On the other hand, from the user's alternative side, this involves maintenance after the system has been used for a long time. When the system is maintained for a long time, the permanently excluded users are always excluded, which increases the transmission amount in most methods where the transmission amount depends on r. It leads to a factor.

In such a case, it is necessary to reduce the number of excluded users by adding a new user to the position after removing the key of the permanently excluded user. In a conventional method such as interpolation, such user substitution can be performed at any rate, but it is a difficult task according to a method using a structure such as a hierarchy. In the case of SD, the key of the roots node must be newly changed in order to substitute one user, so there is an inconvenience that the keys of all users must be updated.

On the other hand, in the above-described embodiment of the present invention, it can be applied relatively easily as compared with the method using a tree such as SD. That is, if one user is to be replaced, in the case of the basic embodiment, the keys of a total of 2c users may be updated.

A traitor is a legitimate user who helps to leak his or her password and show a message to an illegal user. Rebel tracking is an algorithm that finds the user who leaked the key from the keys they have when such illegal users exist.

There are various results for such rebel tracking, but if each user's key is all distinguishable and it is not possible to generate a new key from a large number of user's keys, rebel tracking is basically possible. Is known as. On the other hand, the previously proposed embodiment of the present invention satisfies such a property, so that the rebel can be tracked.

Further, by transforming the basic embodiment into a method using a public key, the number of password keys for each user can be reduced to two. In this case, the required public key is O (c)²). Such variants are useful when used in applications where the size of the public key is not limited.

In conclusion, Table 3 below shows the results of comparison between the present invention and the most effective CS and SC methods among various broadcast encryption methods. It should be noted that N = 1,000,000 and r = 50,000 as in the above-mentioned result.

<tables num="3"><img id="000008" he="39" wi="159" file="JP6139965B2_D0001.tif" img-format="tif" img-content="drawing" /></tables>

With reference to Table 3 above, it can be seen that the most important transmission amount in broadcast encryption is reduced to less than r based on the embodiments of the present invention. That is, it can be seen that the embodiment of the present invention has significantly reduced the transmission amount as compared with SD, which is known to be the most preferable method so far. It also includes various properties required for the actual application described above.

Although preferred embodiments of the present invention have been illustrated and described above based on the drawings, the scope of protection of the present invention is not limited to the above-described embodiments, but the inventions described in the claims and their equivalents. It extends to things.

The present invention is used for encryption such as broadcast encryption.

100 content producers 110 Service Provider 120 satellites 130 internet network 140 network 141 set-top box 142 Mobile communication terminal 150 smart home network 151,152,153,154,155 terminals 160 Illegal users