Encryption key generation device

CROSS-REFERENCE TO RELATED APPLICATIONS

0001This application is a Continuation-In-Part of International Application No. PCT/JP2009/058400, filed Apr. 28, 2009, the disclosure of which application is incorporated by reference herein. This application is also a Continuation-In-Part of U.S. application Ser. No. 12/522,642, filed Nov. 4, 2008, which is the U.S. National Phase under 35 U.S.C. §371 of International Application No. PCT/JP2008/070037, filed on Nov. 4, 2008, which in turn claims the benefit of Japanese Application Nos. 2007-287756, filed on Nov. 5, 2007 and 2008-108115, filed on Apr. 17, 2008, the disclosures of which Applications are incorporated by reference herein.

BACKGROUND OF THE INVENTION

00021. Field of the Invention

0003The present invention relates to an apparatus and method of generating of an encryption key used in coding (encryption) and decoding (decryption) of digital data with plural types of hierarchical scalabilities and, more particularly, to an apparatus and method of automatically generating partial encryption keys corresponding to respective data units in hierarchies in each scalability.

00042. Related Background Art

0005In recent years, the spread of information and communications services through networks has also increased services to transmit data to unspecified masses, e.g., a delivery service of digital contents such as images (including one-frame data of a moving picture). In conjunction therewith, there is a demand for highly advanced functionality in protection technology of digital data.

0006In general, a coded digital image or the like is decoded in a quality (distortion, resolution, color representation, or the like) determined in a coding process. With diversification of communication channels, diversification of communication terminals, and diversification of delivery services, there is a demand for capability of decoding the image in a quality different from the quality determined in the coding process, by decoding a certain part of a codestream, i.e., scalability. For meeting this demand for scalability, for example, JPEG2000 (Joint Photographic Experts Group 2000) being the international standard of image compression provides hierarchized scalabilities with scales such as resolution. In the protection technology of hierarchically protecting data in different qualities, it is common practice to perform encryption using individual partial keys for respective data units located in respective hierarchies in each of scalabilities.

0007The known protection technologies of digital data as described above include, for example, those of Japanese Patent Application Laid-open No. 2004-312740 (Patent Document 1), Japanese Patent Application Laid-open No. 2003-204321 (Patent Document 2), Y. Wu, D. Ma, and R. H. Deng, “Progressive protection of JPEG 2000 condestreams.” In Proc. IEEE ICIP, pp. 3447-3450, 2004 (Non-patent Document 1), M. Fuhiyoshi, S, Imaizumi, and H. Kiya, “Encryption of composite multimedia contents for access control,” IEICE Trans. Fundamentals, Vol. E90-A, No. 3, pp. 590-596, March 2007 (Non-patent Document 2), and Shoko Imaizumi, Masaaki Fujiyoshi, Yoshito Abe, and Hitoshi Kiya, “Hierarchical encryption method of JPEG2000 for coded images with resistance to collusion attacks,” IEICE SIP symposium, 2006 (Non-patent Document 3).

0008Non-patent Document 1 discloses the technology of generating partial keys corresponding to data units in lower hierarchies from one master key by applying a one-way hash function to digital data with hierarchical scalabilities. Non-patent Document 2 discloses the technology independent of an order of streaming data, which is a problem of Non-patent Document 1. Furthermore, Non-patent Document 3 cited above discloses the technology of improving the resistance to collusion attacks, which is a problem of Non-patent Document 1.

0009A collusion attack is such an act that plural types of encryption keys corresponding to different hierarchical levels in respective scalabilities are shared among a plurality of users, so as to implement reproduction of the image in a quality higher than a preliminarily authorized quality.

SUMMARY OF THE INVENTION

0010The inventors thoroughly investigated the conventional data protection technologies and found the following problem. Namely, for hierarchically protecting digital data of different qualities, encryption keys are separately managed for respective types of scalabilities, or the encryption is carried out using individual encryption keys (partial keys) for respective data units located in respective hierarchies in each of scalabilities.

0011Particularly, in the case of managing individual partial keys generated for respective data units, an increase in the number of hierarchies leads to an increase in the number of keys to be managed, and a sufficient key length has to be ensured in order to maintain the resistance to collusion; therefore, the total key length will be considerably long with increase in hierarchies in each scalability.

0012On the contrary, in the case where partial keys corresponding to respective data units are generated from one master key, it is necessary to divide the master key by the number of partial keys, and, as in Non-patent Document 3, an increase in the number of partial keys will inevitably result in shortening the length of each partial key to be generated. In this case, the sufficient resistance to collusion cannot be ensured.

0013The present invention has been accomplished in order to solve the problem as discussed above, and an object of the present invention is to provide an encryption key generating apparatus and method having a structure which ensures sufficient resistance to collusion attacks on digital data with hierarchical scalabilities and achieves drastic reduction in the key length of encryption keys corresponding to respective hierarchies in each scalability.

0014An encryption key generating apparatus and method according to the present invention are applicable to a communication system offering a delivery service of digital data with plural types (≧2) of hierarchical scalabilities (hereinafter referred to as delivery system), and then generate an encryption key (a group of partial keys respectively corresponding to hierarchies at a higher position than the hierarchy of the master key) used in coding and decoding of the digital data, by setting, as a master key, a partial key of the hierarchy at the lowest position out of the hierarchies satisfying a pre-contracted service level. Specifically, the delivery system applied with the encryption key generating apparatus and method includes a communication system offering picture transmission systems and teleconference systems using multimedia such as packet codestreams of JPEG2000 being the international standard of image compression and also offering streaming delivery services. The encryption key generating apparatus according to the present invention can realize the encryption key generating method according to the present invention, and comprises input means, storage means, key dividing means, matrix generating means, key generating means, and output means. The encryption key generating apparatus and method generate partial keys of hierarchies at subordinately higher positions from a master key, as an encryption key to be used in coding and decoding of the digital data for delivery. Therefore, the encryption key generating apparatus enables simultaneous access control on a plurality of scalabilities by a single codestream.

0015Specifically, in an encryption key generating apparatus according to the present invention, the input means inputs a pre-set encryption key (partial key), and the storage means stores the partial key inputted by the input means, as a master key. This master key is a partial key at the lowest position out of hierarchies satisfying a service level allowed by the communication system (delivery system) offering a data delivery service, concerning each of the scalabilities. The key dividing means generates slit keys from stored in the storage means. Subsequently, the encryption key generating apparatus generates, as a minimum processing unit, partial keys respectively corresponding to the data units of the hierarchies in the two types of scalabilities selected. Namely, the matrix generating means generates key element matrices respectively corresponding to the split keys generated by the key dividing means. The key generating means generates partial keys each corresponding to hierarchies using the entry combining of the key element matrices. Further, the output means outputs the partial keys generated by the key generating means in the minimum processing unit, to a device executing at least one of coding and decoding of the digital data, for example coding means, decoding means, or the like. The key element matrices are generated based on the split keys corresponding to the respective hierarchies, on a hierarchy-by-hierarchy basis of one scalability. In each key element matrix, coordinates of each entry are defined by respective hierarchical values (corresponding to hierarchical levels) in the two types of scalabilities, whereby each matrix entry coordinately corresponds to a data unit in respective hierarchies in the two types of scalabilities. The encryption key generating apparatus is characterized by generating each of the partial keys in hierarchies at subordinately higher positions from the only managed master key. Therefore, partial keys in hierarchies at subordinately higher positions are also generated from a master key on a decryption occasion and, for example, in a multimedia delivery service, a user receives only a delivered decryption key for the lowest packet in a packet group authorized to open. In this case, the given decryption key itself serves as the master key in the encryption key generating method and each of hierarchies in respective scalabilities corresponding to this master key is the lowest hierarchy.

0016First, set as the master key stored in the storage means is an encryption key used in coding and decoding of a data unit in hierarchies at the lowest position out of hierarchies satisfying a service level allowed by the delivery system, in each of first and second scalabilities selected from the plural types of scalabilities which the digital data as a coded object has. On the contrary, when the master key is a decryption key obtained by delivery or the like, each of hierarchies in respective scalabilities corresponding to the master key is the lowest hierarchy. The key dividing means divides this master key by the number of hierarchies in the first scalability set as a reference scalability out of the first and second scalabilities, to generate split keys corresponding to the respective hierarchies of the first scalability.

0017Key element matrices, which are generated by the matrix generating means based on the respective split keys, coordinately correspond to data units in respective hierarchies in the first and second scalabilities. In generation of a key element matrix generated based on one split key out of the resultant split keys, at least coordinate entries corresponding to respective hierarchies from the lowest hierarchy to the highest hierarchy in the second scalability in the hierarchy in the first scalability corresponding to the one split key are assigned operation data successively obtained by repeating a hash operation on the one split key using a one-way hash function. This maintains the hierarchical nature of the second scalability.

0018Subsequently, the key generating means combines key elements coordinately consistent among the key element matrices generated with the respective split keys, thereby generating partial keys corresponding to data units in the respective hierarchies in the first and second scalabilities. Namely, the key generating means generates partial keys for coding or decoding each of the data units of higher hierarchies including the hierarchy of the master key. This configuration also maintains the hierarchical nature of the first scalability.

0019In the encryption key generating apparatus according to the present invention, the key generating means preferably selects, as the aforementioned reference scalability, a scalability having a smaller number of hierarchies out of the first and second scalabilities. This configuration is less likely to be affected by increase in the number of hierarchies in one or more scalabilities.

0020The matrix generating means assigns, as entry information of a key element matrix generated based on one split key out of the split keys, the same operation data as the operation data successively obtained for the hierarchy of the one split key, to coordinate entries corresponding to respective hierarchies from the lowest hierarchy to the highest hierarchy of the second scalability in a hierarchy at a lower position than the hierarchy in the first scalability corresponding to the one split key. On the other hand, the matrix generating means assigns operation data, obtained by a hash operation with a one-way hash function on a key element in the highest hierarchy of the second scalability out of key elements in the hierarchy corresponding to the one split key, to all coordinate entries corresponding to respective hierarchies from the lowest hierarchy to the highest hierarchy of the second scalability in a hierarchy at a higher position than the hierarchy in the first scalability corresponding to the one split key.

0021As described above, the encryption key generating apparatus and method according to the present invention are not restricted by progression orders of codestreams, different from the conventional encryption key generating methods required to prepare a plurality of codestreams and master keys according to progression orders. Furthermore, the encryption key generating apparatus and method according to the present invention generate the encryption keys (partial keys) corresponding to respective data units subordinately from the master key and enables simultaneous access control on a plurality of scalabilities by a single codestream. This achieves drastic reduction in information amount of the codestream and managed encryption key (master key) and enables effective improvement in safety in management and delivery of digital contents and the encryption key.

0022Furthermore, when the digital data as a coded target has three or more types of scalabilities, the encryption key generating apparatus and method according to the present invention select two types of scalabilities out of these three or more types of scalabilities, and partial keys (to be used in coding and decoding of the data unit corresponding to each partial key), which are individually correspond to the data units of the higher hierarchies including the hierarchy of the master key, are generated by executing the aforementioned minimum processing unit (key generating operation by the matrix generating means and the key generating means), for all combinations of two types of scalabilities selected out thereof.

0023Namely, the matrix generating means generates, with all the combinations of two types of scalabilities, a partial key element matrix for each combination. On this occasion, the matrix generating means also generates a hierarchy table as one showing all combinations of hierarchical values in the plural types of scalabilities. This hierarchy table is a coordinate representation of partial key matrices whose entries are partial keys corresponding to data units of respective hierarchical values in the plural types of scalabilities, by combinations of hierarchical values. This hierarchy table shows a correspondence relation between the types of scalabilities and the hierarchical values and entries of the partial key element matrices generated for all combinations of scalabilities can be specified from this relation.

0024Then the key generating means involves combining entries in the respective partial key element matrices generated for all the combinations of two types of scalabilities, each of which is specified by two hierarchical values out of hierarchical values constituting one combination and types of scalabilities thereof, for all the combinations of hierarchical values in the hierarchy table. An element resulting from this combining step for each combination of hierarchical values is an entry in a partial key element matrix as it is. Therefore, partial keys corresponding to data units in respective hierarchies in the plural types of scalabilities are sequentially generated by the key generating means combining entries made in correspondence by the hierarchy table from the respective partial key element matrices. The output means outputs the partial keys generated to a device executing at least one of coding and decoding of the digital data, for example coding means, decoding means, or the like.

0025In the generation of the encryption key used in coding and decoding of digital data with hierarchical scalabilities being three or more types of scalabilities, the resistance to collusion attacks can be further improved in comparison with the above-described encryption key generating apparatus and method.

0026Specifically, in each of three or more types of scalabilities, the input means inputs an encryption key used in coding and decoding of a data unit in hierarchies at the lowest position out of the hierarchies satisfying a service level allowed by the delivery system, and the storage means stores the encryption key inputted by the input means as the master key (in the case where the master key is a decryption key obtained by delivery or the like, each of hierarchies in the respective scalabilities corresponding to the master key is the lowest hierarchy). At this time, the key dividing means selects first and second reference scalabilities from the three or more types of scalabilities. The first reference scalability is a scalability for generation of split keys from the master key stored in the storage means, and the key dividing means generates the master key by the number of hierarchies in the first reference scalability, thereby generating split keys corresponding to the respective hierarchies in the first reference scalability. Here, the second reference scalability is a scalability for defining an operation direction of the hash operation with the one-way hash function as described above.

0027In the encryption key generating apparatus, the matrix generating means generates a multidimensional key element matrix as a coordinate representation of hierarchical values in the three or more types of scalabilities, by a series of operations corresponding to respective hierarchies in the first reference scalability, for each hierarchy in each of scalabilities other than the first and second reference scalabilities out of these three or more types of scalabilities. For that, let S be the number of scalabilities, and N_K(K=1, 2, 3, . . . , i−1, or i), specifically, N₁, N₂, . . . , N_i-1, or N_iin order from the smallest be the number of hierarchies in each scalability; for the total packet number given by Mathematical Expression (1) below, the number of multidimensional key element matrices generated in the encryption key generating method is given by Mathematical Expression (2) below.

