JP4208678B2 - Key information processing method and apparatus, and program - Google Patents

Description

  The present invention relates to key management, a method for reducing the load related to the amount of computation required for key generation and the number of key distributions, and a content distribution system and a removable media control method that need to manage a plurality of keys for decryption In the above, it is a thing suitable for.

  In recent years, opportunities for distributing digital contents such as documents and image data through large-capacity recording media such as communication lines and DVDs are increasing. The digital content distribution service is a service for distributing content to a specific user. However, a mechanism that does not leak content is required for non-users. A similar user access control mechanism is also being studied for content distribution using large-capacity media. At that time, the content data is encrypted, scrambled, etc., and only a legitimate user who has valid key information or knows the descrambling process performs the decryption process to create a legitimate document or image. There is a mechanism to enjoy content such as data.

  In such content distribution services, there are content providers that distribute content. Content providers need to set different access control information for each of multiple contents, and encryption with different keys for each content, for each user, and for each user action (for example, browsing, copying, etc.) It is assumed that processing will be performed. In this process, management related to key information such as key generation, key holding, and key distribution is often very burdensome at the content provider. Therefore, research is being conducted on more efficient management methods for key management without lowering the security level. Some of the conventional management methods will be described.

[Tree structure management method]
The tree structure management method is used in offline content playback devices such as a DVD player, and is suitable for invalidating a user. In this method, the encrypted data is distributed simultaneously with the key information used for encryption and the encrypted content or stored in a medium so that only authorized users can decrypt the encrypted data. Although it is necessary to distribute key information in advance in an appropriate combination to each user, a vast amount of user key information can be efficiently managed by using a tree structure.

  In this management system, there are the following indicators for determining the quality of the system. There are three indicators: 1) the data size of the key information delivered simultaneously with the content, 2) the data size of the pre-distributed key information that holds the user, and 3) the data size of the key information that the content provider needs to manage. That's it. In the case of an online distribution service, 1) which influences network traffic will be emphasized, but from the viewpoint of a content provider, the management cost of 3) will be most important. It should be noted that the weight of the index changes depending on the situation.

  A typical tree structure management method is a content distribution model (see, for example, Non-Patent Document 1). In this model, a key distribution tree structure as shown in FIG. 14 is used, and a different key is arranged at each node. It is assumed that the user key (assuming a key held by a player such as a DVD in the paper) is identified with the terminal node (leaf) and holds all key data from the root to the terminal node. In this model, it is assumed that updates occur frequently, and this arrangement improves the efficiency of key revocation.

[Hierarchical key management method]
On the other hand, the key management assumed in the hierarchical key management method is the same in that the key is arranged in each node, but the user is not limited to the terminal node, but the key located in all nodes including the root. Is greatly different (see, for example, Non-Patent Documents 2 and 3).

  In addition, an access structure as shown in FIGS. 15 and 16 is assumed instead of an n-ary tree structure as shown in FIG. 14, and when viewed locally, a portion having a relationship as shown in FIG. 17 can be seen. . In this case, it is necessary to provide a mechanism that can generate a key that the node n3 should have from both the key arranged at the node n1 and the node n2. According to the paper of Birget et al., The following two methods have been proposed as a method for providing this mechanism.

[(1) User multiple keying]
Each node holds a plurality of keys, and the parent node is configured to hold all the keys of the child nodes. FIG. 18 shows an example thereof, in which a set of key data distributed to each node is described. For example, it can be seen that the key data k5 is included in the parent node of the node to which {k5} is distributed. Similarly, in other nodes, it can be seen that the parent node includes all the key data of the child nodes.

  [(2) One-way function based keying schemes] This is an extended system of Lin et al., And by using a one-way hash function, key information held by each node can be reduced. However, as shown in FIG. 17, when generating key data of a child node from key data of a plurality of parent nodes, the following operation is necessary. This operation will be described with reference to FIG.

In FIG. 19, in order to generate k3 from the key data k1 or k2, k3: = F (k1, n3) XOR r13
k3: = F (k2, n3) XOR r23
Perform the operation. Here, XOR is an exclusive OR for each bit. F () is a one-way hash function, details of which will be described later. n3 is an identifier of the node to which the key data k3 is associated, r13 and r23 are respectively the random data associated by the node n1 (key data k1) and the node n3, and the node n2 (key data k2) and the node n3, respectively. It is random data and is data that is open to the public.

The function F () is composed of F (k_i, n_j) = g ^ {k_i + n_j} mod p (where p is a prime number and g is a primitive element). It is generated so as to satisfy F (k2, n3) XOR r23.
“Digital Content Protection Management Method” SCIS2001, pp. 213-218 C. H. Lin. “Dynamic key management schemes for access control in a hierarchy”, Computer Communications, 20: 1381-1385, 1997. J. et al. -C. Biget, X. et al. Zou, G. et al. Neubir, B.M. Ramamthy, “Hierarchy-Based Access Control in Distributed Environments” in the Processing of IEEE ICC, June 2001.

  As described above, when there are two parent nodes locally in the hierarchical key management method (see FIG. 17), a method for generating the same key data from different parent nodes has already been proposed. However, in 1) User multiple keying, each node must have many keys, and there is a problem that the key data to be held increases geometrically as the hierarchy deepens. 2) One- In the way function based keying schemes, the amount of key data held by each node is reduced by using a one-way hash function, but it is necessary to separately hold public random data such as r12, r13, etc. However, there is a problem that data to be held increases as the hierarchy becomes deeper.

  Furthermore, in 2), a power operation is used for the one-way hash function. Although a configuration using a hash function with a trapdoor is conceivable, in any case, an operation requiring a power operation is included, and the calculation cost is enormous. In particular, a device such as a PDA with a small amount of calculation resources spends a lot of time for key calculation, and as a result, there is a possibility that interactive processing cannot be performed during data decryption.

  Therefore, in view of the above-described problems, the present invention generates a key for a partial image data having a hierarchical structure by a method with a smaller calculation amount and generates an individual key for partial image data in a higher layer even if collusion is performed. The goal is to make things impossible.

  In order to solve the above-described problem, according to the present invention, the control method of the information processing apparatus includes a plurality of partial images having a hierarchical relationship in which the setting unit includes any two of image data quality, resolution, and image area. For each partial image data, a setting step for setting a set of hash function counts for each of the first key and the second key, and a key generation means, for each partial image data, An individual key for the partial image data is generated as a value obtained by executing the hash function according to the number of times corresponding to the set of the number of times set for the partial image data for each of the key and the second key. A key generation step, and in the setting step, for the first key, the upper right cell in the matrix is the origin (0, 0), and the x coordinate is incremented by 1 in the horizontal left direction, and the vertical downward direction The y coordinate is not 1 Define an increasing coordinate axis, and if j = 0, then set x_ij = i, j as the set of times (x_ij, y_ij) for the cell of coordinates (i, j) of the matrix whose size is Nx * Ny If ≠ 0, x_ij = Nx + j-1 is set, and if i = 0, y_ij = j, and if j ≠ 0, y_ij = Ny + i-1 are set. The upper right cell is the origin (0, 0), and the coordinate axis is defined such that the x coordinate increases by 1 in the horizontal left direction and the y coordinate increases by 1 in the vertical downward direction, and the size is (Nx-2) * When the set of the number of times for the cell at coordinates (i ′, j ′) in the matrix (Ny−2) is (u′_i′j ′, v′_i′j ′), the size is Nx * The set of times (u_ij) for the cell at coordinates (i, j) in the matrix Ny v_ij), when i = 0 and j = 0, u_ij = 0 and v_ij = 0, and when i = Nx-1, or j = Ny-1, u_ij and v_ij Information indicating that the key does not exist, and when i = 0 and j ≠ 0, u_ij = u′_i (j−1) and v_ij = v′_i (j−1), j = 0, and When i ≠ 0, u_ij = u ′ _ (i−1) j and v_ij = v ′ _ (i−1) j. Otherwise, u_ij = u ′ _ (i−1) ( j-1) and v_ij = v ′ _ (i−1) (j−1), and the number of execution times of each cell in the matrix whose size is (Nx−2) * (Ny−2) The set is set with the same setting as the first key.

  Further, according to another aspect, the information processing apparatus performs the first processing on each partial image data of a plurality of partial image data having a hierarchical relationship including any two of image quality, resolution, and image area of the image data. A setting unit that sets a set of the number of times of the hash function for each of the key and the second key, and a key generation unit, for each partial image data, for each of the first key and the second key A key generation unit that generates an individual key for the partial image data as a value obtained by executing the hash function according to the number of times corresponding to the set of the number of times set for the image data; For the first key, the upper right cell in the matrix has an origin (0, 0), and a coordinate axis in which the x coordinate is incremented by 1 in the horizontal left direction and the y coordinate is incremented by 1 in the vertical downward direction. Define and size x_ij = i when j = 0, x_ij = Nx + j-1 when j = 0, and x_ij = i when j = 0 for the cell of coordinates (i, j) of the matrix of x * Ny, When i = 0, y_ij = j, and j ≠ 0, y_ij = Ny + i−1. For the second key, the upper right cell in the matrix is the origin (0, 0), and A coordinate axis is defined such that the x coordinate is incremented by 1 in the horizontal left direction and the y coordinate is incremented by 1 in the vertical downward direction, and the coordinates in the matrix having a size of (Nx−2) * (Ny−2) ( When the set of the number of times for the cell of i ′, j ′) is (u′_i′j ′, v′_i′j ′), the coordinates (i, j) of the matrix whose size is Nx * Ny As a set (u_ij, v_ij) of the number of times for the cell, i = 0 and j = 0 If u_ij = 0 and v_ij = 0, and i = Nx-1 or j = Ny-1, then u_ij and v_ij are information indicating that the second key does not exist, and i = 0 When j ≠ 0, u_ij = u′_i (j−1) and v_ij = v′_i (j−1), and when j = 0 and i ≠ 0, u_ij = u′_ (I-1) j and v_ij = v ′ _ (i−1) j, and in other cases, u_ij = u ′ _ (i−1) (j−1) and v_ij = v ′ _ (i -1) Set as (j-1), and set the number of execution times of each cell in the matrix whose size is (Nx-2) * (Ny-2) with the same setting as the first key It is characterized by doing.

  As described above, according to the present invention, in generating keys for partial image data having a hierarchical structure, an individual key for higher-level partial image data is generated by a method with a smaller calculation amount and even when collated. It becomes possible not to be able to.

  Hereinafter, preferred embodiments of the present invention will be described with reference to the drawings.