0028<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mtable><mtr><mtd><mrow><munderover><mo>∏</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>S</mi></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>N</mi><mi>i</mi></msub></mrow></mtd><mtd><mrow><mo>(</mo><mn>1</mn><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mrow><munderover><mo>∏</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>S</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>N</mi><mi>i</mi></msub></mrow></mtd><mtd><mrow><mo>(</mo><mn>2</mn><mo>)</mo></mrow></mtd></mtr></mtable></math></maths><img file="US8634553B2_D0001.tif" />

0029Specifically, the matrix generating means assigns, as entry information in each of multidimensional key element matrices generated, operation data successively obtained by repeating a hash operation on the one split key using a one-way hash function, to at least coordinate entries corresponding to respective hierarchies from the lowest to the highest in the second reference scalability in a hierarchy in the first reference scalability corresponding to one split key out of the generated split keys. This maintains the hierarchical nature of at least the second reference scalability in the multidimensional key element matrix obtained.

0030Subsequently, the key generating means combines entries coordinately consistent among the respective multidimensional key element matrices generated by the series of operations corresponding to the respective hierarchies in the first reference scalability, for the respective hierarchies in each of the scalabilities other than the first and second reference scalabilities, so as to generate partial keys corresponding to data units in the respective hierarchies in the plural types of scalabilities. Namely, since the multidimensional key element matrices obtained are generated with the respective hierarchies of the first reference scalability, for each of hierarchies in each of the scalabilities other than the first and second reference scalabilities, the hierarchical nature of the first reference scalability is also maintained in a partial key matrix finally generated from the obtained multidimensional key element matrices.

0031Here, as entry information in each of the multidimensional key element matrices generated by the series of operations corresponding to the respective hierarchies in the first reference scalability, for the respective hierarchies in each of the scalabilities other than the first and second scalabilities, coordinate entries corresponding to respective hierarchies from the lowest to the highest of the second reference scalability in a hierarchy at a lower position than respective corresponding hierarchies of the other scalability and the first reference scalability are assigned the same operation data as the operation data successively obtained with one split key assigned to the corresponding hierarchy of the first reference scalability. On the other hand, all coordinate entries corresponding to respective hierarchies from the lowest to the highest of the second reference scalability in a hierarchy at a higher position than the respective corresponding hierarchies of the other scalability and the first reference scalability are assigned operation data obtained by a hash operation with a one-way hash function on a key element in the highest hierarchy in the second reference scalability out of key elements in the hierarchy corresponding to the one split key.

0032The output means outputs the partial keys generated by the key generating means in the foregoing minimum processing unit, to a device executing at least one of coding and decoding of the digital data, for example coding means, decoding means, or the like.

0033Each of embodiments according to the present invention will become further fully understood by the following detailed description and accompanying drawings. These embodiments are presented by way of illustration only and should not be construed as limiting the present invention.

0034A further application range of this invention will become apparent from the following detailed description. It should be, however, noted that the detailed description and specific examples will be presented to explain preferred embodiments of the present invention by way of illustration only, and it is apparent that a variety of modifications and improvements within the scope of the invention are obvious to those skilled in the art in view of the detailed description.

BRIEF DESCRIPTION OF THE DRAWINGS

0035<figref idref="DRAWINGS">FIG. 1</figref> is a drawing showing the schematic structure of a delivery system for digital data applied with an encryption key generating apparatus and method according to the present invention;

0036<figref idref="DRAWINGS">FIGS. 2A and 2B</figref> show a structure of each part in an information processing apparatus (delivery server or PC) constituting a part of the delivery system shown in <figref idref="DRAWINGS">FIG. 1</figref>;

0037<figref idref="DRAWINGS">FIG. 3</figref> is a conceptual diagram for explaining a data structure of digital data which becomes a delivered target in the delivery system shown in <figref idref="DRAWINGS">FIG. 1</figref> and has plural types of hierarchical scalabilities;

0038<figref idref="DRAWINGS">FIGS. 4A and 4B</figref> show a conceptual diagram for explaining progressive orders;

0039<figref idref="DRAWINGS">FIGS. 5A and 5B</figref> show matrix representations of data units (corresponding to respective packages of JPEG2000) of digital data with two types of three-layered scalabilities, and partial keys corresponding thereto;

0040<figref idref="DRAWINGS">FIG. 6</figref> is a logical block diagram for explaining data delivery operation in the delivery system (<figref idref="DRAWINGS">FIG. 1</figref>) of the digital data applied with the encryption key generating apparatus according to the present invention;

0041<figref idref="DRAWINGS">FIG. 7</figref> is a logical block diagram for explaining a structure of the encryption key generating apparatus according to the present invention;

0042<figref idref="DRAWINGS">FIG. 8</figref> is a conceptual diagram for explaining an encryption generating operation (encryption key generating method according to the first embodiment) executed in a first embodiment of the encryption key generating apparatus according to the present invention;

0043<figref idref="DRAWINGS">FIG. 9</figref> is a conceptual diagram for explaining generation of key element matrices by the matrix generating means in the encryption key generating apparatus according to the first embodiment;

0044<figref idref="DRAWINGS">FIG. 10</figref> is a conceptual diagram for explaining an encryption generating operation (encryption key generating method according to the second embodiment) executed in a second embodiment of the encryption key generating apparatus according to the present invention;

0045<figref idref="DRAWINGS">FIG. 11</figref> is a conceptual diagram for explaining generation of key element matrices by the matrix generating means in the encryption key generating apparatus according to the second embodiment;

0046<figref idref="DRAWINGS">FIG. 12</figref> is a conceptual diagram for explaining an encryption generating operation (encryption key generating method according to the third embodiment) executed in a third embodiment of the encryption key generating apparatus according to the present invention;

0047<figref idref="DRAWINGS">FIG. 13</figref> is a conceptual diagram for explaining generation of key element matrices by the matrix generating means in the encryption key generating apparatus according to the third embodiment;

0048<figref idref="DRAWINGS">FIG. 14</figref> is a conceptual diagram for explaining generation of partial keys for digital data with three or more types of hierarchical scalabilities, as an encryption generating operation (encryption key generating method according to the fourth embodiment) executed in a fourth embodiment of the encryption key generating apparatus according to the present invention;

0049<figref idref="DRAWINGS">FIG. 15</figref> is a drawing showing generation of a hierarchy table by the matrix generating means of the encryption key generating apparatus according to the fourth embodiment, and a coordinate correspondence relation between partial key element matrices and a partial key matrix;

0050<figref idref="DRAWINGS">FIGS. 16A and 16B</figref> show drawings for explaining an element correspondence relation between partial key element matrices and a partial key matrix in generation of partial keys that are generated by the matrix generating means of the encryption key generating apparatus according to the fourth embodiment;

0051<figref idref="DRAWINGS">FIGS. 17A and 17B</figref> show drawings for explaining a three-dimensional matrix as an example of stereoscopic indication of coordinate entry arrangement in a multidimensional partial key matrix and a multidimensional key element matrix, and an assigning operation of split keys in the encryption key generation (<figref idref="DRAWINGS">FIG. 14</figref>) generalized from the encryption key generating operation executed by the fourth embodiment;

0052<figref idref="DRAWINGS">FIGS. 18A to 18D</figref> show drawings for explaining key element generating steps corresponding to respective hierarchies of scalabilities L and R, using three-dimensional matrices of stereoscopic indications, in the encryption key generation generalized from the encryption key generating operation executed by the fourth embodiment;

0053<figref idref="DRAWINGS">FIGS. 19A to 19D</figref> show drawings for explaining key element generating steps corresponding to respective hierarchies of scalabilities R and C, using three-dimensional matrices of stereoscopic indications, in the encryption key generation generalized from the encryption key generating operation executed by the fourth embodiment;

0054<figref idref="DRAWINGS">FIGS. 20A to 20C</figref> show drawings for explaining key element generating steps corresponding to respective hierarchies of scalabilities L and C, using three-dimensional matrices of stereoscopic indications, in the encryption key generation generalized from the encryption key generating operation executed by the fourth embodiment;

0055<figref idref="DRAWINGS">FIG. 21</figref> is a drawing for explaining an example of operation of the key generating means generating split keys from a master key, in the encryption key generating operation (encryption key generating method according to the fifth embodiment) executed in a fifth embodiment of the encryption key generating apparatus according to the present invention;

0056<figref idref="DRAWINGS">FIGS. 22A to 22D</figref> show drawings for explaining generation steps of multidimensional key element matrices by the matrix generating means in the encryption key generating apparatus according to the fifth embodiment (generation of a multidimensional key element matrix group corresponding to the lowest hierarchy of scalability C other than reference scalabilities L and R);

0057<figref idref="DRAWINGS">FIGS. 23A to 23D</figref> show drawings for explaining generation steps of multidimensional key element matrices by the matrix generating means in the encryption key generating apparatus according to the fifth embodiment (generation of a multidimensional key element matrix group corresponding to a hierarchy higher by one hierarchy than the lowest hierarchy of scalability C other than reference scalabilities L and R); and

0058<figref idref="DRAWINGS">FIGS. 24A to 24D</figref> show drawings for explaining generation steps of multidimensional key element matrices by the matrix generating means in the encryption key generating apparatus according to the fifth embodiment (generation of a multidimensional key element matrix group corresponding to the highest hierarchy of scalability C other than reference scalabilities L and R).

DESCRIPTION OF THE PREFERRED EMBODIMENTS

0059In the following, embodiments of an encryption key generating apparatus and method according to the present invention will be described below in detail with reference to <figref idref="DRAWINGS">FIGS. 1</figref>, <b>2</b>A, <b>2</b>B, <b>3</b>, <b>4</b>A to <b>5</b>B, <b>6</b> to <b>15</b>, <b>16</b>A to <b>20</b>C, <b>21</b>, and <b>22</b>A to <b>24</b>D. In the description of the drawings the same portions and the same elements will be denoted by the same reference symbols, without redundant description.

0060The encryption key generating apparatus and method according to the present invention are to generate an encryption key used in coding and decoding of digital data with plural types of hierarchical scalabilities. Each of the embodiments will be described using a specific example of digital data with hierarchical scalabilities, as to generation of partial keys corresponding to respective packet codestreams of JPEG2000 being the international standard of image compression, for simplicity. JPEG2000 allows an order of priorities to be given to types of scalabilities. This order in a codestream is expressed as a construction order (progression order) of packets being data units. Elements to determine this progression order include four types of scalabilities, layer (L), resolution level (R), component (C), and position (P).

0061<figref idref="DRAWINGS">FIG. 1</figref> is a drawing showing the schematic structure of a delivery system for digital data applied with an encryption key generating apparatus and method according to the present invention. The delivery system shown in <figref idref="DRAWINGS">FIG. 1</figref> includes a communication system offering picture transmission systems and teleconference systems which offers a delivery service for digital data having a hierarchical scalability and also offering a streaming delivery service. Also, this delivery system comprises a network <b>300</b> without regard to wired or wireless, plural information processing terminals <b>200</b> (hereinafter referred to as PC) such as for example personal computer respectively connected to the network <b>300</b>, and a delivery server <b>100</b>, and the PCs <b>200</b> and the delivery server <b>100</b> are enable to execute an interactive communication for multimedia including digital data through the network <b>300</b>. The delivery server <b>100</b> manages a database (hereinafter referred to as D/B) <b>110</b>, as an external storage device, in which plural kinds of digital data contents are preliminarily stored for a delivery service. Between each of the PCs <b>200</b> and the delivery server <b>100</b>, a contract regarding a delivery service for digital data is preliminarily is closed, and the delivery server <b>100</b> deliveries digital data with a quality of preliminarily contracted level, when receiving a request for delivery fro the PC <b>200</b>.

0062The structure of an information processing apparatus such as the delivery server <b>100</b>, the PCs <b>200</b> and the like, which constitute a part of the above0described delivery system, is shown in <figref idref="DRAWINGS">FIGS. 2A and 2B</figref>. In particular, <figref idref="DRAWINGS">FIG. 2A</figref> shows a structure of the delivery server <b>100</b> or the PC <b>200</b>, and <figref idref="DRAWINGS">FIG. 2B</figref> shows a logical structure of the D/B <b>110</b> managed by the delivery server <b>100</b>.

0063Namely, As shown in <figref idref="DRAWINGS">FIG. 2A</figref>, the delivery server <b>100</b> or the PC <b>200</b> comprises an input/output means (hereinafter referred to as I/O) <b>210</b> for transmitting and receiving data to another information processing apparatus through the network <b>300</b>, a controller <b>220</b> executing plural operation programs <b>231</b>, a memory <b>230</b> as storage means in which such operation programs and data are stored, and an input/output means (hereinafter referred to as I/O) <b>240</b> for allowing data communication to plural peripheral devices. On the monitor <b>251</b>, data for display, produced by the drawer <b>250</b>, is displayed. To the I/O <b>240</b>, the external storage device <b>270</b> such as D/B <b>110</b> to be managed by the delivery server <b>100</b>, the key board <b>260</b> and the pointing device as input means.

0064In the D/B <b>110</b> as an external storage device managed by the delivery server <b>100</b>, a contract information table <b>110</b><i>a</i>, key management table <b>110</b><i>b </i>and digital data groups <b>110</b><i>c </i>for delivery are preliminarily stored. The contract information table <b>110</b><i>a </i>homologizes users (contractors) as an operator of PC <b>200</b> and service levels reflecting contract. The key management table <b>110</b><i>b </i>homologizes digital data (plural digital contents for delivery) stored in D/B <b>110</b> and partial keys (master keys) for coding these digital contents, every each user (contractor).

0065<figref idref="DRAWINGS">FIG. 3</figref> is a conceptual diagram for explaining a data structure of digital data which becomes a delivered target in the delivery system shown in <figref idref="DRAWINGS">FIG. 1</figref> and has plural types of hierarchical scalabilities. Further <figref idref="DRAWINGS">FIG. 3</figref> shows a decoding pattern of packet codestreams in JPEG2000 when scalabilities as access control targets out of the scalabilities of JPEG2000 are limited to only the layer (L) and the resolution level (R) (a case of a grayscale picture). Specifically, in <figref idref="DRAWINGS">FIG. 1</figref>, the number of hierarchies N_Lin the layer (scalability L) is 3 and the number of hierarchies N_Rin the resolution level (scalability R) is 3. The layer is also called a quality layer and means arithmetic code data of a digital image corresponding to SNR (Signal/Noise Ratio) in reproduction of image. Since a higher layer contains information with greater effect on the image quality, the quality of a reproduced image can be improved stepwise by successively adding data of a lower layer to data of a higher layer.

0066In this <figref idref="DRAWINGS">FIG. 3</figref>, P_i,j(i=0, . . . , N_L−1; j=0, . . . , N_R−1; i a hierarchy number of scalability L; j a hierarchy number of scalability) represents JPEG2000 packets with image information. When Q_L,Rrepresents a JPEG2000 coded image with a certain quality, all packets P_i,j(i=0, . . . , L; j=0, . . . , R) within frame A in <figref idref="DRAWINGS">FIG. 1</figref> have to be decoded in order to obtain Q_L,R. For normally reproducing the image, all the packets P_i,jto be decoded must be decrypted. Therefore, it is necessary to individually encrypt the packets P_i,jin order to maintain the hierarchical nature in access control.

0067In JPEG2000 as described above, there are five types of progression orders, LRCP, RLCP, RPCL, PCRL, and CPRL, and priorities are given to respective elements in descending order from the top. <figref idref="DRAWINGS">FIGS. 4A and 4B</figref> are conceptual diagrams for explaining progressive orders showing priority orders in decoding the JPEG2000 packet codestreams shown in <figref idref="DRAWINGS">FIG. 3</figref>. Particularly, <figref idref="DRAWINGS">FIG. 4A</figref> shows a decoding order in the LRCP progression order with the highest priority to scalability L (layer), and <figref idref="DRAWINGS">FIG. 4B</figref> shows a decoding order in the RLCP progression order with the highest priority to scalability R (resolution level).

0068The encryption key generating apparatus and method according to the present invention generate an encryption key of which the key length is reduced in terms of safety and easy production in management and delivery of the encryption key, and which has the resistance to collusion attacks. Since the encryption key generating apparatus and method handle each packet as a matrix entry specified by hierarchical levels of respective scalabilities in order to generate encryption keys for the respective JPEG2000 packets as described above, the progression orders in JPEG2000 do not matter. As an example, <figref idref="DRAWINGS">FIG. 5A</figref> shows packets P_L,R(L:0 (highest), 1, 2 (lowest); R:0 (highest), 1, 2 (lowest)) in a matrix representation with hierarchical levels of scalability L (layer) and hierarchical levels of scalability R (resolution level). <figref idref="DRAWINGS">FIG. 5B</figref> shows partial keys K_L,R(L:0, 1, 2; R:0, 1, 2) in a matrix representation corresponding to the packets P_L,Rin <figref idref="DRAWINGS">FIG. 5A</figref>.

0069A collusion attack herein is such an attack that two or more users illegally share their encryption keys, so as to enable reproduction of an image in a quality higher than a regularly authorized quality. Specifically, let us consider a collusion case using an example of a JPEG2000 coded image, in which a collusion is made by a user authorized to open only the highest layer (layer 0) and a user authorized to open only the highest resolution level (resolution level 0). In this case, when K_i,jrepresents an encryption key for packet P_i,j, one user receives encryption keys K_0,j(j=0, 1, 2) for three packets P_0,j(j=0, 1, 2) and the other user receives encryption keys K_j,0(i=0, 1, 2) for three packets P_i,0(i=0, 1, 2), as regularly authorized keys. If the resistance is not enough to collusion attacks, these users could collude and illegally generate encryption keys K_2,2, K_2,0, K_0,2, and K_1,1which are not authorized for the two users. In the encryption key generating operation (encryption key generating method according to the present invention) executed in the encryption key generating apparatus according to the present invention, as described in each of the embodiments below, an encryption key (partial key) for a certain packet cannot be generated from a packet in a hierarchy at a higher position in at least one scalability than that of the packet of interest, and can be generated from a packet in a hierarchy at an identical or lower position in each scalability. For this reason, the encryption key generating apparatus and method according to the present invention have the resistance to collusion attacks.

0070Next, a data delivery operation in the delivery system for digital data shown in <figref idref="DRAWINGS">FIG. 1</figref> will be described using <figref idref="DRAWINGS">FIG. 6</figref>. <figref idref="DRAWINGS">FIG. 6</figref> is a logical block diagram for explaining data delivery operation in the delivery system (<figref idref="DRAWINGS">FIG. 1</figref>) of the digital data applied with the encryption key generating apparatus according to the present invention. The delivery server <b>100</b> and each PC <b>200</b> have the same structure shown in <figref idref="DRAWINGS">FIG. 2A</figref>.

0071As shown in <figref idref="DRAWINGS">FIG. 6</figref>, the delivery service from the delivery server <b>100</b> to the PC <b>200</b> starts by the PC <b>200</b> sending a delivery request to the delivery server <b>100</b>. As receiving the delivery request from the PC <b>200</b>, a request analysis executed in the delivery server <b>100</b>. In this request analysis, an authentication proceeding for user having sent a delivery request, specification of data to be delivered, and specification of service level are executed.

0072In the delivery server <b>100</b>, after the request analysis, data that a delivery is requested is read-out from the D/B <b>110</b>, and a master key corresponding to the read-out data is also read-out, the master key being a partial key for generating encryption key using a coding of the read-out data. The encryption key generation apparatus <b>400</b> (encryption key generation apparatus according to the present invention) inputs the master key, and generates partial keys (partial keys respectively corresponding to higher hierarchies at higher positions than the hierarchy corresponding to the master key) using such a master key. Such generated partial keys are outputted from the encryption key generation apparatus <b>400</b> to the coding means <b>410</b>. On the other hand, the coding means <b>410</b> inputs data read-out from the D/B <b>110</b>, and generates coded data (a codestream of packet group to be delivered) by coding each of packets constituting the read-out data using such partial keys. Then, the delivery server <b>100</b> delivers coded data generated to the PC <b>200</b> (delivery requestor) together with the master key for generating partial keys to be used in a coding process, through the network <b>300</b>. The concrete data coding is executed by the controller <b>220</b> (<figref idref="DRAWINGS">FIG. 2A</figref>) in the delivery server <b>100</b>. Namely, the controller <b>220</b> functions as coding means <b>410</b> by executing the program <b>231</b> preliminarily stored in the memory <b>230</b>.

0073In the PC <b>200</b>, the coded data and master key, delivered through the network <b>300</b>, are taken in by the I/O <b>210</b> and stored in the memory <b>230</b>. The encryption key generation apparatus <b>400</b> (encryption key generation apparatus according to the present invention) in the PC <b>200</b> inputs the master key stored in the memory <b>230</b>, and generates partial keys for decoding (partial keys respectively corresponding to higher hierarchies at higher positions than the hierarchy corresponding to the master key) using this master key. Also, the encryption key generation apparatus <b>400</b> outputs these decryption keys generated to the decoding means <b>420</b>. The decoding means <b>420</b> inputs the coded data read-out from the memory <b>230</b>, and generates decoded data by decoding each of coded packets using a corresponding decryption key of the decryption keys outputted from the encryption key generation apparatus <b>400</b>. The concrete data decoding is executed by the controller <b>220</b> (<figref idref="DRAWINGS">FIG. 2A</figref>) in the PC <b>200</b>. Namely, the controller <b>220</b> functions as decoding means <b>420</b> by executing the program <b>231</b> preliminarily stored in the memory <b>230</b>.

0074the encryption key generation apparatus according to the present invention corresponds to the encryption key generation apparatus <b>400</b> in <figref idref="DRAWINGS">FIG. 6</figref> when being applied to the delivery system of <figref idref="DRAWINGS">FIG. 1</figref>, and concretely comprises the structure shown in <figref idref="DRAWINGS">FIG. 7</figref>. <figref idref="DRAWINGS">FIG. 7</figref> is a logical block diagram for explaining a structure of the encryption key generating apparatus according to the present invention.

0075Namely, the encryption key generation apparatus <b>400</b>, as shown in <figref idref="DRAWINGS">FIG. 7</figref>, comprises input means <b>450</b> for taking in the master key, operating means <b>460</b> for partial keys using the master key, storage means <b>470</b> for temporarily storing the master key and the operation results in the operating means <b>460</b>, and output means <b>480</b> for outputting, out of the partial keys generated, the partial key of the hierarchy corresponding to the contracted service level to the coding means <b>410</b> and the decoding means <b>420</b>. The operating means <b>460</b> is constituted by the key dividing means <b>461</b>, the matrix generating means <b>461</b>, and the key generating means <b>463</b>.

0076As applying the above-mentioned logical configuration to the hardware configuration, the I/O <b>210</b> functions as the input means <b>450</b> and the output means <b>480</b>. The memory <b>230</b> functions as the storage means <b>470</b>. The controller <b>220</b> functions as the operating means <b>460</b>. By executing the program <b>231</b> preliminarily stored in the memory <b>230</b>, the controller <b>220</b> functions as the key dividing means <b>461</b>, the matrix generating means <b>462</b>, and the key generating means <b>463</b>.

First Embodiment

0077The encryption key generating operation (encryption key generating method according to the first embodiment) executed in the first embodiment of the encryption key generating apparatus according to the present invention will be described below. The encryption key generating apparatus according to the first embodiment has the structure shown in <figref idref="DRAWINGS">FIG. 7</figref>, and is realized with a hardware configuration concretely shown in <figref idref="DRAWINGS">FIG. 2A</figref>. In this first embodiment, scalabilities as access control targets are scalability L (layer) and scalability R (resolution level), the number of hierarchies N_Lin scalability L is 3, and the number of hierarchies N_Rin scalability R is 3. At this time, packets in the respective hierarchies in scalabilities L and R are handled as 3×3 matrix entries P_i,j(i=0, 1, 2; j=0, 1, 2). <figref idref="DRAWINGS">FIG. 8</figref> is a conceptual diagram for explaining an encryption generating operation (operation of the operating means <b>460</b>) executed in the first embodiment of the encryption key generating apparatus according to the present invention. <figref idref="DRAWINGS">FIG. 9</figref> is a conceptual diagram for explaining generation of key element matrices by the matrix generating means <b>462</b> in the encryption key generating method of the first embodiment.

0078A master key is a partial key being in the D/B <b>110</b> by the input means <b>450</b> or delivered through the network <b>300</b>, and is stored in the storage means <b>470</b>. Namely, the master key is a partial key corresponding to the lowest packet preliminarily managed by the storage means <b>470</b> and in the example of <figref idref="DRAWINGS">FIG. 8</figref>, the master key is a partial key K_2,2corresponding to the packet P_2,2in the hierarchies at the lowest position in each of scalabilities L and R. The key dividing means <b>461</b> divides this master key K_2,2is divided by a smaller value (=min(N_L,N_R)) out of the hierarchy number N_Lof scalability L and the hierarchy number N_Rof scalability R.

0079Since in this first embodiment N_L=N_R=3, either of scalabilities L and R can be selected, and it is assumed as an example herein that the key dividing means <b>461</b> selects scalability R as a reference scalability. At this time, the key dividing means <b>461</b> divides the master key K_2,2by the minimum hierarchy number 3 (the number of hierarchies in scalability R) to obtain split keys e_R2, e_R1, and e_R0. These split keys e_R2, e_R1, and e_R0are root keys (keys for generation of respective matrix entries) corresponding to the respective hierarchies of scalability R, and the matrix generating means <b>462</b> generates key element matrices M<b>1</b>-M<b>3</b> for the respective hierarchies of scalability R.

0080Matrix entries in the respective key element matrices M<b>1</b>-M<b>3</b> are sequentially generated from the split keys e_R2, e_R1, and e_R0being the corresponding root keys, as shown in <figref idref="DRAWINGS">FIG. 9</figref>.

0081First, in the key element matrix M<b>1</b>, as a matrix corresponding to the hierarchical level 2 (lowest hierarchy) of scalability R, the split key e_R2is assigned to the (2,2) entry. In the drawing, superscript R2 to each matrix entry e represents the hierarchical level of scalability R (reference scalability) corresponding to the key element matrix M<b>1</b> and each subscript represents coordinates of an entry in the key element matrix M<b>1</b>. In this first embodiment, the entries in the key element matrix M<b>1</b> will be denoted below by e^R2(i,j) (i=0, 1, 2; j=0, 1, 2).

0082Coordinate entries e^R2(1,2) and e^R2(0,2) corresponding to the respective remaining hierarchies in scalability L in the hierarchy (hierarchical level=2) in scalability R corresponding to the split key e_R2are assigned operation data successively obtained by repeating a hash operation on the split key e_R2using a one-way hash function H*. Namely, e^R2(1,2) is assigned the operation data of H*(e^R2(2,2)) and the entry e^R2(0,2) is assigned the operation data of H*²(e^R2(2,2)). This matrix operation procedure maintains the hierarchical nature of scalability L, for the hierarchical level 2 of scalability R. In this specification, the operation of n (n=2, 3, . . . ) repetitions with one-way hash function H* is denoted by H*ⁿ.

0083On the other hand, in the key element matrix M<b>1</b>, all the entries e^R2(i,j) (i=0, 1, 2; j=0, 1) in the higher hierarchies than the hierarchical level 2 of scalability R are assigned operation data H*(e^R2(0,2))(=H*³(e^R2(2,2))) obtained by further carrying out the hash operation with the one-way hash function H* on the entry e^R2(0,2). The operation data at this time is a value corresponding to a packet with the hierarchy number of scalability L being −1 (which is nonexistent in fact).

0084The key element matrix M<b>1</b> generated as described above enables the access control to the packets P_i,2(i=0, 1, 2), while maintaining the hierarchical nature of scalability L.

0085In the key element matrix M<b>2</b>, as a matrix corresponding to the hierarchical level 1 of scalability R, the split key e_R1is assigned to the (2,1) entry. In this first embodiment, the entries in the key element matrix M<b>2</b> will be denoted below by e^R1(i,j) (i=0, 1, 2; j=0, 1, 2).

0086Operation data of H*(e^R1(2,1)) is assigned to the coordinate entry e^R1(1,1) and operation data of H*²(e^R1(2,1)) to the entry e^R1(0,1) corresponding to the respective remaining hierarchies in scalability L in the hierarchy (hierarchical level=1) in scalability R corresponding to the split key e_R1. This matrix operation procedure maintains the hierarchical nature of scalability L, for the hierarchical level 1 of scalability R.

0087Furthermore, in the key element matrix M<b>2</b>, all the entries e^R1(i,0) (i=0, 1, 2) in the higher hierarchy than the hierarchical level 1 of scalability R are assigned operation data H*(e^R1(0,1))(=H*³(e^R1(2,1))) obtained by further carrying out the hash operation with the one-way hash function H* on the entry e^R1(0,1). The operation data at this time is a value corresponding to a packet with the hierarchy number of scalability L being −1 (which is nonexistent in fact).

0088On the other hand, in the key element matrix M<b>2</b>, the entries e^R1(i,2) (i=0, 1, 2) in the lower hierarchy than the hierarchical level 1 of scalability R are assigned the same values as the corresponding entries e^R1(i,1) (i=0, 1, 2). It is synonymous with the following: the entries e^R1(i,2) (i=0, 1) are assigned values obtained by successively carrying out the hash operation with the one-way hash function on the entry e^R1(2,2) in which the value of entry e^R1(2,1) is copied once. In <figref idref="DRAWINGS">FIG. 9</figref> and others, “CP” means copy.

0089The key element matrix M<b>2</b> generated as described above enables the access control to the packets P_i,1(i=0, 1, 2), while maintaining the hierarchical nature of scalability L.

0090Similarly, in the key element matrix M<b>3</b>, as a matrix corresponding to the hierarchical level 0 (highest hierarchy) of scalability R, the split key e_R0is assigned to the (2,0) entry. In this first embodiment, the entries in the key element matrices M<b>3</b> will be denoted below by e^R0(i,j) (i=0, 1, 2; j=0, 1, 2).

0091Operation data of H*(e^R0(2,0)) is assigned to the coordinate entry e^R0(1,0) and operation data of H*²(e^R0(2,0)) is assigned to the entry e^R0(0,0) corresponding to the respective remaining hierarchies in scalability L in the hierarchy (hierarchical level=0) in scalability R corresponding to the split key e_R0. This matrix operation procedure maintains the hierarchical nature of scalability L, for the hierarchical level 0 of scalability R.

0092Furthermore, since there is no higher hierarchy than the hierarchical level 0 of scalability R in the key element matrix M<b>3</b>, no further hash operation is carried out on the entry e^R0(0,0).

0093On the other hand, in the key element matrix M<b>3</b>, the entries e^R0(i,j) (i=0, 1, 2; j=1, 2) in the lower hierarchies than the hierarchical level 0 of scalability R are assigned the same values as the corresponding entries e^R0(i,0) (i=0, 1, 2). This is synonymous with the following: the entries e^R0(i,j) (i=0, 1, 2; j=1, 2) are assigned the values obtained by successively carrying out the hash operation with the one-way hash function on each of the entries e^R0(2,2) and e^R0(2,1) in which the value of the entry e^R0(2,0) is copied once.

0094In this case, the key element matrix M<b>3</b> generated also enables the access control to the packets P_i,0(i=0, 1, 2), while maintaining the hierarchical nature of scalability L.

0095Subsequently, the key generating means <b>463</b> generates a partial key matrix MP<b>1</b> by combining the entries coordinately consistent among the key element matrices M<b>1</b>-M<b>3</b> generated by the matrix generating means <b>462</b> as described above. Namely, entries in the partial key matrix MP<b>1</b> serve as partial keys K_i,j(i=0, 1, 2; j=0, 1, 2) corresponding to the respective packets P_i,j(i=0, 1, 2; j=0, 1, 2). As described above, for each of the hierarchies of one scalability R (resolution level), the partial keys are generated while maintaining the hierarchical nature of the other scalability L (layer), whereby the hierarchical nature is maintained in the layer and in the resolution level. The output means <b>480</b> outputs the partial keys (i=0, 1, 2; j=0, 1, 2) generated by the key generating means <b>463</b> as described above, to the coding means <b>410</b>. The coding means <b>410</b> codes the packets P_i,j(i=0, 1, 2; j=0, 1, 2) by the respective corresponding partial keys K_i,j(i=0, 1, 2; j=0, 1, 2). In this manner, as coded data to be delivered through the network <b>300</b>, the JPEG2000 packet codestreams thus encrypted are delivered to the PC <b>200</b> together with the master key K_2,2.

Second Embodiment

0096The encryption key generating operation (encryption key generating method according to the second embodiment) executed in the second embodiment of the encryption key generating apparatus according to the present invention will be described below. The encryption key generating apparatus according to the second embodiment, similar to the first embodiment, has the structure shown in <figref idref="DRAWINGS">FIG. 7</figref>, and is realized with a hardware configuration concretely shown in <figref idref="DRAWINGS">FIG. 2A</figref>. In this second embodiment, scalabilities as access control targets are scalability L (layer) and scalability R (resolution level), the number of hierarchies N_Lin scalability L is 3, and the number of hierarchies N_Rin scalability R is 2. At this time, packets in respective hierarchies in scalabilities L and R are handled as 3×2 matrix entries P_i,j(i=0, 1, 2; j=0, 1). <figref idref="DRAWINGS">FIG. 10</figref> is a conceptual diagram for explaining the encryption key generating operation (operation of the operating means <b>460</b> shown in <figref idref="DRAWINGS">FIG. 7</figref>) executed in the second embodiment of the encryption key generating apparatus according to the present invention. <figref idref="DRAWINGS">FIG. 11</figref> is a conceptual diagram for explaining generation of key element matrices by the matrix generating means <b>462</b> in the encryption key generating apparatus according to the second embodiment.

0097The master key is a partial key delivered by the input means <b>450</b> through the D/B <b>110</b> or the network <b>300</b>, and is stored temporarily stored in the storage means <b>470</b>. Namely, the master key is a partial key corresponding to the lowest packet preliminarily managed by the storage means <b>470</b> and in the example of <figref idref="DRAWINGS">FIG. 10</figref>, it is an encryption key K_2,1corresponding to the packet P_2,1in the hierarchies at the lowest position in each of scalabilities L and R. This master key K_2,1is, by the key dividing means <b>461</b>, divided by a smaller value (=min(N_L,N_R)) out of the hierarchy number N_Lof scalability L and the hierarchy number N_Rof scalability R. Specifically, the key dividing means <b>461</b> divides the master key K_2,1by the hierarchy number of scalability R (minimum hierarchy number 2) to obtain split keys e_R1and e_R0. These split keys e_R1, e_R0are root keys corresponding to the respective hierarchies of scalability R and the matrix generating means <b>462</b> generates key element matrices M<b>1</b>, M<b>2</b> for the respective hierarchies of scalability R.

0098Matrix entries in the respective key element matrices M<b>1</b>, M<b>2</b> are sequentially generated from the split keys e_R1, e_R0being the corresponding root keys, as shown in <figref idref="DRAWINGS">FIG. 11</figref>.

0099First, in the key element matrix M<b>1</b>, as a matrix corresponding to the hierarchical level 1 (lowest hierarchy) of scalability R, the split key e_R1is assigned to the (2,1) entry. In the drawing, superscript R1 to each matrix entry e represents the hierarchical level of scalability R (reference scalability) corresponding to the key element matrix M<b>1</b>, and each subscript represents coordinates of an entry in the key element matrix M<b>1</b>. In this second embodiment, the entries in the key element matrix M<b>1</b> will be denoted below by e^R1(i,j) (i=0, 1, 2; j=0, 1).

0100Coordinate entries e^R1(1,1) and e^R2(0,1) corresponding to the respective remaining hierarchies in scalability L in the hierarchy (hierarchical level=1) in scalability R corresponding to the split key e_R1are assigned operation data successively obtained by repeating the hash operation on the split key e_R1using the one-way hash function H*. Namely, e^R1(1,1) is assigned the operation data of H*(e^R1(2,1)) and the entry e^R1(0,1) is assigned the operation data of H*²(e^R1(2,1)) This matrix operation procedure maintains the hierarchical nature of scalability L, for the hierarchical level 1 of scalability R.

0101On the other hand, in the key element matrix M<b>1</b>, all the entries e^R1(i,0) (i=0, 1, 2) in the higher hierarchy than the hierarchical level 1 of scalability R are assigned the operation data H*(e^R1(0,1))(=H*³(e^R1(2,1))) obtained by further carrying out the hash operation with the one-way hash function H* on the entry e^R1(0,1). The operation data at this time is a value corresponding to a packet with the hierarchy number of scalability L being −1 (which is nonexistent in fact).

0102The key element matrix M<b>1</b> generated as described above enables the access control to the packets P_i,1(i=0, 1, 2), while maintaining the hierarchical nature of scalability L.

0103In the key element matrix M<b>2</b>, as a matrix corresponding to the hierarchical level 0 (highest hierarchy) of scalability R, the split key e_R0is assigned to the (2,0) entry. In this second embodiment, the entries in the key element matrix M<b>2</b> will be denoted below by e^R0(i,j) (i=0, 1, 2; j=0, 1).

0104The operation data of H*(e^R0(2,0)) is assigned to the coordinate entry e^R0(1,0) and the operation data of H*²(e^R0(2,0)) is assigned to the entry e^R0(0,0) corresponding to the respective remaining hierarchies in scalability L in the hierarchy (hierarchical level=0) in scalability R corresponding to the split key e_R0. This matrix operation procedure maintains the hierarchical nature of scalability L, for the hierarchical level 0 of scalability R.

0105Furthermore, no further hash operation on the entry e^R0(0,0) is carried out because there is no higher hierarchy than the hierarchical level 0 of scalability R in the key element matrix M<b>2</b>.

0106On the other hand, in the key element matrix M<b>2</b>, the entries e^R0(i,1) (i=0, 1, 2) in the lower hierarchy than the hierarchical level 0 of scalability R are assigned the same values as the corresponding entries e^R0(i,0) (i=0, 1, 2). This is synonymous with the following: the entries e^R0(i,1) (i=0, 1, 2) are assigned values obtained by successively carrying out the hash operation with the one-way hash function on each of the entries e^R0(1,1) and e^R0(0,1) in which the value of the entry e^R0(2,0) is copied once. In <figref idref="DRAWINGS">FIG. 11</figref>, CP represents the copy operation.

0107In this case, the key element matrix M<b>2</b> thus generated also enables the access control to the packets P_i,0(i=0, 1, 2), while maintaining the hierarchical nature of scalability L. In <figref idref="DRAWINGS">FIG. 11</figref> and others, “CP” means copy.

0108Subsequently, the key generating means <b>463</b> generates a partial key matrix MP<b>1</b> by combining the entries coordinately consistent among the key element matrices M<b>1</b>-M<b>3</b> generated by the matrix generating means <b>462</b> as described above. Namely, entries in the partial key matrix MP<b>1</b> serve as partial keys K_i,j(i=0, 1, 2; j=0, 1) corresponding to the respective packets P_i,j(i=0, 1, 2; j=0, 1). As described above, for each of the hierarchies of one scalability R (resolution level), the partial keys are generated while maintaining the hierarchical nature of the other scalability L (layer), whereby the hierarchical nature is maintained in the layer and in the resolution level. The output means <b>480</b> outputs the partial keys (i=0, 1, 2; j=0, 1) generated by the key generating means <b>463</b> as described above, to the coding means <b>410</b>. The coding means <b>410</b> codes the packets P_i,j(i=0, 1, 2; j=0, 1) by the respective corresponding partial keys K_i,j(i=0, 1, 2; j=0, 1). In this manner, as coded data to be delivered through the network <b>300</b>, the JPEG2000 packet codestreams thus encrypted are delivered to the PC <b>200</b> together with the master key K_2,1.

Third Embodiment

0109The encryption key generating operation (encryption key generating method according to the third embodiment) executed in the third embodiment of the encryption key generating apparatus according to the present invention will be described below. The encryption key generating apparatus according to the third embodiment, similar to the first embodiment, has the structure shown in <figref idref="DRAWINGS">FIG. 7</figref>, and is realized with a hardware configuration concretely shown in <figref idref="DRAWINGS">FIG. 2A</figref>. In this third embodiment, the scalabilities as access control targets are scalability L (layer) and scalability R (resolution level), the number of hierarchies N_Lin scalability L is 4, and the number of hierarchies N_Rin scalability R is 3. At this time, packets in respective hierarchies in scalabilities L and R are handled as 4×3 matrix entries P_i,j(i=0, 1, 2; j=0, 1, 2). <figref idref="DRAWINGS">FIG. 12</figref> is a conceptual diagram for explaining the encryption key generating operation (operation of the operating means <b>460</b> shown in <figref idref="DRAWINGS">FIG. 7</figref>) executed in the third embodiment of the encryption key generating apparatus according to the present invention. <figref idref="DRAWINGS">FIG. 13</figref> is a conceptual diagram for explaining generation of key element matrices by the matrix generating means <b>462</b> in the encryption key generating apparatus according to the third embodiment.

0110The master key is a partial key delivered by the input means <b>450</b> through the D/B <b>110</b> or the network <b>300</b>, and is stored temporarily stored in the storage means <b>470</b>. Namely, the master key is a partial key corresponding to the lowest packet preliminarily managed by the storage means <b>470</b> and in the example of <figref idref="DRAWINGS">FIG. 12</figref>, it is an encryption key K_3,2corresponding to the packet P_3,2in the hierarchies at the lowest position in each of the scalabilities L and R. This master key K_3,2is, by the key dividing means <b>461</b>, divided by a smaller value (=min(N_L,N_R)) out of the hierarchy number N_Lof scalability L and the hierarchy number N_Rof scalability R. Namely, the key dividing means <b>461</b> divides the master key K_3,2by the hierarchy number of scalability R (minimum hierarchy number 3) to obtain split keys e_R2, e_R1, and e_R0. These split keys e_R2, e_R1, and e_R0are root keys corresponding to the respective hierarchies of scalability R and the matrix generating means <b>462</b> generates key element matrices M<b>1</b>-M<b>3</b> for the respective hierarchies of scalability R.

0111The matrix entries in the respective key element matrices M<b>1</b>-M<b>3</b> are successively generated from the split keys e_R2, e_R1, and e_R0being the corresponding root keys, as shown in <figref idref="DRAWINGS">FIG. 13</figref>.

0112First, in the key element matrix M<b>1</b>, as a matrix corresponding to the hierarchical level 2 (lowest hierarchy) of scalability R, the split key e_R2is assigned to the (3,2) entry. In the drawing, superscript R2 to each matrix entry e represents the hierarchical level of scalability R (reference scalability) corresponding to the key element matrix M<b>1</b>, and each subscript represents coordinates of an entry in the key element matrix M<b>1</b>. In this third embodiment, the entries in the key element matrix M<b>1</b> will be denoted below by e^R2(i,j) (i=0, 1, 2, 3; j=0, 1, 2).

0113The coordinate entries e^R2(2,2), e^R2(1,2), and e^R2(0,2) corresponding to the respective remaining hierarchies in scalability L in the hierarchy (hierarchical level=2) in scalability R corresponding to the split key e_R2are assigned operation data successively obtained by repeating the hash operation on the split key e_R2using the one-way hash function H*. Specifically, e^R2(2,2) is assigned the operation data of H*(e^R2(3,2)), e^R2(1,2) is assigned the operation data of H*²(e^R2(3,2)), and the entry e^R2(0,2) is assigned the operation data of H*³(e^R2(3,2)). This matrix operation procedure maintains the hierarchical nature of scalability L, for the hierarchical level 2 of scalability R.

0114On the other hand, in the key element matrix M<b>1</b>, all the entries e^R2(i,j) (i=0, 1, 2, 3; j=0, 1) in the higher hierarchies than the hierarchical level 2 of scalability R are assigned operation data H*(e^R2(0,2))(=H*⁴(e^R2(3,2))) obtained by further carrying out the hash operation with the one-way hash function H* on the entry e^R2(0,2). The operation data at this time is a value corresponding to a packet with the hierarchy number of scalability L being −1 (which is nonexistent in fact).

0115The key element matrix M<b>1</b> generated as described above enables the access control to the packets P_i,2(i=0, 1, 2, 3), while maintaining the hierarchical nature of scalability L.

0116In the key element matrix M<b>2</b>, as a matrix corresponding to the hierarchical level 1 of scalability R, the split key e_R1is assigned to the (3,1) entry. In this third embodiment, the entries in the key element matrix M<b>2</b> will be denoted below by e^R1(i,j) (i=0, 1, 2, 3; j=0, 1, 2).

0117Operation data of H*(e^R1(3,1)) is assigned to the coordinate entry e^R1(2,1), operation data of H*²(e^R1(3,1)) is assigned to the entry e^R1(1,1), and operation data of H*³(e^R1(3,1)) is assigned to the entry e^R1(0,1), corresponding to the respective remaining hierarchies in scalability L in the hierarchy (hierarchical level=1) in scalability R corresponding to the split key e_R1. This matrix operation procedure maintains the hierarchical nature of scalability L, for the hierarchical level 1 of scalability R.

0118Furthermore, in the key element matrix M<b>2</b>, all the entries e^R1(i,0) (i=0, 1, 2, 3) in the higher hierarchy than the hierarchical level 1 of scalability R are assigned operation data H*(e^R1(0,1)) H*⁴(e^R1(3,1))) obtained by further carrying out the hash operation with the one-way hash function H* on the entry e^R2(0,1). The operation data at this time is a value corresponding to a packet with the hierarchy number of scalability L being −1 (which is nonexistent in fact).