<First Embodiment>
FIG. 1 is a diagram for explaining an electrical configuration of an information processing apparatus for realizing each embodiment according to the present invention. Note that, in realizing the present invention, it is not essential to use all the functions shown in FIG.

  As shown in FIG. 1, the information processing apparatus 100 includes a modem 118 such as a public line, a monitor 102 as a display unit, a CPU 103, a ROM 104, a RAM 105, an HD (hard disk) 106, a network connection unit 107, a CD 108, and an FD ( Flexible disk) 109, DVD (Digital Video Disk or Digital Versatile Disk) 110, interface (I / F) 117 of the printer 115, and interface (I / F) 111 such as a mouse 112 and a keyboard 113 as an operation unit. Are communicably connected to each other via a bus 116.

  The mouse 112 and the keyboard 113 are operation units for the user to input various instructions to the information processing apparatus 100. Information (operation information) input via the operation unit is taken into the information processing apparatus 100 via the interface 111.

  Various information (character information, image information, etc.) in the information processing apparatus 100 can be printed out by the printer 115.

  The monitor 102 displays various instruction information to the user and various information such as character information or image information.

  The CPU 103 controls operation of the entire information processing apparatus 100, and controls the entire information processing apparatus 100 by reading and executing a processing program (software program) from the HD (hard disk) 106 or the like. In particular, in the present embodiment, the CPU 103 reads out and executes a processing program that realizes key generation from the HD 106 or the like, thereby performing information processing to be described later.

  The ROM 104 stores a processing program for key generation, various data (such as a key generation graph) used in the program, and the like.

  The RAM 105 is used as a work area or the like for temporarily storing a processing program and information to be processed for various processes in the CPU 103.

  The HD 106 is a component as an example of a large-capacity storage device, and stores various data or a processing program for information conversion processing that is transferred to the RAM 105 or the like when various processing is executed.

  The CD (CD drive) 108 has a function of reading data stored in a CD (CD-R) as an example of an external storage medium and writing data to the CD.

  Similar to the CD 108, the FD (floppy (R) disk drive) 109 reads data stored in the FD 109 as an example of an external storage medium. It also has a function of writing various data to the FD 109.

  Similar to the CD 108 and the FD 109, the DVD (digital video disk) 110 has a function of reading data stored in the DVD 110 as an example of an external storage medium and writing data to the DVD 110.

  For example, when an editing program or a printer driver is stored in an external storage medium such as CD 108, FD 109, or DVD 110, these programs are installed in the HD 106, and if necessary, You may comprise so that it may transfer to RAM105.

  An interface (I / F) 111 is used to receive input from the user via the mouse 112 or the keyboard 113.

  The modem 118 is a communication modem, and is connected to an external network through an interface (I / F) 119 through, for example, a public line.

  The network connection unit 107 is connected to an external network via an interface (I / F) 114.

  Hereinafter, key generation / management by the above-described apparatus will be described.

[Key generation overview]
First, a description will be given of generation of individual keys for each node in the hierarchical key management method.

  In the following, for the sake of convenience, as shown in FIG. 2, the tree structure in the hierarchical key management method will be replaced with a matrix. FIG. 2A shows an example of a tree structure composed of seven hierarchies and having 16 nodes. FIG. 2B shows an example in which the tree structure shown in FIG. 2A is replaced with a matrix. The numbers written in each node in FIG. 2A and the numbers written in each cell in FIG. 2B indicate the same correspondence.

  First, in the tree structure as shown in FIG. 2A, the root node (the node indicated by “0” in the figure) is associated with the upper right cell in the matrix. Then, the node located on the left and the node located on the right among the child nodes of each node in the tree structure are associated with the left cell and the lower cell of the matrix cell, respectively. By performing this association for all nodes and cells in order, the tree structure shown in FIG. 2A can be replaced with the matrix shown in FIG.

  Next, key generation in the present embodiment will be described. Key generation is performed according to the key generation matrix and graph shown in FIGS.

  Individual keys for each element and each node other than a type A key obtained by applying a hash function from two original keys common to all nodes and leaf nodes (nodes having no child nodes) in the tree structure There are two types of type B keys that can be obtained only by nodes.

  In the tree structure, a group called “rank” is defined for convenience as a set of nodes existing in the same hierarchy. The root node is assumed to be rank 1, and the rank number is incremented by 1 every time a hierarchy is passed (see FIG. 2A).

  Further, in the matrix, in order to show the coordinates of each cell, the coordinate axis is such that the uppermost element is the origin (0, 0), the x coordinate increases in the horizontal left direction, and the y coordinate increases in the vertical downward direction. Define According to this definition, for example, the coordinates of the element marked “4” in FIG. 2B are (1, 1), and the coordinates of the element marked “14” are (2, 3). ) (See FIG. 2B).

  In the following description, the number of cells in the horizontal direction of the matrix is Nx, and the number of cells in the vertical direction is Ny.