0119On the other hand, in the key element matrix M<b>2</b>, the entries e^R1(i,2) (i=0, 1, 2, 3) in the lower hierarchy than the hierarchical level 1 of scalability R are assigned the same values as the corresponding entries e^R1(i,1) (i=0, 1, 2, 3). This is synonymous with the following: the entries e^R1(i,2) (i=0, 1, 2) are assigned values obtained by successively carrying out the hash operation with the one-way hash function on the entry e^R1(3,2) in which the value of the entry e^R1(3,1) is copied once. In <figref idref="DRAWINGS">FIG. 13</figref> and others, “CP” means copy.

0120The key element matrix M<b>2</b> generated as described above enables the access control to the packets P_i,1(i=0, 1, 2, 3), while maintaining the hierarchical nature of scalability L.

0121Similarly, in the key element matrix M<b>3</b>, as a matrix corresponding to the hierarchical level 0 (highest hierarchy) of scalability R, the split key e_R0is assigned to the (3,0) entry. In this third embodiment, the entries in the key element matrix M<b>3</b> will be denoted below by e^R0(i,j) (i=0, 1, 2, 3; j=0, 1, 2).

0122Operation data of H*(e^R0(3,0)) is assigned to the coordinate entry e^R0(2,0), operation data of H*²(e^R0(3,0)) is assigned to the entry e^R0(1,0), and operation data of H*³(e^R0(3,0)) is assigned to the entry e^R0(0,0), corresponding to the respective remaining hierarchies in scalability L in the hierarchy (hierarchical level=0) in scalability R corresponding to the split key e_R0. This matrix operation procedure maintains the hierarchical nature of scalability L, for the hierarchical level 0 of scalability R.