[Type A key]
An example of the type A key will be described with reference to FIG. 3A and FIG. 3A shows an example of a type A key matrix with Nx = 4 and Ny = 4, and FIG. 4A shows an example of a type A key matrix with Nx = 5 and Ny = 5. Let two original keys from which all type A keys are generated be x and y, respectively. In FIG. 3A and FIG. 4A, the two numbers described in each cell represent the number of hash functions to be applied to x and y. For example, in a cell marked [1, 4], it is assumed that H (x) and H (H (H (H (y)))) are held as type A keys. When a hash operation is performed n times in the future, it will be expressed as H ^ n (). Based on this notation, a cell marked [1,4] has two type A keys, H (x) and H ^ 4 (y).

[Type B key]
An example of a type B key will be described with reference to FIGS. 3B and 4B. Note that FIG. 3B and FIG. 4B have matrices of the same size as FIG. 3A and FIG. 4A, respectively. These keys do not exist in the bottom row and the leftmost column in the matrix. The symbol 'N' is used below to indicate that no key exists. In addition, the value of the type A key whose size is Nx-2 and Ny-2 is directly applied to the cells other than the leftmost column, the rightmost column, the lowermost row, and the uppermost row. Further, the value of the cell immediately below it is applied to the cells in the uppermost row other than these, and the value of the cell to the left is applied to the cells in the rightmost row as they are.

  Let u and v be two original keys from which all type A keys are generated, respectively. Similar to the type A key, two numbers added to the respective cells in FIGS. 3B and 4B represent the number of hash functions to be applied to u and v. .

  Furthermore, as shown in FIG. 4C, when the larger size of the type B key matrix is 5 or more, the size is Nx− as shown in FIG. 2 and Ny-2 fusion keys are applied. Details of the fusion key will be described later.

[Fusion key]
In the present embodiment, the type A key and the type B key as described above are fused and used. Hereinafter, a key obtained by fusing the type A key and the type B key is referred to as a fused key. FIG. 5 shows a fusion key matrix (FIG. 5A) when Nx = 4 and Ny = 4 as shown in FIG. As shown in FIG. 5, the type A key and the type B key located in the same cell are fused to generate a corresponding fused key. For example, in FIG. 5A, cell (1, 2) holds fusion keys H ^ 5 (x), H ^ 4 (y), H ^ 2 (u), and H (v). Means.

  As described above, the key matrix in the present embodiment as described above can also be expressed as a tree structure. FIG. 5B shows an example of the case where the matrix shown in FIG. 5A is expressed by a tree structure.

[Key Generation Graph Generation Method]
Next, a processing method for generating a fusion key in this embodiment will be described with reference to FIG.

  As shown in FIG. 6, first, in step S601, variables Nx and Ny indicating the number of cells in the horizontal direction and the vertical direction of the fusion key matrix are initialized. An appropriate value may be set according to the number of objects to be subjected to access control. For example, when performing access control according to resolution and image quality for image data having 6 resolutions and 5 image quality, settings are made such that Nx = 6 and Ny = 5. However, the present invention is not limited to this, and can be applied to various access controls. Further, a variable PL indicating the processing level is initialized to 0.

  Next, step S602 initializes the number of elements stored in each cell of the fusion key matrix. In the present embodiment, the number of fusion keys to be stored in one cell generated by the fusion key generation process described later is set as the number of elements. In the fusion key generation process in this embodiment, since Min (Nx, Ny) fusion keys are generated for one cell, the number of elements is set to Min (Nx, Ny). Min (a, b) is an operation for selecting a smaller value from a and b. For example, if Nx = 6 and Ny = 5 as described above, the number of elements stored in one cell is initialized to 5.

  Step S603 generates a fusion key matrix of size Nx * Ny at the processing level PL. Details of the fusion key generation process in this embodiment will be described later.

  In step S604, the generated fusion key at each processing level PL is merged into one fusion key matrix. In the present embodiment, the type A key with the processing level PL = 0 and the type B key with the processing level PL = 0 are merged, and all the generated type B keys (after the processing level PL1) after that are merged. To merge.

  The processing method for generating the fusion key in the present embodiment has been described above.

  Next, the fusion key generation process in this embodiment will be described with reference to FIG. FIG. 7 is a flowchart for explaining the fusion key generation process in this embodiment.

  As shown in FIG. 7, first, in step S701, it is determined whether Max (Nx, Ny) is 2 or less. Note that Max (a, b) is an operator that selects a large value from a and b. If the value is 2 or less, the process proceeds to step S702. Otherwise, the process proceeds to step S703.

  A step S702 generates a type A key matrix of size Nx * Ny at the processing level PL, generates a type A key matrix, and then ends the fusion key generation process.

  On the other hand, step S703 generates a fusion key matrix of size (Nx-2) * (Ny-2) at the processing level PL + 1. Further, after generating the fusion key matrix, step S704 generates an Nx * Ny type B key matrix at the processing level PL, and ends the fusion key generation process.

  As described above, in the present embodiment, in order to generate a fusion key matrix having a size Nx * Ny at the processing level PL, a fusion key having a size (Nx-2) * (Ny-2) at the processing level PL. A matrix is generated recursively. That is, a larger fusion key matrix is sequentially generated using a smaller fusion key matrix.

  Next, a method of generating a type A key matrix will be described with reference to the flowchart of FIG.

  First, in step S801, variables i and j are set to zero. Variables i and j are indices indicating the horizontal and vertical coordinates of the matrix, respectively.

  In step S802, the value of the variable Ny is evaluated. If Ny is 1, the process proceeds to step S814. Otherwise, the process proceeds to step S803.

  In step S803, the value of the variable j is evaluated. If j is 0, the process proceeds to step S804. Otherwise, the process proceeds to step S805. In step S804, the value i is assigned to the x key x_ (i, j) of the cell (i, j). On the other hand, step S805 substitutes the value Nx + j−1 for the x key x_ (i, j) of the cell (i, j). Thereafter, the process proceeds to step S814.

  In step S814, the value of the variable Nx is evaluated. If Nx is 1, the process proceeds to step S809. Otherwise, the process proceeds to step S806.

  In step S806, the value of the variable i is evaluated. If i is 0, the process proceeds to step S807. Otherwise, the process proceeds to step S808. In step S807, the value j is substituted into the y key y_ (i, j) of the cell (i, j). On the other hand, step S808 substitutes the value Ny + i−1 for the y key y_ (i, j) of the cell (i, j). Thereafter, the process proceeds to step S809.

  In step S809, the variable i is increased by 1, and the process proceeds to step S810. In step S810, the value of the variable i is evaluated. If i is smaller than Nx, the process proceeds to step S803. Otherwise, the process proceeds to step S813, the variable i is initialized to 0, and the process proceeds to step S811.

  In step S811, the variable j is incremented by 1, and the process proceeds to step S812. In step S812, the value of the variable j is evaluated. If j is smaller than Ny, the process proceeds to step S803. Otherwise, the type A key generation process is terminated.

  The type A key matrix generation method in the present embodiment has been described above. By the method described above, when Nx = 4 and Ny = 4, the type A key matrix described in FIG. 3A can be generated. When Nx = 5 and Ny = 5, the type A key matrix described in FIG. 4A can be generated in the same manner.

  Next, a method for generating a type B key matrix will be described with reference to the flowchart of FIG. First, in step S902, variables i and j are set to zero. Variables i and j are indices indicating the horizontal and vertical coordinates of the matrix, respectively.

  In step S903, the values of the variables i and j are evaluated. If i and j are both 0, the process proceeds to step S904. Otherwise, the process proceeds to step S905. In step S904, 0 is assigned to both the u key u_ (i, j) of the cell (i, j) and the v key v_ (i, j) of the cell (i, j). Thereafter, the process proceeds to step S911. Note that the u key u_ (i, j) is not generated when Nx = 3, and the v key v_ (i, j) is not generated when Ny = 3.

  In step S905, the values of the variables i and j are evaluated. If i is equal to Nx-1, or j is equal to Ny-1, the process proceeds to step S906. Otherwise, the process proceeds to step S907. In step S906, 'N' is assigned to both the u key u_ (i, j) of the cell (i, j) and the v key v_ (i, j) of the cell (i, j). As described above, 'N' is a code indicating that no key is set. Thereafter, the process proceeds to step S911. Note that the u key u_ (i, j) is not generated when Nx = 3, and the v key v_ (i, j) is not generated when Ny = 3.

  In step S907, the value of the variable i is evaluated. If i is 0, the process proceeds to step S908. Otherwise, the process proceeds to step S909. In step S908, u ′ _ (0, j−1) is assigned to the u key u_ (i, j) of the cell (i, j) and v key v_ (i, j) of the cell (i, j). Substitute v ′ _ (0, j−1). Here, u ′ and v ′ represent a type A key whose processing level is PL + 1, that is, whose matrix size is (Nx−2) * (Ny−2). The type A key whose processing level is PL + 1 is generated in advance in the fusion key generation process (step S703 in FIG. 7) before the type B key generation process (step S704 in FIG. 7). Thereafter, the process proceeds to step S911. Note that the u key u_ (i, j) is not generated when Nx = 3, and the v key v_ (i, j) is not generated when Ny = 3.

  In step S909, the value of the variable j is evaluated. If j is 0, the process proceeds to step S910. Otherwise, the process proceeds to step S915. In step S910, u ′ _ (i−1,0) is assigned to the u key u_ (i, j) of the cell (i, j), and v key v_ (i, j) of the cell (i, j). Substitute v '_ (i-1, 0). On the other hand, in step S915, u ′ _ (i−1, j−1) is assigned to the u key u_ (i, j) of (i, j), and the v key v_ (i, j, of cell (i, j)). Substitute v ′ _ (i−1, j−1) for j). Thereafter, the process proceeds to step S911. Note that the u key u_ (i, j) is not generated when Nx = 3, and the v key v_ (i, j) is not generated when Ny = 3.

  In step S911, the variable i is increased by 1, and the process proceeds to step S912. In step S912, the value of the variable i is evaluated. If i is smaller than Nx, the process proceeds to step S903. Otherwise, the process proceeds to step S915, the variable i is initialized to 0, and the process proceeds to step S913.

  In step S913, the variable j is increased by 1, and the process proceeds to step S914. In step S914, the value of the variable j is evaluated. If j is smaller than Ny, the process proceeds to step S903. Otherwise, the type B key generation process is terminated.

  The type B key matrix generation method in the present embodiment has been described above. By the method described above, when Nx = 4 and Ny = 4, the type B key matrix shown in FIG. 3B can be generated. When Nx = 5 and Ny = 5, the type B key matrix shown in FIG. 4A can be generated in the same manner.