0123Furthermore, no further hash operation is carried out on the entry e^R0(0,0) because there is no higher hierarchy than the hierarchical level 0 of scalability R in the key element matrix M<b>3</b>.

0124On the other hand, in the key element matrix M<b>3</b>, the entries e^R0(i,j) (i=0, 1, 2, 3; j=1, 2) in the lower hierarchies than the hierarchical level 0 of scalability R are assigned the same values as the corresponding entries e^R0(i,0) (i=0, 1, 2, 3). This is synonymous with the following: the entries e^R0(i,j) (i=0, 1, 2, 3; j=1, 2) are assigned the values obtained by successively carrying out the hash operation with the one-way hash function on each of the entries e^R0(2,2) and e^R0(3,1) in which the value of entry e^R0(3,0) is copied once. In <figref idref="DRAWINGS">FIG. 13</figref>, CP indicates the copy operation.

0125In this case, the key element matrix M<b>3</b> thus generated enables the access control to the packets P_i,0(i=0, 1, 2, 3), while maintaining the hierarchical nature of scalability L.

0126Subsequently, the key generating means <b>463</b> generates a partial key matrix MP<b>1</b> by combining the entries coordinately consistent among the key element matrices M<b>1</b>-M<b>3</b> generated by the matrix generating means <b>462</b> as described above. Namely, entries in the partial key matrix MP<b>1</b> serve as partial keys K_i,j(i=0, 1, 2, 3; j=0, 1, 2) corresponding to the respective packets P_i,j(i=0, 1, 2, 3; j=0, 1, 2). As described above, for each of the hierarchies of one scalability R (resolution level), the partial keys are generated while maintaining the hierarchical nature of the other scalability L (layer), whereby the hierarchical nature is maintained in the layer and in the resolution level. The output means <b>480</b> outputs the partial keys (i=0, 1, 2, 3; j=0, 1, 2) generated by the key generating means <b>463</b> as described above, to the coding means <b>410</b>. The coding means <b>410</b> codes the packets P_i,j(i=0, 1, 2, 3; j=0, 1, 2) by the respective corresponding partial keys K_i,j(i=0, 1, 2, 3; j=0, 1, 2). In this manner, as coded data to be delivered through the network <b>300</b>, the JPEG2000 packet codestreams thus encrypted are delivered to the PC <b>200</b> together with the master key K_3,2