[Validity of key generation]
The above graph generation method is generated so as to satisfy the following conditions.
-A node can only generate keys for its grandchild nodes-It cannot generate keys for its parent node from the key information of child nodes (unless the one-way function becomes weak)-Any two or more entities can collaborate However, it is impossible to generate a key for a node located above each entity. With these conditions, a hierarchical key management system capable of securely generating and distributing keys can be realized.

[Key distribution]
A key distribution method to each node by the root key distributor (entity of the root node) and a key distribution method to lower nodes by an entity holding an individual key other than the root key distributor will be described. First, the root key distributor generates keys x, y, u, and v randomly and securely, and sets them as their own individual keys. Further, a plurality of keys are arranged at each node by the above-described key generation procedure. The root key distributor securely distributes the key of each node to the entity located at each node. Also, a key distribution graph as shown in FIGS. 3 and 4 is made public, and data that can identify the position of the distributed key in the graph is distributed to each entity. For example, this data may be constituted by a rank number in a tree structure and an in-rank identification number indicating the number within the same rank, or may be constituted by coordinates in a matrix.

  Next, a key distribution method by an entity holding an individual key other than the root key distributor will be described. Key data for the child node or grandchild node is generated from the identification data indicating the position of the key in the individual key and the key distribution graph. For example, in FIG. 5A, it has x ′, y ′, u ′, v ′ as a fusion key, and this is the cell (1, 1) in the matrix, that is, the second rank 3 at the position on the graph. Then, it corresponds to [4, 4, 0, 0]. This entity is H ^ 4 (x) = H ^ 0 (H ^ 4 (x)) = x ', H ^ 5 for cell (2,1), the second child node in rank 4 (Y) = H ^ 1 (H ^ 4 (y)) = H ^ 1 (y '), H (u) = H ^ 1 (H ^ 0 (u)) = H ^ 1 (u'), and Since H ^ 2 (v) = H ^ 2 (H ^ 0 (v)) = H ^ 2 (v '), H ^ 4 (x'), H ( y ′), H 1 (u ′), and H 2 (v ′) can be distributed. It is clear that keys for other child nodes and grandchild nodes can be generated in the same manner.

[Key generation / distribution processing in information processing devices]
A procedure for performing the above key generation / distribution processing in the information processing apparatus 100 will be described. Data to be managed such as images is acquired through the CD 108 or the network connection unit 107 of the network and stored in the HD 106 or selected from data already stored in the HD 106. Here, the user selects from the list displayed on the monitor 102 using the mouse 112 or the keyboard 113.

  When the user selects an access control structure such as how many hierarchy axes to have for the management target data using a similar method, a key generation graph corresponding to the structure is calculated using the CPU 103, The data is stored in the RAM 105, the HD 106, or the like.

  Random data is generated from data such as the operation of the ROM 104, RAM 105, HD 106, or mouse 112, and a plurality of original keys are generated using the random data and stored in the RAM 105, HD 106, or the like. Further, the individual key of each node in the key generation graph is calculated from the original key and stored in the RAM 105, HD 106, or the like.

  The individual keys stored in the RAM 105, HD 106, etc. are read out to other information processing apparatuses and distributed via the network through the network connection unit 107.

[Hierarchical access structure with different number of levels for each hierarchy axis]
3 and 4 only illustrate the case where Nx and Ny are equal (Nx = Ny = 4 in FIG. 3 and Nx = Ny = 5 in FIG. 4), but the same applies when Nx and Ny are different. FIG. 10A shows a type A key and FIG. 10B shows a type B key that can be generated by this method. In FIG. 10, Nx = 3 and Ny = 4, but it can be seen that normal processing can be performed based on the flowcharts shown in FIGS.

<Second Embodiment>
A preferred example of access control using key data having a hierarchical structure generated by the key distribution method in the first embodiment will be described. The key generation graphs represented in FIGS. 3 and 4 have two hierarchical axes. FIG. 12 shows an example in which one of the resolutions (lower left direction) is the resolution and the other (lower right direction) is the image area.

  There are three levels of resolution, high, medium, and low, which indicate the resolution of the image that can be acquired. There are also three levels in the image area, and the authority to view all areas, sub-area A, and sub-area B (narrower than sub-area A) is given. At this time, the node having the highest authority located in the root is assigned (resolution = high, image region = all), and the lowest node is assigned (resolution = low, image region = region B).

  The key distribution method and the image encryption method will be described by taking the case of performing key distribution according to FIG. 11 as an example. FIG. 11 is an example of a type A key ((A) in FIG. 11) and a type B key ((B) in FIG. 11) when Nx = 3 and Ny = 3. The target image data IMG is image data IMG1 of region B, region A difference data is IMG_2, and difference data for obtaining all image data is IMG_3. That is, IMG = IMG_1 + IMG_2 + IMG_3. Each IMG_i is defined as IMG_i (L) for low resolution data, IMG_i (M) for medium resolution difference data, and IMG_i (H) for high resolution difference data. That is, IMG_i = IMG_i (L) + IMG_i (M) + IMG_i (H).

  First, the root key distributor randomly generates original keys x, y, and u. Key Key (<High, All>) used for encryption: = H (x || y || u), and IMG — 3 (H) is encrypted with this key. However, || is data concatenation. Each child node concatenates the acquired three data in the same manner as the root node to generate an encryption key, and encrypts the data shown in FIG.

  For example, in the <Mid, All> node, H (x), H ^ 3 (y), u are given as key data, but the encryption key Key (<Mid, All>): = H (H (x ) || H ^ 3 (y) || u), and IMG — 3 (M) is encrypted with this key. When decrypting the encrypted data, the same processing is performed to calculate the encryption key, and decryption processing is performed to obtain appropriate image data.

  In this embodiment, a method of concatenating and hashing keys is used as a method for generating an encryption key, but other key concatenation methods (methods for calculating one key from a plurality of key data) may be used.

  Further, in the present embodiment, the resolution and the image area are taken as a hierarchical axis, but the present invention is not limited to this, and from the hierarchy that should be subject to access control such as image quality, time axis, and usage control information, It is also possible to select and use any two or more hierarchies.

<Other embodiments using software, etc.>
Even if the present invention is applied as a part of a system composed of a plurality of devices (for example, a host computer, an interface device, a reader, a printer, etc.), a part of a device composed of a single device (for example, a copying machine, a facsimile machine). You may apply to.

  Further, the present invention is not limited to the apparatus and method for realizing the above-described embodiment and the method performed by combining the methods described in the embodiment, but is not limited to the computer (CPU or MPU) in the system or apparatus. This is also the case when the above-described embodiment is realized by supplying software program code for realizing the above-described embodiment and causing the computer of the system or apparatus to operate the various devices according to the program code. It is included in the category of the invention.

  In this case, the program code of the software itself realizes the function of the above embodiment, and the program code itself and means for supplying the program code to the computer, specifically, the program code Is included in the scope of the present invention.

  As a storage medium for storing such a program code, for example, a floppy (R) disk, a hard disk, an optical disk, a magneto-optical disk, a CD-ROM, a magnetic tape, a nonvolatile memory card, a ROM, or the like can be used.

  The computer controls various devices according to only the supplied program code so that the functions of the above-described embodiments are realized, and the OS (operating system) on which the program code is running on the computer is also provided. Such program code is also included in the scope of the present invention even when the above embodiment is realized in cooperation with a system) or other application software.

  Further, after the supplied program code is stored in the memory of the function expansion board of the computer or the function expansion unit connected to the computer, the program code is stored in the function expansion board or function storage unit based on the instruction of the program code. The case where the above-described embodiment is realized by performing a part or all of the actual processing and the processing is included in the scope of the present invention.