0127(Evaluation of Resistance to Collusion Attacks)

0128In the following, the encryption keys (partial keys corresponding to the packets in the respective hierarchies) generated by the encryption key generating apparatuses and methods of the first to third embodiments configured as described above will be evaluated as to the resistance to collusion attacks.

0129It is first assumed in this evaluation that data to be coded is JPEG2000 data with scalability L having the hierarchy number N_Land scalability R (resolution level) having the hierarchy number N_R.

0130Partial keys K_i,jfor the JPEG2000 packets P_i,j(i=0, 1, . . . , N_L−1; j=0, 1, . . . , N_R−1) are subordinately generated with the one-way hash function H*, using a partial key K_NL-1,NR-1for the lowest packet P_NL-1,NR-1as a master key. The concepts of superordinate and subordinate of hierarchies are the same as in <figref idref="DRAWINGS">FIG. 1</figref>. Namely, the partial keys K_i,jmust be subordinately generated from partial keys K_a1,b1corresponding to packets P_a1,b1(a1=i, i−1, . . . , N_L-1; b1=j, j−1, . . . , N_R-1) in all the hierarchies lower than or identical to the hierarchy of packet P_i,jin each of the scalabilities L, R. Under this condition, in order to prevent the partial keys K_i,jfrom being illegally generated by a collusion attack from any partial key K_a2,b2corresponding to packet P_a2,b2(a2=0, 1, . . . , i−1; b2=0, . . . , j−1) in a hierarchy at a higher position than packet P_i,jin each of the scalabilities L, R, at least one of elements constituting the partial keys K_i,jmust be an element corresponding to a packet in a lower hierarchy than the partial key P_a2,b2.

0131Let us assume, for example, N_R<N_L. Elements e^Rj_i,jin partial key K_i,jfor all the packets P_i,j(i=0, 1, . . . , N_L−1) in the hierarchy j (0≦j≦N_R−1) of scalability R are subordinately generated by the hash operation H*^(NL-1-i)(e_Rj) with the one-way hash function H*, from the element e_Rjas a root key. At this time, hash operation values H*^(NL-1-i)(e_Rj) in the higher hierarchy in the key element matrix Mj are directly reflected (or copied) into corresponding elements e^Rj_i,b1in partial key K_i,b1for all packets P_i,b1(i=0, 1, . . . , N_L−1) in a lower hierarchy b1 (<j) of scalability R. On the other hand, a hash operation value H*^NL(e_Rj) is assigned to elements e^Rj_i,b2in partial key K_i,b2for all packets P_i,b2(i=0, 1, . . . , N_L−1) in a higher hierarchy b2 (>j) in scalability R.

0132For this reason, a partial key in a higher hierarchy is reflected in at least some of elements constituting a partial key in a lower hierarchy, while any elements in a partial key in a lower hierarchy are not reflected in elements constituting a partial key in a higher hierarchy. Namely, the partial keys generated by the encryption key generating method of the present invention do not allow any partial key in a lower hierarchy to be generated from a partial key in a higher hierarchy, and, therefore, they have the resistance to collusion attacks.

0133(Generation of Encryption Keys in Decryption)

0134The below will describe generation of encryption keys (partial keys corresponding to respective packets allowed) by the encryption key generation apparatuses and methods according to the present invention, in decryption (decoding). In the foregoing encryption key generating operation (operation of the operating means <b>460</b> shown in <figref idref="DRAWINGS">FIG. 7</figref>), each of partial keys in hierarchies at higher positions was subordinately generated from the only managed master key. On the occasion of decryption, namely in a decoding process in the PC <b>200</b> in <figref idref="DRAWINGS">FIG. 7</figref>, partial keys in a hierarchy at each higher position are similarly subordinately generated from a master key, but a user (PC <b>200</b>) receives only a delivered decryption key (master key) for the lowest packet in a packet group authorized to open.

0135Specifically, in the case of NL=NR=3, as shown in <figref idref="DRAWINGS">FIG. 3</figref>, the PC <b>200</b> side, requesting a grayscale picture Q_L,R(0≦L≦N_Land 0≦R≦N_R) up to scalability L (layer) and scalability R (resolution level), is authorized to open an image with JPEG2000 packet codestream P_L,Ras the lowest packet (packet in hierarchies at the lowest position in each of the scalabilities L, R) and the input means <b>450</b> receives a key K_L,R(0≦L≦2 and 0≦R≦2) for the packet. The key K_L,R(0≦L≦2 and 0≦R≦2) is stored in the storage means <b>470</b>. When the user is allowed to view the coded picture Q_L,Rin <figref idref="DRAWINGS">FIG. 3</figref>, the encryption key generation apparatus <b>400</b> generates decryption keys (decoding keys) corresponding to respective packets P in a frame A ((N_L−R+1)×(N_R−L+1)) as the master key by making use of the key K_L,Rcorresponding to the coded picture Q_L,R. In this case, the key element matrices M<b>1</b>-M<b>3</b> corresponding to split keys e^R2, e^R1, and e^R0generated from the key K_L,Rare also (N_L−R+1)×(N_R−L+1) matrices.

0136The following will explain a case where the user is allowed to view a coded picture Q_1,1in <figref idref="DRAWINGS">FIG. 3</figref>. In this case, the key generation in the encryption key generation apparatus <b>400</b> corresponds to a part of <figref idref="DRAWINGS">FIG. 9</figref>, and decryption keys (decoding keys) corresponding to respective packets P_1,0, P_0,1, and P_0,0in the frame A are generated by making use of the key K_1,1corresponding to the coded picture Q_1,1.