It is a block diagram which shows the structure of the processing apparatus which concerns on embodiment of this invention. It is a figure explaining the correspondence of the tree structure and matrix which concern on 1st Embodiment. It is a figure which shows the example of the graph for key generation which concerns on 1st Embodiment. It is a figure which shows the other example of the graph for key generation concerning 1st Embodiment. It is a figure explaining the fusion key which concerns on 1st Embodiment. It is a flowchart which produces | generates the fusion key which concerns on 1st Embodiment. It is a flowchart which produces | generates the fusion key whose size which concerns on 1st Embodiment is Nx * Ny. It is a flowchart which shows the procedure which produces | generates the type A key which concerns on 1st Embodiment. It is a flowchart which shows the procedure which produces | generates the type B key which concerns on 1st Embodiment. It is a figure which shows the other example of the graph for key generation from which a number of levels differs for every hierarchy axis | shaft. It is a figure which shows the example of the graph for key generation concerning 2nd Embodiment. It is a conceptual diagram explaining the hierarchical access structure which concerns on 2nd Embodiment. It is a table | surface showing the image list which each node which concerns on 2nd Embodiment should encrypt. It is a conceptual diagram explaining the binary tree access structure in a tree structure management system. It is a conceptual diagram explaining the access structure in a hierarchical access control system. It is a conceptual diagram explaining the access structure in a hierarchical access control system. It is a conceptual diagram explaining the local structure in a hierarchical access control system. It is a figure explaining the example of User multiple keying. It is a figure explaining One-way function based keying schemes.