0137For that, in the PC <b>200</b> side, the key dividing means <b>461</b> divides the partial key K_1,1, as the master key, stored in the storage means <b>470</b> by the number of hierarchies in scalability R (i.e., by three) to generate three split keys e^R2, e^R1, and e^R0.

0138Subsequently, the matrix generating means <b>462</b> generates a key element matrix for each of the three hierarchies in scalability R. Among the three split keys e^R2, e^R1, and e^R0, a split key in a lower corresponding hierarchy of scalability R than the corresponding hierarchy of the received key K_1,1is hash operation data with the hierarchical level of the other scalability L being −1. In this case, therefore, the same value as the corresponding partial key is preliminarily assigned to all entries in the key element matrix.

0139First, in generation of the 2×2 key element matrix M<b>1</b> corresponding to the hierarchy 2 of scalability R, the partial key e^R2is hash operation data corresponding to the hierarchy −1 of scalability L. Namely, since the hierarchy (hierarchical level: 2) corresponding to the split key e^R2of scalability R is lower than the hierarchy (hierarchical level: 1) of scalability R corresponding to the master key K_1,1, the value of the split key e^R2is the hash operation value with the hierarchical level of scalability L being −1. In this case, the same value as the split key e^R2(with the hierarchical level of scalability L being −1) is assigned to all the matrix entries e^R2(0,1), e^R2(1,1), e^R2(0,0), and e^R2(1,0) in the 2×2 key matrix M<b>1</b> corresponding to the split key e^R2.

0140Next, in generation of the 2×2 key element matrix M<b>2</b> corresponding to the hierarchy 1 of scalability R, the value of the split key e^R1is first assigned to the e^R1(1,1) entry. The entry e^R1(0,1) in the higher hierarchy of scalability L is assigned operation data H*(e^R1(1,1)) of the hash operation with the one-way hash function H*. Furthermore, hash operation data H*²(e^R2(1,1)) with the hierarchical level of scalability L: −1 is assigned to each of the entries e^R1(1,0) and e^R1(0,0) corresponding to the higher hierarchy (hierarchical level: 0) than the hierarchy (hierarchical level: 1) corresponding to the split key e^R1in scalability R. Conversely, no hash operation is carried out because there is no lower hierarchy (hierarchical level: 2) than the hierarchy (hierarchical level: 1) corresponding to the split key e^R1in scalability R.

0141On the other hand, in generation of the 2×2 key element matrix M<b>3</b> corresponding to the hierarchy 0 of scalability R, there is no higher hierarchy (hierarchical level: −1) than the hierarchy (hierarchical level: 0) corresponding to the split key e^R0in scalability R. Therefore, the value of the split key e^R0is first assigned to the e^R0(1,0) entry. The entry e^R0(0,0) in the higher hierarchy of scalability L is assigned operation data H*(e^R1(1,0)) of the hash operation with the one-way hash function H*. Conversely, for the lower hierarchy (hierarchical level: 1) than the hierarchy (hierarchical level: 0) corresponding to the split key e^R0in scalability R, the value of the entry e^R0(1,0) is copied into the e^R0(1,1) entry and the hash operation is successively carried out based on this copy value. Namely, the entry e^R0(0,1) in the higher hierarchy of scalability L is assigned operation data H*(e^R0(1,1)) of the hash operation with the one-way hash function H*.

0142By combining the entries coordinately consistent among the 2×2 key element matrices M<b>1</b>-M<b>3</b> corresponding to the respective hierarchies of scalability R generated by the matrix generating means <b>462</b> as described above, the key generating means <b>463</b> generates decryption keys K_1,0, K_0,1, K_0,0corresponding to the packets P_1.0, P_0,1, P_0,0from the master key K_1,1.

0143As described above, a partial key for a certain packet is not generated from a packet in a higher hierarchy in at least one scalability than the packet of interest, but can be generated from any packet in an equivalent or lower hierarchy in each of scalabilities. For this reason, the partial keys have the resistance to collusion attacks.

Fourth Embodiment

0144<figref idref="DRAWINGS">FIG. 14</figref> is a conceptual diagram for explaining generation of partial keys for digital data with three or more types of hierarchical scalabilities, as the encryption key generating operation executed in the fourth embodiment of the encryption key generating apparatus and method according to the present invention. <figref idref="DRAWINGS">FIG. 15</figref> is a drawing showing a hierarchy table <b>11</b><i>a </i>in the partial key generation of <figref idref="DRAWINGS">FIG. 14</figref>, and a coordinate correspondence relation between partial key element matrices MPa-MPc and a partial key matrix MP<b>4</b>. <figref idref="DRAWINGS">FIGS. 16A and 16B</figref> are drawing for explaining an element correspondence relation between partial key element matrices MPa-MPc and a partial key matrix MP<b>4</b> in the partial key generation of <figref idref="DRAWINGS">FIG. 14</figref>. The encryption key generating apparatus according to the fourth embodiment, similar to the first embodiment, has the structure shown in <figref idref="DRAWINGS">FIG. 7</figref>, and is realized with a hardware configuration concretely shown in <figref idref="DRAWINGS">FIG. 2A</figref>.

0145When there are three or more types of scalabilities as access control targets, a first conceivable method is to repeat the aforementioned key generation procedure (operations of the key generating means <b>461</b>, the matrix generating means <b>2462</b>, and generating means as a minimum processing unit for combinations of two types of scalabilities. In this case, where the number of scalabilities as access control targets is N_S, the number of repetitions of the minimum processing unit is given by _NSC₂(=(N_S(N_S−1))/2).

0146In the example shown in <figref idref="DRAWINGS">FIG. 14</figref>, the encryption keys those corresponding to respective packets in digital data having L (layer) with three hierarchies, R (resolution level) with two hierarchies, and C (component) with three hierarchies, as three types of scalabilities, are generated by the encryption key generating apparatus <b>400</b> according to the fourth embodiment. In this case, the following three partial key element matrices are successively generated through much the same operation process as in the above-described first to third embodiments: partial key element matrix MPb (entry K^RL(0,0)-entry K^RL(2,1)) for a set of scalabilities R and L; partial key element matrix MPc (entry K^RC(0,0)-entry K^RC(2,1)) for a set of scalabilities R and C; partial key element matrix MPa (entry K^LC(0,0)-entry K^LC(2,2)) for a set of scalabilities L and C.

0147On that occasion, as shown in <figref idref="DRAWINGS">FIG. 15</figref>, the matrix generating means <b>462</b> generates also the hierarchy table <b>11</b><i>a </i>showing all combinations of hierarchical values in scalabilities L, R, and C. This hierarchy table <b>11</b><i>a </i>provides a coordinate representation of partial key matrix MP<b>4</b> whose entries are partial keys corresponding to data units in respective hierarchies in scalabilities L, R, and C, by hierarchical value groups of respective combinations. Furthermore, this hierarchy table <b>11</b><i>a </i>shows a relation between types of scalabilities and hierarchical values and it is possible to specify the entries in the partial key element matrices MPa-MPc generated for all the combinations of scalabilities, from this relation. Namely, the matrix generating means <b>462</b> generates a partial key element table <b>11</b><i>b </i>as a table corresponding to all the combinations of hierarchical values in the hierarchy table <b>11</b><i>a. </i>

0148The key combinations listed in the partial key element table <b>11</b><i>b </i>generated in this manner correspond to the hierarchical value combinations in the hierarchy table <b>11</b><i>a </i>showing coordinates of respective entries in the partial key matrix MP<b>4</b>. Each entry K_L,R,C(L=0, 1, 2; R=0, 1; C=0, 1, 2) in the partial key matrix MP<b>4</b> is obtained by combining key elements K^RL_R,L, K^RC_R,C, and K^LC_L,Cconstituting one combination in the partial key element table <b>11</b><i>b</i>, as shown in <figref idref="DRAWINGS">FIG. 16A</figref>. Therefore, the partial key matrix MP<b>4</b> is obtained by combining the key elements in the partial key element table <b>11</b><i>b </i>corresponding to one combination (cf. <figref idref="DRAWINGS">FIG. 16B</figref>), one by one for all the combinations in the hierarchy table <b>11</b><i>a </i>showing the coordinates of respective entries in the partial key matrix MP<b>4</b>.

0149Each entry in the partial key matrix MP<b>4</b> generated by the matrix generating means <b>462</b> in this manner is an encryption key corresponding to each packet in the digital data having L (layer) with three hierarchies, R (resolution level) with two hierarchies, and C (component) with three hierarchies as the scalabilities. Namely, each entry in the partial key matrix MP<b>4</b> is a partial key corresponding to a packet specified by hierarchical values of the scalabilities indicating coordinates of the entry.

0150In cases where there are three or more types of scalabilities as access control targets, the partial keys thus obtained have the resistance to collusion attacks as in the case of two types of scalabilities.

0151The above encryption key generating operation (encryption key generating method according to the fourth embodiment) executed in the encryption key generating apparatus according to the fourth embodiment was described using the two-dimensional matrix representation as in the first to third embodiments, and the following will explain the encryption key generating operation as a generalized method of the fourth embodiment in a stereoscopic state using a three-dimensional matrix representation. It is assumed in the description below that the access control targets are scalabilities L, R, and C, the number of hierarchies N_Lin the scalability L (layer) is 6, the number of hierarchies N_Rin the scalability R (resolution level) is 4, and the number of hierarchies N_cin the scalability C (component) is 3. In this case, packets in the respective hierarchies in scalabilities L, R, and C are handled as 6×4×3 matrix entries P_i,j,k(i=0, 1, 2, 3, 4, 5; j=0, 1, 2, 3; k=0, 1, 2), as shown in <figref idref="DRAWINGS">FIG. 17A</figref>. <figref idref="DRAWINGS">FIG. 17A</figref> is a stereoscopic representation of arrangement of coordinate entries in a three-dimensional partial key matrix QM (the same also applies to a three-dimensional key element matrix).

0152As shown in <figref idref="DRAWINGS">FIG. 17A</figref>, a master key is the coordinate entry K_5,3,2corresponding to the lowest hierarchies of the respective scalabilities L, R, and C. Furthermore, the coordinate entry K_0,0,0is a coordinate entry corresponding to the highest hierarchies of the respective scalabilities L, R, and C.

0153In the case where the 6×4×3 three-dimensional partial key matrix QM as in <figref idref="DRAWINGS">FIG. 17A</figref> is generated according to the aforementioned encryption key generating method of the fourth embodiment, the lowest partial key K_5,3,2is first divided by the number of repetitions, _NSC₂, of the minimum processing unit carried out for two types of scalabilities, to generate master keys K_RL, K_RC, and K_LCfor the minimum processing unit of each set. Here the master key K_RLis a master key for generation of key elements as to the scalabilities L and R. The master key K_RCis a master key for generation of key elements as to the scalabilities R and C. Furthermore, the master key K_LCis a master key for generation of key elements as to the scalabilities L and C (cf. <figref idref="DRAWINGS">FIG. 17B</figref>).

0154<figref idref="DRAWINGS">FIGS. 18A to 18D</figref> are drawings for explaining key element generating steps corresponding to the respective hierarchies of scalabilities L and R, using three-dimensional matrices in stereoscopic indication, in the encryption key generating operation as the generalized operation of the fourth embodiment. In the minimum processing unit about scalabilities L and R, the reference scalability is R, and the master key K_RLis divided by the hierarchy number 4 of the scalability R to obtain four split keys e^RL_R3, e^RL_R2, e^RL_R1, and e^RL_R0(cf. <figref idref="DRAWINGS">FIG. 17B</figref>).

0155First, the split key e^RL_R3is assigned to the coordinate entry P_5,3,2(the hatched portion in <figref idref="DRAWINGS">FIG. 18A</figref>) in the three-dimensional matrix, and then the hash operation on the split key e^RL_R3using the one-way hash function H is carried out in order from the lowest hierarchy to the highest hierarchy of scalability L. Namely, every time the hash operation is carried out, resultant operation data is assigned to a corresponding coordinate entry (all entries located in a region surrounded by solid lines in <figref idref="DRAWINGS">FIG. 18A</figref>). At this time, operation data H*⁵(e^RL_R3) is assigned to the coordinate entry corresponding to the highest hierarchy of scalability L. On the other hand, each of coordinate entries (all entries located in a region surrounded by dashed lines in <figref idref="DRAWINGS">FIG. 18A</figref>) except for the coordinate entries P_{L=0-5,R=3,C=2}assigned the operation data is assigned operation data H*⁶(e^RL_R3) obtained by further carrying out the hash operation with the one-way hash function H on the operation data H*⁵(e^RL_R3) assigned to the coordinate entry corresponding to the highest hierarchy of scalability L. The above operations generate a three-dimensional key element matrix QM_RL1.

0156Subsequently, the split key e^RL_R2is assigned to the coordinate entry P_5,2,2(the hatched portion in <figref idref="DRAWINGS">FIG. 18B</figref>) in the three-dimensional matrix, and then this split key e^RL_R2is copied (CP) once into the coordinate entry P_5,3,2. Then, for each of hierarchy 3 and hierarchy 2 of scalability R, the hash operation on the split key e^RL_R2using the one-way hash function H is carried out in order from the lowest hierarchy to the highest hierarchy of scalability L. Namely, every time the hash operation is carried out, resultant operation data is assigned to a corresponding coordinate entry (all entries located in a region surrounded by solid lines in <figref idref="DRAWINGS">FIG. 18B</figref>). At this time, operation data H*⁵(e^RL_R2) is assigned to the coordinate entry corresponding to the highest hierarchy of scalability L. On the other hand, each of the coordinate entries (all entries located in a region surrounded by dashed lines in <figref idref="DRAWINGS">FIG. 18B</figref>) except for the coordinate entries P_{L=0-5,R=2-3,C=2}assigned the operation data is assigned operation data H*⁶(e^RL_R2) obtained by further carrying out the hash operation with the one-way hash function H on the operation data H*⁵(e^RL_R2) assigned to the coordinate entry corresponding to the highest hierarchy of scalability L. The above operations generate a three-dimensional key element matrix QM_RL2.

0157Furthermore, a three-dimensional key element matrix QM_RL3shown in <figref idref="DRAWINGS">FIG. 18C</figref> is also generated in the same manner as above by the hash operation on the split key e^RL_R1(assigned as the coordinate entry P_5,1,2indicated by hatching). In <figref idref="DRAWINGS">FIG. 18C</figref>, H indicates the hash operation and CP the copy operation of operation data between coordinate entries. Furthermore, a three-dimensional key element matrix QM_RL4is also generated by the hash operation on the split key e^RL_R0(assigned as the coordinate entry P_5,0,2indicated by hatching), as shown in <figref idref="DRAWINGS">FIG. 18D</figref>.

0158Next, <figref idref="DRAWINGS">FIGS. 19A to 19D</figref> are drawings for explaining key element generating steps corresponding to the respective hierarchies of scalabilities R and C, using a three-dimensional matrix in stereoscopic indication, in the encryption key generating operation as the generalized operation of the fourth embodiment. In the minimum processing unit about the scalabilities R and C, the reference scalability is R, and the master key K_RCis divided by the hierarchy number 4 of the scalability R to obtain four split keys e^RC_R3, e^RC_R2, e^RC_R1, and e^RC_R0(cf. <figref idref="DRAWINGS">FIG. 17B</figref>).

0159The split key e^RC_R3is assigned to the coordinate entry P_6,4,3(the hatched portion in <figref idref="DRAWINGS">FIG. 19A</figref>) in the three-dimensional matrix, and then the hash operation on the split key e^RC_R3using the one-way hash function H is carried out in order from the lowest hierarchy to the highest hierarchy of scalability C. Namely, every time the hash operation is carried out, resultant operation data is assigned to a corresponding coordinate entry (all entries located in a region surrounded by solid lines in <figref idref="DRAWINGS">FIG. 19A</figref>). At this time, operation data H*²(e^RC_R3) is assigned to the coordinate entry corresponding to the highest hierarchy of scalability C. On the other hand, each of coordinate entries (all entries located in a region surrounded by dashed lines in <figref idref="DRAWINGS">FIG. 19A</figref>) except for the coordinate entries P_{L=5,R=3,C=0-2}assigned the operation data is assigned operation data H*³(e^RC_R3) obtained by further carrying out the hash operation with the one-way hash function H on the operation data H*²(e^RC_R3) assigned to the coordinate entry corresponding to the highest hierarchy of scalability C. The above operations generate a three-dimensional key element matrix QM_RC1.

0160A three-dimensional key element matrix QM_RC2shown in <figref idref="DRAWINGS">FIG. 19B</figref> is generated by repeating the copy operation of the split key e^RC_R2(assigned as the coordinate entry P_5,2,2indicated by hatching) into the lower hierarchy than the hierarchy 2 of the reference scalability R, and the hash operation from the lowest hierarchy to the highest hierarchy of scalability C (hash operation on the split key e^RC_R2using the one-way hash function H). Similarly, a three-dimensional key element matrix QM_RC3shown in <figref idref="DRAWINGS">FIG. 19C</figref> is also generated by repeating the copy operation of the split key e^RC_R1(assigned as the coordinate entry P_5,1,2indicated by hatching) into each of the lower hierarchies than the hierarchy 1 of the reference scalability R, and the hash operation from the lowest hierarchy to the highest hierarchy of scalability C (hash operation on the split key e^RC_R1using the one-way hash function H). Furthermore, a three-dimensional key element matrix QM_RC4shown in <figref idref="DRAWINGS">FIG. 19D</figref> is also generated by repeating the copy operation of the split key e^RC_R0(assigned as the coordinate entry P_5,0,2indicated by hatching) into each of the higher hierarchies than the hierarchy 0 (highest hierarchy) of the reference scalability R, and the hash operation from the lowest hierarchy to the lowest hierarchy of scalability C (hash operation on the split key e^RC_R0using the one-way hash function H).

0161<figref idref="DRAWINGS">FIGS. 20A to 20C</figref> are drawings for explaining key element generating steps corresponding to the respective hierarchies of scalabilities L and C, using a three-dimensional matrix in stereoscopic indication, in the encryption key generating operation as the generalized method of the fourth embodiment. In the minimum processing unit about the scalabilities L and C, the reference scalability is C, and the master key K_LCis divided by the hierarchy number 3 of the scalability C to obtain three split keys e^LC_C2, e^LC_C1, and e^LC_C0(cf. <figref idref="DRAWINGS">FIG. 17B</figref>).

0162The split key e^LC_C2is assigned to the coordinate entry P_6,4,3(the hatched portion in <figref idref="DRAWINGS">FIG. 20A</figref>) in the three-dimensional matrix, and then the hash operation on the split key e^LC_C3using the one-way hash function H is carried out in order from the lowest hierarchy to the highest hierarchy of scalability L. Namely, every time the hash operation is carried out, resultant operation data is assigned to a corresponding coordinate entry (all entries located in a region surrounded by solid lines in <figref idref="DRAWINGS">FIG. 20A</figref>). At this time, operation data H*⁵(e^LC_C2) is assigned to the coordinate entry corresponding to the highest hierarchy of scalability L. On the other hand, each of coordinate entries (all entries located in a region surrounded by dashed lines in <figref idref="DRAWINGS">FIG. 20A</figref>) except for the coordinate entries P_{L=0-5,R=3,C=2}assigned the operation data is assigned operation data H*⁶(e^LC_C2) obtained by further carrying out the hash operation with the one-way hash function H on the operation data H*⁵(e^LC_C2) assigned to the coordinate entry corresponding to the highest hierarchy of scalability L. The above operations generate a three-dimensional key element matrix QM_LC1.

0163A three-dimensional key element matrix QM_LC2shown in <figref idref="DRAWINGS">FIG. 20B</figref> is generated by repeating the copy operation of the split key e^LC_C1(assigned as the coordinate entry P_5,3,1indicated by hatching) into the lower hierarchy than the hierarchy 1 of the reference scalability C, and the hash operation from the lowest hierarchy to the highest hierarchy of scalability L (hash operation on the split key e^LC_C1using the one-way hash function H). Similarly, a three-dimensional key element matrix QM_LC3shown in <figref idref="DRAWINGS">FIG. 20C</figref> is also generated by repeating the copy operation of the split key e^LC_C0(assigned as the coordinate entry P_5,3,0indicated by hatching) into each of the lower hierarchies than the hierarchy 0 (highest hierarchy) of the reference scalability C, and the hash operation from the lowest hierarchy to the highest hierarchy of scalability L (hash operation on the split key e^LC_C0using the one-way hash function H).

0164A three-dimensional partial key matrix QM by the encryption key generating operation as the generalized operation of the fourth embodiment is obtained by combining the coordinate entries at the same positions in the three-dimensional key element matrices QM_RL1-QM_RL4, QM_RC1-QM_RC4, QM_LC1-QM_LC3shown of <figref idref="DRAWINGS">FIGS. 18A to 20C</figref>, which were generated by repetitions of the above-described hash operation.

Fifth Embodiment

0165Since in the above-described encryption key generating operation executed by the encryption key generating apparatus according to the fourth embodiment the minimum processing unit is definitely the partial key generating procedure with two types of scalabilities, the resultant partial keys are vulnerable to collusion attacks by three or more persons with increase in the number of hierarchies in each scalability (e.g., there are a plurality of coordinate lines with the same partial key in a multidimensional partial key matrix like the three-dimensional partial key matrix QM in <figref idref="DRAWINGS">FIG. 17A</figref>). Therefore, the encryption key generating apparatus and method according to the present invention generates an encryption key with a sufficiently resistant to collusion attacks by three or more persons. The encryption key generating apparatus and method of the fifth embodiment will also be described with reference to the three-dimensional partial key matrix QM shown in <figref idref="DRAWINGS">FIG. 17</figref><i>a</i>, and it is assumed that the access control targets are scalabilities L, R, and C, the number of hierarchies N_Lin the scalability L (layer) is 6, the number of hierarchies N_Rin the scalability R (resolution level) is 4, and the number of hierarchies N_Cin the scalability C (component) is 3. At this time, packets in respective hierarchies in scalabilities L, R, and C are handled as 6×4×3 matrix entries P_i,j,k(i=0, 1, 2, 3, 4, 5; j=0, 1, 2, 3; k=0, 1, 2). The master key prepared is the coordinate entry K_5,3,2corresponding to the lowest hierarchies of the respective scalabilities L, R, and C, as shown in <figref idref="DRAWINGS">FIG. 17A</figref> (the coordinate entry K_0,0,0is the coordinate entry corresponding to the highest hierarchies of the respective scalabilities L, R, and C). The encryption key generating apparatus according to the fifth embodiment, similar to the first embodiment, has the structure shown in <figref idref="DRAWINGS">FIG. 7</figref>, and is realized with a hardware configuration concretely shown in <figref idref="DRAWINGS">FIG. 2A</figref>. The prepared master key is preliminarily stored in the storage means <b>470</b> through the input means <b>450</b>.

0166First, in the encryption key generating operation (encryption key generating method according to the fifth embodiment) executed by the encryption key generating apparatus according to the fifth embodiment, the key dividing means <b>461</b> preliminarily sets two types of scalabilities as reference scalabilities out of the three or more types of scalabilities, as shown in <figref idref="DRAWINGS">FIG. 21</figref>. In the example shown in <figref idref="DRAWINGS">FIG. 21</figref>, scalabilities L and R are set as reference scalabilities. Particularly, the reference scalability R (first reference scalability) is a scalability for generating split keys from the master key K_5,3,2. The key dividing means <b>461</b> divides the master key by the hierarchy number 4 of this reference scalability R to generate four split keys e^RL_R3, e^RL_R2, e^RL_R1, and e^RL_R0corresponding to the respective hierarchies of the reference scalability R. On the other hand, the reference scalability L is a scalability for defining an operation direction of the hash operation with the one-way hash function as described above. <figref idref="DRAWINGS">FIG. 21</figref> is a drawing for explaining an example of the generation operation (operation of the key dividing means <b>461</b> shown in <figref idref="DRAWINGS">FIG. 7</figref>) for the split keys from the master key, in the encryption key generation operation executed in the fifth embodiment of the encryption key generating apparatus and method according to the present invention.

0167The matrix generating means <b>462</b> of the encryption key generating apparatus of the fifth embodiment generates a three-dimensional key element matrix in coordinate representation with hierarchical values in three or more types of scalabilities L, R, C (cf. <figref idref="DRAWINGS">FIG. 17A</figref>) by a series of hash operations corresponding to the respective hierarchies of the reference scalability R, for each hierarchy of the scalability C except for the reference scalabilities L, R. In this fifth embodiment, therefore, with three types of scalabilities L, R, and C (hierarchy number of L: 6; hierarchy number of R: 4; hierarchy number of C: 3), the total packet number given by Mathematical Expression (1) above is 72, and the number of generated three-dimensional key element matrices given by Mathematical Expression (2) above is 12.

0168<figref idref="DRAWINGS">FIGS. 22A to 24D</figref> are drawings for explaining steps of generating the three-dimensional key element matrices by the encryption key generating method of the fifth embodiment. Particularly, <figref idref="DRAWINGS">FIGS. 22A to 22D</figref> show the three-dimensional key element matrices QM_1-1, QM_2-1, QM_3-1, and QM_4-1generated by assigning predetermined coordinate entries the operation data obtained by successively carrying out the hash operation from the lowest hierarchy to the highest hierarchy of scalability L, for the lowest hierarchy (hierarchy 2) of the scalability C other than the reference scalabilities L and R. <figref idref="DRAWINGS">FIGS. 23A to 23D</figref> show the three-dimensional key element matrices QM_1-2, QM_2-2, QM_3-2, and QM_4-2generated by assigning predetermined coordinate entries the operation data obtained by successively carrying out the hash operation from the lowest hierarchy to the highest hierarchy of the scalability L, for the hierarchy (hierarchy 1) higher by one hierarchy than the lowest hierarchy of the scalability C other than the reference scalabilities L and R. <figref idref="DRAWINGS">FIGS. 24A to 24D</figref> show the three-dimensional key element matrices QM_1-3, QM_2-3, QM_3-3, and QM_4-3generated by assigning predetermined coordinate entries the operation data obtained by successively carrying out the hash operation from the lowest hierarchy to the highest hierarchy of the scalability L, for the highest hierarchy (hierarchy 0) of the scalability C other than the reference scalabilities L and R.

0169First, <figref idref="DRAWINGS">FIG. 22A</figref> shows the three-dimensional key element matrix QM_1-1generated using the split key e^RL_R3corresponding to the lowest hierarchy of the reference scalability R, for the lowest hierarchy 2 of the scalability C other than the reference scalabilities L and R.

0170The split key e^RL_R3is assigned to the coordinate entry P_5,3,2(the hatched portion in <figref idref="DRAWINGS">FIG. 22A</figref>) in the three-dimensional matrix, and then the hash operation on the split key e^RL_R3using the one-way hash function H is carried out in order from the lowest hierarchy to the highest hierarchy of scalability L. Namely, every time the hash operation is carried out, resultant operation data is assigned to a corresponding coordinate entry (all entries located in a region surrounded by solid lines in <figref idref="DRAWINGS">FIG. 22A</figref>). At this time, operation data H*⁵(e^RL_R3) is assigned to the coordinate entry corresponding to the highest hierarchy of the scalability L. On the other hand, each of the coordinate entries (all entries located in a region surrounded by dashed lines in <figref idref="DRAWINGS">FIG. 22A</figref>) except for the coordinate entries P_{L=0-5,R=3,C=2}assigned the operation data is assigned operation data H*⁶(e^RL_R3) obtained by further carrying out the hash operation with the one-way hash function H on the operation data H*⁵(e^RL_R3) assigned to the coordinate entry corresponding to the highest hierarchy of the scalability L. The above operations generate the three-dimensional key element matrix QM_1-1.

0171<figref idref="DRAWINGS">FIG. 22B</figref> shows the three-dimensional key element matrix QM_2-1generated using the split key e^RL_R2corresponding to the hierarchy 2 of the reference scalability R (hierarchy higher by one hierarchy than the lowest hierarchy), for the lowest hierarchy 2 of the scalability C other than the reference scalabilities L and R.

0172In generation of this three-dimensional key element matrix QM_2-1, the split key e^RL_R2is assigned to the coordinate entry P_5,2,2(the hatched portion in <figref idref="DRAWINGS">FIG. 22B</figref>) in the three-dimensional matrix. At this time, the split key e^RL_R2is copied (CO) once into the coordinate entry P_5,3,2. Then, for each of hierarchy 3 and hierarchy 2 of scalability R, the hash operation on the split key e^RL_R2using the one-way hash function H is carried out in order from the lowest hierarchy to the highest hierarchy of the scalability L. Namely, every time the hash operation is carried out, resultant operation data is assigned to a corresponding coordinate entry (all entries located in a region surrounded by solid lines in <figref idref="DRAWINGS">FIG. 22B</figref>). At this time, operation data H*⁵(e^RL_R2) is assigned to the coordinate entry corresponding to the highest hierarchy of the scalability L. On the other hand, each of the coordinate entries (all entries located in a region surrounded by dashed lines in <figref idref="DRAWINGS">FIG. 22B</figref>) except for the coordinate entries P_{L=0-5,R=2-3,C=2}assigned the operation data is assigned operation data H*⁶(e^RL_R2) obtained by further carrying out the hash operation with the one-way hash function H on the operation data H*⁵(e^RL_R2) assigned to the coordinate entry corresponding to the highest hierarchy of the scalability L. The above operations generate the three-dimensional key element matrix QM_2-1.

0173The three-dimensional key element matrix QM_3-1shown in <figref idref="DRAWINGS">FIG. 22C</figref> is also generated in the same manner as in the generation of the three-dimensional key element matrices QM_1-1and QM_2-1, by repeating the copy operation of the split key e^RL_R1(assigned as the coordinate entry P_5,1,2indicated by hatching) into each of the lower hierarchies than the hierarchy 1 of the reference scalability R, and the hash operation from the lowest hierarchy to the highest hierarchy of the scalability L (hash operation on the split key e^RL_R1using the one-way hash function H). Similarly, the three-dimensional key element matrix QM_4-1shown in <figref idref="DRAWINGS">FIG. 22D</figref> is also generated by repeating the copy operation of the split key e^RL_R0(assigned as the coordinate entry P_5,0,2indicated by hatching) into each of the lower hierarchies than the hierarchy 0 (highest hierarchy) of the reference scalability C, and the hash operation from the lowest hierarchy to the highest hierarchy of the scalability L (hash operation on the split key e^RL_R0using the one-way hash function H).

0174Next, <figref idref="DRAWINGS">FIG. 23A</figref> shows the three-dimensional key element matrix QM_1-2generated using the split key e^RL_R3corresponding to the lowest hierarchy of the reference scalability R, for the hierarchy 1 (hierarchy higher by one hierarchy than the lowest hierarchy) of the scalability C other than the reference scalabilities L and R.

0175The split key e^RL_R3is assigned to the coordinate entry P_5,3,1(the hatched portion in <figref idref="DRAWINGS">FIG. 23A</figref>) in the three-dimensional matrix, and then this split key e^RL_R3is copied (CP) once into the coordinate entry P_5,3,1. Then, for each of hierarchy 2 (lowest hierarchy) and hierarchy 1 (hierarchy higher by one hierarchy than the lowest hierarchy) of the scalability C, the hash operation on the split key e^RL_R3using the one-way hash function H is carried out in order from the lowest hierarchy to the highest hierarchy of the scalability L. Namely, every time the hash operation is carried out, resultant operation data is assigned to a corresponding coordinate entry (all entries located in a region surrounded by solid lines in <figref idref="DRAWINGS">FIG. 23A</figref>). At this time, operation data H*⁵(e^RL_R3) is assigned to each coordinate entry corresponding to the highest hierarchy of the scalability L. On the other hand, each of the coordinate entries (all entries located in a region surrounded by dashed lines in <figref idref="DRAWINGS">FIG. 23A</figref>) except for the coordinate entries P_{L=0-5,R=3,C=2-3}assigned the operation data is assigned operation data H*⁶(e^RL_R3) obtained by further carrying out the hash operation with the one-way hash function H on the operation data H*⁵(e^RL_R3) assigned to the coordinate entry corresponding to the highest hierarchy of the scalability L. The above operations generate the three-dimensional key element matrix QM_1-2.

0176<figref idref="DRAWINGS">FIG. 23B</figref> shows the three-dimensional key element matrix QM_2-2generated using the split key e^RL_R2corresponding to the hierarchy 2 (hierarchy higher by one hierarchy than the lowest hierarchy) of the reference scalability R, for the hierarchy 1 of the scalability C other than the reference scalabilities L and R.

0177In generation of this three-dimensional key element matrix QM_2-2, the split key e^RL_R2is assigned to the coordinate entry P_5,2,1(the hatched portion in <figref idref="DRAWINGS">FIG. 23B</figref>) in the three-dimensional matrix. At this time, the split key e^RL_R2is copied (CP) once into the coordinate entries P_5,2-3,1-2. Then, for each of hierarchy 3 and hierarchy 2 of the scalability R in hierarchy 2 and hierarchy 1 of the scalability C, the hash operation on the split key e^RL_R2using the one-way hash function H is carried out in order from the lowest hierarchy to the highest hierarchy of the scalability L. Namely, every time the hash operation is carried out, resultant operation data is assigned to a corresponding coordinate entry (all entries located in a region surrounded by solid lines in <figref idref="DRAWINGS">FIG. 23B</figref>). At this time, operation data H*⁵(e^RL_R2) is assigned to each coordinate entry corresponding to the highest hierarchy of the scalability L. On the other hand, each of the coordinate entries (all entries located in a region surrounded by dashed lines in <figref idref="DRAWINGS">FIG. 23B</figref>) except for the coordinate entries P_{L=0-5,R=2-3,C=1-2}assigned the operation data is assigned operation data H*⁶(e^RL_R2) obtained by further carrying out the hash operation with the one-way hash function H on the operation data H*⁵(e^RL_R2) assigned to the coordinate entry corresponding to the highest hierarchy of the scalability L. The above operations generate the three-dimensional key element matrix QM_2-2.

0178The three-dimensional key element matrix QM_3-2shown in FIG. <b>23</b>C is also generated in the same manner as in the generation of the three-dimensional key element matrices QM_1-2and QM_2-2described above, by repeating the copy operation of the split key e^RL_R1(assigned as the coordinate entry P_5,1,1indicated by hatching) into each of the lower hierarchies than the hierarchy 1 of the reference scalability R and the lower hierarchy than the hierarchy 1 of the scalability C, and the hash operation from the lowest hierarchy to the highest hierarchy of the scalability L (hash operation on the split key e^RL_R1using the one-way hash function H). Similarly, the three-dimensional key element matrix QM_4-2shown in <figref idref="DRAWINGS">FIG. 23D</figref> is also generated by repeating the copy operation of the split key e^RL_R0(assigned as the coordinate entry P_5,0,1indicated by hatching) into each of the lower hierarchies than the hierarchy 0 (highest hierarchy) of the reference scalability R and the lower hierarchy than the hierarchy 1 of the reference scalability C, and the hash operation from the lowest hierarchy to the highest hierarchy of the scalability L (hash operation on the split key e^RL_R0using the one-way hash function H).

0179Furthermore, <figref idref="DRAWINGS">FIG. 24A</figref> shows the three-dimensional key element matrix QM_1-3generated using the split key e^RL_R3corresponding to hierarchy 3 (lowest hierarchy) of the reference scalability R, for hierarchy 0 (highest hierarchy) of the scalability C other than the reference scalabilities L and R.

0180The split key e^RL_R3is assigned to the coordinate entry P_5,3,0(the hatched portion in <figref idref="DRAWINGS">FIG. 24A</figref>) in the three-dimensional matrix, and then this split key e^RL_R3is copied (CP) once into each of the coordinate entries P_5,3,C=1,2. Then, for each of hierarchy 2 (lowest hierarchy) to hierarchy 0 (highest hierarchy) of the scalability C in hierarchy 3 (highest hierarchy) of the reference scalability R, the hash operation on the split key e^RL_R3using the one-way hash function H is carried out in order from the lowest hierarchy to the highest hierarchy of the scalability L. Namely, every time the hash operation is carried out, resultant operation data is assigned to a corresponding coordinate entry (all entries located in a region surrounded by solid lines in <figref idref="DRAWINGS">FIG. 24A</figref>). At this time, operation data H*⁵(e^RL_R3) is assigned to each coordinate entry corresponding to the highest hierarchy of the scalability L. On the other hand, each of the coordinate entries (all entries located in a region surrounded by dashed lines in <figref idref="DRAWINGS">FIG. 24A</figref>) except for the coordinate entries P_{L=0-5,R=3,C=0-2}assigned the operation data is assigned operation data H*⁶(e^RL_R3) obtained by further carrying out the hash operation with the one-way hash function H on the operation data H*⁵(e^RL_R3) assigned to the coordinate entries corresponding to the highest hierarchy of the scalability L. The above operations generate the three-dimensional key element matrix QM_1-3.

0181<figref idref="DRAWINGS">FIG. 24B</figref> shows the three-dimensional key element matrix QM_2-3generated using the split key e^RL_R2corresponding to hierarchy 2 (hierarchy higher by one hierarchy than the lowest hierarchy) of the reference scalability R, for hierarchy 0 (highest hierarchy) of the scalability C other than the reference scalabilities L and R.

0182In generation of this three-dimensional key element matrix QM_2-3, the split key e^RL_R2is assigned to the coordinate entry P_5,2,0(the hatched portion in <figref idref="DRAWINGS">FIG. 24B</figref>) in the three-dimensional matrix. At this time, the split key e^RL_R2is copied (CP) once into each of the coordinate entries P_5,2-3,0-2. Then, for each of hierarchy 2 (highest hierarchy) to hierarchy 0 (lowest hierarchy) of the scalability C in hierarchy 3 and hierarchy 2 of the scalability R, the hash operation on the split key e^RL_R2using the one-way hash function H is carried out in order from the lowest hierarchy to the highest hierarchy of the scalability L. Namely, every time the hash operation is carried out, resultant operation data is assigned to a corresponding coordinate entry (all entries located in a region surrounded by solid lines in <figref idref="DRAWINGS">FIG. 24B</figref>). At this time, operation data H*⁵(e^RL_R2) is assigned to each of the coordinate entries corresponding to the highest hierarchy of the scalability L. On the other hand, each of the coordinate entries (all entries located in a region surrounded by dashed lines in <figref idref="DRAWINGS">FIG. 24B</figref>) except for the coordinate entries P_{L=0-5,R=2-3,C=0-2}assigned the operation data, is assigned operation data H*⁶(e^RL_R2) obtained by further carrying out the hash operation with the one-way hash function H on the operation data H*⁵(e^RL_R2) assigned to the coordinate entries corresponding to the highest hierarchy of the scalability L. The above operations generate the three-dimensional key element matrix QM_2-3.

0183The three-dimensional key element matrix QM_3-3shown in <figref idref="DRAWINGS">FIG. 24C</figref> is also generated in the same manner as in the generation of the three-dimensional key element matrices QM_1-3and QM_2-3described above, by repeating the copy operation of the split key e^RL_R1(assigned as the coordinate entry P_5,1,0indicated by hatching) into each of the lower hierarchies than hierarchy 1 of the reference scalability R and the lower hierarchies than the hierarchy 0 (highest hierarchy) of the scalability C, and the hash operation from the lowest hierarchy to the highest hierarchy of the scalability L (hash operation on the split key e^RL_R1using the one-way hash function H). Similarly, the three-dimensional key element matrix QM_4-3shown in <figref idref="DRAWINGS">FIG. 24D</figref> is also generated by repeating the copy operation of the split key e^RL_R0(assigned as the coordinate entry P_5,0,0indicated by hatching) into each of the lower hierarchies than the hierarchy 0 (highest hierarchy) of the reference scalability R and the lower hierarchies than the hierarchy 0 (highest hierarchy) of the reference scalability C, and the hash operation from the lowest hierarchy to the highest hierarchy of the scalability L (hash operation on the split key e^RL_R0using the one-way hash function H).

0184The three-dimensional partial key matrix QM by the encryption key generating method of the fifth embodiment is obtained by the key dividing means <b>461</b> combining the coordinate entries at the same coordinate positions in the three-dimensional key element matrices QM_1-1-QM_4-1, QM_1-2-QM_4-2, and QM_1-3-QM_4-3shown in <figref idref="DRAWINGS">FIGS. 22A to 24D</figref>, which were generated by the matrix generating means <b>462</b> repeating the hash operation described above. The output means <b>480</b> outputs such a three-dimensional partial keys generated by the key generating means <b>463</b> to the coding means <b>410</b>.

0185According to the apparatus and method of present invention, as described above, the partial keys for the hierarchies at subordinately higher positions are generated by making use of the one-way hash function from the master key, and, therefore, a partial key corresponding to one data unit specified by hierarchical levels in respective scalabilities cannot be generated from any partial key corresponding to a data unit at a higher hierarchical position in one of the scalabilities. Therefore, it becomes feasible to prevent collusion attacks. Since the partial keys are generated for each of combinations of two types of scalabilities as scalabilities of access control targets, it is feasible to reduce the key length of the generated partial keys.

0186From the invention thus described, it will be obvious that the embodiments of the invention may be varied in many ways. Such variations are not to be regarded as a departure from the spirit and scope of the invention, and all such modifications as would be obvious to one skilled in the art are intended for inclusion within the scope of the following claims.