Explanation of symbols

100 Information processing apparatus 102 Monitor 103 CPU
104 ROM
105 RAM
106 HD
107 Network Connection Unit 108 CD Drive 109 FD Drive 110 DVD Drive 111 Interface 112 Mouse 113 Keyboard 114 Interface 115 Printer 116 Bus 117 Interface 118 Modem 119 Interface

Claims (4)

A method for controlling an information processing apparatus,
The setting means hashes each of the first key and the second key with respect to each partial image data of a plurality of partial image data having a hierarchical relationship consisting of any two of image quality, resolution, and image area of the image data. A setting process for setting a set of the number of functions;
For each partial image data, the key generation means is configured to select the hash function according to the number of times corresponding to the set of the number of times set for the partial image data for each of the first key and the second key. A key generation step for generating an individual key for the partial image data as a value obtained by executing
In the setting step, for the first key, the upper right cell in the matrix is the origin (0, 0), the x coordinate is incremented by 1 in the horizontal left direction, and the y coordinate is incremented by 1 in the vertical downward direction. As a set (x_ij, y_ij) of the number of times for a cell of coordinates (i, j) of a matrix whose size is Nx * Ny
if j = 0, x_ij = i,
If j ≠ 0, then x_ij = Nx + j-1 and
if i = 0, y_ij = j,
If j ≠ 0, set y_ij = Ny + i-1
For the second key, the upper right cell in the matrix is the origin (0, 0), and the coordinate axis is such that the x coordinate increases by 1 in the horizontal left direction and the y coordinate increases by 1 in the vertical downward direction. Define the set of times for the cell at coordinates (i ′, j ′) in the matrix of size (Nx−2) * (Ny−2) (u′_i′j ′, v′_i′j )), The set (u_ij, v_ij) of the number of times for the cell at coordinates (i, j) in the matrix of size Nx * Ny
If i = 0 and j = 0, then u_ij = 0 and v_ij = 0,
When i = Nx−1 or j = Ny−1, u_ij and v_ij are information indicating that the second key does not exist,
When i = 0 and j ≠ 0, u_ij = u′_i (j−1) and v_ij = v′_i (j−1)
When j = 0 and i ≠ 0, u_ij = u ′ _ (i−1) j and v_ij = v ′ _ (i−1) j,
Otherwise, set u_ij = u ′ _ (i−1) (j−1) and v_ij = v ′ _ (i−1) (j−1),
A method for controlling an information processing apparatus, wherein a set of the number of times of execution of each cell in a matrix having a size of (Nx-2) * (Ny-2) is set with the same setting as the first key. .   The information processing apparatus control method according to claim 1, further comprising a key distribution step in which the key distribution unit distributes the individual key. For each partial image data of a plurality of partial image data having a hierarchical relationship composed of any two of image quality, resolution, and image area, the number of times of the hash function for each of the first key and the second key A setting means for setting a pair;
For each partial image data, a value obtained by executing the hash function according to the number of times corresponding to the number of times set for the partial image data in each of the first key and the second key. , Having key generation means for generating an individual key for the partial image data,
In the setting means, for the first key, the upper right cell in the matrix is the origin (0, 0), the x coordinate is incremented by 1 in the horizontal left direction, and the y coordinate is incremented by 1 in the vertical downward direction. As a set (x_ij, y_ij) of the number of times for a cell of coordinates (i, j) of a matrix whose size is Nx * Ny
if j = 0, x_ij = i,
If j ≠ 0, then x_ij = Nx + j-1 and
if i = 0, y_ij = j,
If j ≠ 0, set y_ij = Ny + i-1
For the second key, the upper right cell in the matrix is the origin (0, 0), and the coordinate axis is such that the x coordinate increases by 1 in the horizontal left direction and the y coordinate increases by 1 in the vertical downward direction. Define the set of times for the cell at coordinates (i ′, j ′) in the matrix of size (Nx−2) * (Ny−2) (u′_i′j ′, v′_i′j )), The set (u_ij, v_ij) of the number of times for the cell at coordinates (i, j) in the matrix of size Nx * Ny
If i = 0 and j = 0, then u_ij = 0 and v_ij = 0,
When i = Nx−1 or j = Ny−1, u_ij and v_ij are information indicating that the second key does not exist,
When i = 0 and j ≠ 0, u_ij = u′_i (j−1) and v_ij = v′_i (j−1)
When j = 0 and i ≠ 0, u_ij = u ′ _ (i−1) j and v_ij = v ′ _ (i−1) j,
Otherwise, set u_ij = u ′ _ (i−1) (j−1) and v_ij = v ′ _ (i−1) (j−1),
An information processing apparatus, wherein a set of the number of execution times of each cell in a matrix whose size is (Nx−2) * (Ny−2) is set with the same setting as the first key.   The program for making a computer implement | achieve the function of the information processing apparatus of Claim 3.

Images