DESCRIPTION KEY PROVIDING SYSTEM, KEY PROVIDING APPARATUS, TERMINAL DEVICE, KEY PROVIDING METHOD, AND KEY GENERATION METHOD Technical Field [0001] The present invention relates to a key providing system, a key providing apparatus, a terminal device, a key providing method, and a key generation method. Background Art [0002] Information devices such as personal computer (hereinafter referred to as PC), portable telephone, and digital home electrical appliance are recently being widespread used in general. The technique related to such information devices and information communication connecting such devices is greatly advancing, and content distribution service such as music distribution and video distribution using such information device is being widely developed. Pay broadcasting using CATV (Community Antenna Television), satellite broadcast or Internet, and content distribution using physical media such as CD (Compact Disc) or DVD (Digital Versatile Disc) are examples of the content distribution service. [0003] However, in order to provide such content distribution service, a mechanism allowing only the contractant to acquire the content based on the contract made between the provider of the service (hereinafter referred to as system manager) and the viewer is necessary. With respect to such issue, a mechanism of providing a predetermined key from the system manager to the contractant, and distributing header information h for generating a content key mek used to encrypt content M with the predetermined key along with the encrypted content M is contrived. [0004] A content distribution system called the broadcast encryption system is known as one specific means for realizing such mechanism. The broadcast encryption system is a system of corresponding each contract with an element of a set, and then dividing the contractant set representing the entire contractant into a plurality of subsets, and distributing the header h such that only the contractant belonging to a specific subset acquires the content key mek. That is, the content M can be distributed excluding the specific contractant specified by the system manager by applying such system. In reality, however, the broadcast encryption system of the related art is desirably more efficient in view of the calculation load associated with the generation of the content key mek at the server device (hereinafter referred to as center) on the system manager side and the terminal device on the contractant side, the communication load between the server device and the terminal device, and the like. [0005] Specifically, when distributing the content, to what extent the amount of communication that increases according to the size of the header h distributed by the center, the amount of memory that increases according to the number of keys to be held by each terminal device, and the amount of calculation necessary for each terminal device to generate the content key mek can be reduced becomes an issue. Each amount greatly differs depending on the dividing method of the contractant set. Various broadcast encryption systems devising the dividing method of the contractant set have been proposed to realize efficient content distribution. For instance, Non-Patent Document 1 discloses a content distribution system called the Subset Incremental Chain Based Broadcast Encryption system by Nuttapong Attrapadung and Hideki Imai et al. as one means for reducing each amount (hereinafter referred to as AI05 system). [0006] [Non-Patent Document 1] Nuttapong Attrapadung and Hideki Imai, "Subset Incremental Chain Based Broadcast Encryption with Shorter Ciphertext", The 28th Symposium on Information Theory and Its Applications (SITA2005) Disclosure of the Invention [0007] The applicant of the present invention developed a first improved system (hereinafter referred to as A06(A) system) in which the amount of memory for each terminal device to hold the key can be reduced, a second improved system (hereinafter referred to as A06(B) system) in which the amount of calculation for each terminal device to generate the content key can be reduced, and a third improved system (hereinafter referred to as A06(A+B) system) in which the amount of memory and the amount of calculation can be reduced than the content distribution system described in Non-Patent Document 1, and has already been filed for patent to Japanese Patent Office (A06(A) system: Japanese Application No. 2006-310182, A06(B) system: Japanese Application No. 2006-310213, A06(A+B) system: Japanese Application No. 2006-310226). The characteristics of each system lie in that when generating the content key mek utilizing a pseudo random sequence generator, the pseudo random sequence generation calculation is executed based on a key generation algorithm represented by a digraph unique to each system. [0008] However, when generating a key corresponding to a subset from a key corresponding to another subset according to a certain system, not limited to each system above, if the set related information such as the digraph including information of a plurality of key generation paths are all to be held on the terminal device side, the storage capacity to hold the information of the plurality of key generation paths becomes large. If the terminal device is to acquire all the information of the key generation path held by the key providing apparatus, the capacity propagated for the terminal device to acquire the information of the plurality of key generation paths becomes large. [0009] The present invention addresses the above-identified, and other issues associated with conventional methods and apparatuses, and it is desirable to provide a new and improved key providing system capable of reducing the capacity necessary for the terminal device to propagate or hold the information for key generation compared to when the terminal device propagates or holds all the key generation path information in advance, a key providing apparatus, a terminal device, a key providing method, and a key generation method. [0010] According to an embodiment of the present invention, there is provided a key providing system including a plurality of terminal devices, and a key providing apparatus for providing key information used for encryption or decryption of information to the plurality of terminal devices. Further, the key providing apparatus may include a set relationship information acquiring unit for acquiring set relationship information including a plurality of set information each indicating different combinations of the plurality of terminal devices, and a plurality of key generation path information indicating a key generation path necessary for generating, from the key information corresponding to one of the plurality of set information, key information corresponding to another one of the plurality of set information, a key generation path information extracting unit for extracting the key generation path information of one part of the plurality of key generation path information from the plurality of key generation path information contained in the set relationship information, and a key generation path information providing unit for providing the key generation path information of one part extracted by the key generation path information extracting unit to the terminal device. Furthermore, the terminal device may include a key generation path information acquiring unit for acquiring the key generation path information of one part, and a key information generation unit for generating, from the key information corresponding to one of the plurality of set information, key information corresponding to another one of the plurality of set information based on the key generation path information of one part. [0011] According to another embodiment of the present invention, there is provided a key providing apparatus for providing key information used for encryption or decryption of data to a plurality of terminal devices. The key providing apparatus includes a set relationship information acquiring unit for acquiring set relationship information including a plurality of set information each indicating different combinations of the plurality of terminal devices, and a plurality of key generation path information indicating a key generation path necessary for generating, from the key information corresponding to one of the plurality of set information, key information corresponding to another one of the plurality of set information; a key generation path information extracting unit for extracting the key generation path information of one part of the plurality of key generation path information from the plurality of key generation path information contained in the set relationship information; and a key generation path information providing unit for providing the key generation path information of one part extracted by the key generation path information extracting unit to the terminal device. [0012] Further, the key generation path information providing unit may include a communication unit for transmitting the key generation path information to the terminal device through a network. [0013] Further, the key generation path information providing unit may include a recording unit for recording the key generation path information to a recording medium to provide to the terminal device. [0014] Also, the key providing apparatus may further include an encryption unit for encrypting information using the key information corresponding to one of the plurality of set information; and an encrypted information providing unit for providing the encrypted information to the terminal device. [0015] Further, the key generation path information acquiring unit may be configured to acquire, as the set relationship information, a digraph formed by directional branches connecting coordinate points with respect to a plurality of coordinate points corresponded to the plurality of set information each indicating different combinations of the plurality of terminal devices. [0016] Further, the key generation path information extracting unit may be configured to extract, as the key generation path information of one part, one part of the digraph reaching a coordinate point corresponded to the set information to which the terminal device belongs. [0017] Further, the key generation path information extracting unit may be configured to extract, as the key generation path information of one part, information indicating a terminating end position of the directional branch configuring one part of the digraph. [0018] Further, the key generation path information extracting unit may be configured to extract, as the key generation path information of one part, information indicating a length of the directional branch configuring one part of the digraph. [0019] Also, the key providing may further include a key information generation unit for generating the key information k(S1), ..., k(Sm) corresponding to coordinate points S1, ..., Sm of the terminating ends of all directional branches having a coordinate point S0 as the starting end according to the input of the key information k(S0) corresponding to the coordinate point S0. [0020] Further, the key information may be configured by a set key k for encrypting or decrypting information, and an intermediate key t for generating the set key k. Furthermore, the key providing apparatus may further include a key information generation unit for generating the set key k(S0) corresponding to the coordinate point S0 and the intermediate key t(S1), ..., t(Sm) corresponding to coordinate points S1, ..., Sm of the terminating ends of all directional branches having a coordinate point S0 as the starting end according to the input of the intermediate key t(S0) corresponding to the coordinate point S0. [0021] According to another embodiment of the present invention, there is provided a key providing apparatus for providing key information used for encryption or decryption of information to a plurality of terminal devices. The key providing apparatus includes: a set relationship information generation unit for generating set relationship information including a plurality of set information each indicating different combinations of the plurality of terminal devices, and a plurality of key generation path information indicating a key generation path necessary for generating, from the key information corresponding to one of the plurality of set information, key information corresponding to another one of the plurality of set information; a key generation path information extracting unit for extracting the key generation path information of one part of the plurality of key generation path information from the plurality of key generation path information contained in the set relationship information; and a key generation path information providing unit for providing the key generation path information of one part extracted by the key generation path information extracting unit to the terminal device. [0022] According to another embodiment of the present invention, there is provided a terminal device for generating key information used for encryption or decryption of information. The terminal device includes: a key generation path information acquiring unit for acquiring key generation path information of one part of a plurality of key generation path information extracted from set relationship information including a plurality of set information each indicating different combinations of the plurality of terminal devices, and a plurality of key generation path information indicating a key generation path necessary for generating, from the key information corresponding to one of the plurality of set information, key information corresponding to another one of the plurality of set information; and a key information generation unit for generating, from the key information corresponding to one of the plurality of set information, key information corresponding to another one of the plurality of set information based on the key generation path information of one part. [0023] Further, the key generation path information acquiring unit may include a communication unit for receiving the key generation path information through a network. [0024] Further, the key generation path information acquiring unit may include a readout unit for acquiring a recording medium recorded with the key generation path information and reading out the key generation path information from the recording medium. [0025] Also, the terminal device may further includes: an encrypted information acquiring unit for acquiring information encrypted using the key information corresponding to another one of the plurality of set information; and an encrypted information decryption unit for decrypting the encrypted information using the key information corresponding to another one of the plurality of set information generated by the key information generation unit. [0026] Further, the key generation path information acquiring unit may be configured to acquire, with respect to a plurality of coordinate points corresponded to the plurality of set information each indicating different combinations of the plurality of terminal devices, one part of a digraph reaching a coordinate point corresponded to the set information to which the terminal device belongs extracted from the digraph formed by directional branches connecting the coordinate points as the key generation path information of one part. [0027] Further, the key generation path information acquiring unit may be configured to acquire, as the key generation path information of one part, information indicating a terminating end position of the directional branch configuring one part of the digraph. [0028] Further, the key generation path information acquiring unit may be configured to acquire, as the key generation path information of one part, information indicating a length of the directional branch configuring one part of the digraph. [0029] Also, the terminal device may further include a key information generation unit for generating the key information k(S1) corresponding to a coordinate point S1 of the terminating end of the directional branch according to an input of the key information k(S0) corresponding to a starting end S0 of the directional branch. [0030] Further, the key information may be configured by a set key k for encrypting or decrypting information, and an intermediate key t for generating the set key k. Furthermore, the terminal device may further include a key information generation unit for generating the set key k(S0) corresponding to a starting end S0 of the directional branch and the intermediate key t(S1) corresponding to a terminating end S1 of the directional branch according to an input of the intermediate key t(S0) corresponding to the starting end S0 of the directional branch. [0031] According to another embodiment of the present invention, there is provided a key providing method for providing key information used for encryption or decryption of data to a plurality of terminal devices. The key providing method includes the steps of: acquiring set relationship information including a plurality of set information each indicating different combinations of the plurality of terminal devices, and a plurality of key generation path information indicating a key generation path necessary for generating, from the key information corresponding to one of the plurality of set information, key information corresponding to another one of the plurality of set information; extracting the key generation path information of one part of the plurality of key generation path information from the plurality of key generation path information contained in the set relationship information; and providing the key generation path information of one part extracted by the key generation path information extracting unit to the terminal device. [0032] According to another embodiment of the present invention, there is provided a key generation method for generating key information used for encryption or decryption of information. The key generation method includes the steps of: acquiring key generation path information of one part of a plurality of key generation path information extracted from set relationship information including a plurality of set information each indicating different combinations of a plurality of terminal devices and a plurality of key generation path information indicating a key generation path for generating, from the key information corresponding to one of the plurality of set information, key information corresponding to another one of the plurality of set information; and generating, from the key information corresponding to one of the plurality of set information, key information corresponding to another one of the plurality of set information based on the key generation path information of one part. [0033] According to each configuration described above, the key generation path information of one part extracted by the key providing apparatus is provided to the terminal device, and the terminal device derives, from the key corresponding to one set, a key corresponding to another set, and thus the capacity necessary for propagating the key generation path information from the key providing apparatus to the terminal device can be limited compared to when receiving the provision of all the key generation path information held in the key providing apparatus. Furthermore, the capacity required by the terminal device for holding the key generation path information can be limited compared to when the terminal device holds all the key generation path information in advance. [0034] According to the present invention described above, the capacity necessary for the terminal device to propagate or hold the information for key generation can be reduced compared to when the terminal device propagates or holds all the key generation path information in advance. Brief Description of the Drawings [0035] FIG. 1 is an explanatory view showing a configuration of a key providing system 100 according to first and second embodiments of the present invention; FIG. 2 is an explanatory view showing a hardware configuration of a key distribution server 102 and a terminal device 122 according to the embodiment; FIG. 3 is an explanatory view showing a structure of a logical binary tree according to the embodiment; FIG. 4 is an explanatory view showing a digraph H according to the AI05 system; FIG. 5 is an explanatory view showing a flow of a key distribution process according to the AI05 system; FIG. 6 is an explanatory view showing a flow of a key distribution process according to the AI05 system; FIG. 7 is an explanatory view showing a decryption process of an encrypted text according to the present embodiment; FIG. 8 is an explanatory view showing a function configuration of the key distribution server 102 according to the present embodiment; FIG. 9 is an explanatory view showing a flow of a process for generating a temporary digraph F according to a A06(A+B) system; FIG. 10 is an explanatory view showing the temporary digraph V of the A06(A+B) system; FIG. 11 is an explanatory view showing a flow of a process for generating a digraph I according to the A06(A+B) system; FIG. 12 is an explanatory view showing a flow of a process for generating a digraph I according to the A06(A+B) system; FIG. 13 is an explanatory view showing a flow of a process for generating a digraph I according to the A06(A+B) system; FIG. 14 is an explanatory view showing a flow of a process for generating a digraph I according to the A06(A+B) system; FIG. 15 is an explanatory view showing the digraph I of the A06(A+B) system; FIG. 16 is an explanatory view showing an example of a directional path referenced when applying the embodiment to the digraph H of the AI05 system; FIG. 17 is an explanatory view showing an example of a directional path referenced when applying the embodiment to the digraph H of the AI05 system; FIG. 18 is an explanatory view showing an example of a directional path referenced when applying the embodiment to the digraph I of the A06(A+B) system; FIG. 19 is an explanatory view showing a function configuration of a terminal device 122 according to the present embodiment; FIG. 20 is an explanatory view showing a flow of a key generation process according to a first embodiment of the present invention; FIG. 21 is an explanatory view showing a flow of a key generation process according to a second embodiment of the present invention; FIG. 22 is an explanatory view showing a configuration of a broadcast encryption system 300 serving as an application example of the first and second embodiments of the present invention; and FIG. 23 is an explanatory view showing a configuration of a broadcast encryption system 400 serving as an application example of the first and second embodiments of the present invention. Explanation of Reference Numerals [0036] 100 key providing system 102 key distribution server 104 tree structure setting unit 106 coordinate axis setting unit 108 temporary digraph generation unit 110 digraph generation unit 112 initial intermediate key setting unit 114 key generation unit 116 encryption unit 118 communication unit 120 subset determination unit 121 path information generation unit 122 terminal device 124 communication unit 126 judgment unit 128 key generation unit 130 decryption unit 202 controller 204 calculation unit 206 input/output interface 208 secure storage unit 210 main storage unit 212 network interface 216 media interface 218 information media Best Mode for Carrying out the Invention [0037] Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the appended drawings. Note that, in this specification and the appended drawings, configuring elements that have substantially the same function configuration are denoted with the same reference numerals, and redundant explanation of these configuring elements will be omitted. [0038] 63) indicates the direction of the directional branch. The digraph H(33→63) is obtained as a result of executing the above-described algorithm for the case of lv = 33, rv = 64, k = 6, n = 64. The black circle drawn at the lowermost stage in FIG. 4 represents the digraph H(2←2), ..., H(63→63) in order from the left. [0107] The above-described algorithm is provided to generate the rightward digraph H(lv→rv-l), but the leftward digraph H(lv+l←rv) can be similarly generated by applying the algorithm. However, when setting the horizontal coordinate axis forming the digraphs H(lv+1←rv) and H(2←n), it is to be noted that the subset S; is arrayed such that the inclusion relation becomes larger from the right towards the left on the horizontal coordinate axis and that the direction of the directional branch is leftward. [0108] The method of generating the digraph H according to the AI05 system has been described above. The logic for generating the set key using the digraph H will be described below. [0109] (Generation of set key) In the AI05 system, the content key mek is encrypted using each set key k(Si) corresponding to each subset S1 configuring the set system SS. Each coordinate point of the digraph H corresponds to the subset S; representing the combination of the terminal devices 122, as described above. The set key k(Si) and the intermediate key t(S1) are corresponded to each subset Si. The method of generating the set key k(S;) based on the digraph H will be described in view of such correspondence relationship. [0110] The coordinate point indicated by the terminating end of one or more directional branches having the coordinate point S0 as the starting end is expressed as S1, S2, ..., Sk in the order closer to the starting end S0 of the relevant directional branch (order of shorter directional branch). If the number of directional branches having the coordinate point S0 as the starting point is q (q < k), the coordinate points S(q+1), S(q+2), ..., Sk are counted as dummies but are not actually used. S1nce the number of repetition processes in (step 2-2) is x (1 < x < k), the number of directional branches having each coordinate point of the digraph H as the starting end is k at maximum. [0111] According to the AI05 system, the set key k(S,) is generated using the PRSG that outputs (k+l)*l bits with respect to the input of k bits. When the intermediate key t(S0) corresponding to the coordinate point S0 is input, the PRSG outputs the intermediate key t(S1), t(S2), ..., t(Sk) corresponding to each coordinate point (e.g., coordinate points S1, S2, ..., Sk) to which the directional branch having the coordinate point S0 as the starting end reaches, and the set key k(S0) corresponding to the input intermediate key t(S0). That is, t(S1)||...||t(Sk)||k(S0)←PRSG(t(S0)). The intermediate keys t(S1), t(S2),..., t(Sk) and the set key k(S0) can be generated by sectionalizing the output of the PRSG by  bits from the left. [0112] For instance, with reference to FIG. 4, four directional branches are output from the coordinate point S0 focusing on the coordinate point S0 = [1, 8] (eighth coordinate point from the left end) of the digraph H(l →64). The ending points of the directional branches are coordinate points S1 = [1,9], S2 = [1,10], S3 = [1,12], and S4 = [1,16]. Therefore, when the intermediate key t(S0) is input to the PRSG, the set key k(S0) and the intermediate keys t(S1), t(S2), t(S3), t(S4) can be generated. Furthermore, when the intermediate key t(S4) is input to the PRSG, the set key k(S4) and the intermediate keys t(S11), t(S12), t(S13), t(S14), t(S1s) corresponding to S11 = [1,17], S12 = [1,18], S13 = [1,20], S14 = [1,24], S15 = [1,32] can be generated. The plurality of set keys thus can be calculated by repeatedly using the PRSG. [0113] As described above, the intermediate key and the set key can be generated based on the digraph H if the predetermined intermediate key t(S0) is held. However, if the information of the digraph H is not referenced, the intermediate key or the set key generated by inputting the predetermined intermediate key t(S0) to the PRSG are not known, and thus the desired set key becomes difficult to generated. It is an object of the present embodiment to provide a solution to such issue. This will be hereinafter described. [0114] The key generation method using the intermediate key has been described up to now, but the configuration of using the intermediate key is not essential in the existing AI05 system and in the present embodiment to be hereinafter described. The intermediate key is used for the purpose of enhancing safety, and another set key k(S1) etc. may be directly calculated from the set key k(S0) when significant attention is not paid to safety, when attempting to reduce the amount of calculation for generating the set key, or the like. For instance, when the set key k(S0) is input to the PRSG, the set keys k(S1), k(S2), k(S3), k(S4) corresponding to the reaching destinations of the directional branches extending from the coordinate point S0 may be output. [0115] The method of generating the set key has been described above. As can be easily understood from the above example, if a certain intermediate key is being held, such intermediate key may be used and the PRSG may be iteratively executed to derive the intermediate key and the set key corresponding to all coordinate points that can be reached by a chain of directional branches extending from the coordinate point corresponding to the relevant intermediate key. Therefore, each terminal device 122 merely holds the minimum intermediate key that can derive all intermediate keys corresponding to the subset to which it is included as an element. [0116] The key distribution server 102 uses the intermediate key corresponding to the head coordinate point (hereinafter referred to as route) of each digraph H, and repeatedly executes the calculation by the PRSG to derive the set key corresponding to all coordinate points to which the directional branches configuring each digraph can reach. [0117] Therefore, the manager of the key providing system 100, for example, generates a random sequence of A. bits and sets as an intermediate key of the route of each digraph H in the key distribution server 102 in time of setup of the key providing system 100. The route of the digraph H refers to the coordinate point where the directional branch extends from the relevant coordinate point but the directional branch does not reach the relevant coordinate point. For instance, the route of the digraph H(l→64) of FIG. 4 is the coordinate point [1,1] positioned at the left end of the horizontal coordinate axis. [0118] The method of generating the set key has been described above. This method is used not only when generating the set key for the key distribution server 102, which is the transmitter side of the content or the content key, to encrypt the content or the content key and the intermediate key to distribute to each terminal device 122, but also to generate the desired set key using the intermediate key it holds in advance even in the terminal device 122 on the reception side. [0119] (Method of distributing intermediate key) A method in which the key distribution server 102 distributes a predetermined intermediate key to each terminal device 122 will now be described. A plurality of intermediate keys from which the set key corresponding to all subsets to which the relevant terminal device 122 is included can be derived is provided in advance to each terminal device 122. To the contrary, the intermediate key from which the set key corresponding to the subset to which the relevant terminal device 122 is not included can be derived is not provided to the terminal device 122, and the number of intermediate keys to be provided to the terminal device 122 is preferably a minimum. [0120] The key distribution server 102 extracts all digraphs H that can reach the coordinate point corresponding to the subset in which the terminal device 122 of contractant u is included. If the terminal device 122 of the contractant u is included in the subset corresponding to the route of the digraph H, only the intermediate key corresponding to the relevant route is provided to the terminal device 122 of the contractant u. [0121] If the terminal device 122 of the contractant u is included in one of the subsets corresponding to the coordinate points other than the route of the digraph H, the subset S0 where the terminal device 122 of the contractant u is included in the subset S0 and not included in the subset parent (S0) or the parent of the subset S0 is extracted. The intermediate key t(S0) corresponding to the subset S0 is provided to the terminal device 122 of the contractant u. [0122] That is, if the terminal device 122 of the contractant u is included in the subset corresponding to a plurality of coordinate points other than of the route of the digraph H, the starting end of the directional branch reaching each coordinate point is referenced, and a coordinate point is selected such that the subset corresponding to the starting end of each coordinate point does not include the terminal device 122 corresponding to the contractant u. With the subset corresponding to such coordinate point as S0, and the subset corresponding to the starting end (parent) of the directional branch reaching the coordinate point S0 as parent (S0), the intermediate key t(S0) corresponding to the coordinate point S0 not including the subset parent (S0) is provided to the terminal device 122 of the contractant u. [0123] If the coordinate point S0 exists in plurals, the respective intermediate key t(S0) is provided to the terminal device 122 of the contractant u. The parent-child relationship of the coordinate point is defined by the directional branch. That is, the starting end of the directional branch becomes the parent of the terminating end, and the terminating end of the directional branch becomes the child of the starting end. The parent of the coordinate point S0 is noted as parent (S0). It can be recognized that the parent of the coordinate point S0 does not exist if the coordinate point S0 is the route of the digraph H. Only one parent of the coordinate point S0 exists if the coordinate point S0 is not the route of the digraph H. [0124] The method of distributing the intermediate key will now be specifically described with reference to the example of FIG. 4. [0125] (Example 1) The intermediate key distributed to the terminal device 122 of the contractant 1 will be considered. First, the digraph H that can reach the subset to which the terminal device 122 of the contractant 1 is included is extracted. With reference to FIG. 4, such digraph H is only digraph H(l→64). The terminal device 122 of the contractant 1 belongs to the subset [1,1] corresponding to the route of the digraph H( 1→64). Therefore, the intermediate key t([l,l]) is distributed to the terminal device 122 of the contractant 1. [0126] (Example 2) The intermediate key distributed to the terminal device 122 of a contractant 3 will be considered. First, the digraph H that can reach the subset to which the terminal device 122 of the contractant 3 is included is extracted. With reference to FIG. 4, such digraph H is digraph H(l→64), H(2←64), H(2←32), H(2←16), H(2←8), H(2←4), H(3→3). Considering digraph H(l→64) first, it can be seen that the terminal device 122 of the contractant 3 is not included in the subset [1,1] corresponding to the route of the digraph H(l→64). [0127] However, the terminal device 122 of the contractant 3 is included in the subsets [1,3], [1,4], ..., [1,64] after the third coordinate point. It can be seen with reference to the subset of the parent of such coordinate points that the coordinate points that do not include the terminal device 122 of the contractant 3 in the subset of the parent are only [1,3] and [1,4]. Therefore, the coordinate point [1,2] corresponding to the parents parent ([1,3]) and the parent ([1,4]) of the coordinate points [1,3], [1,4] does not include the terminal device 122 of the contractant 3. [0128] As a result, the intermediate keys t([l,3]) and t([l,4]) corresponding to the digraph H(l→64) are distributed to the terminal device 122 of the contractant 3. S1milarly, the intermediate key is selected for other digraphs H(2←64), H(2←32), H(2←16), H(2←8), H(2←4), H(3→3) and distributed to the terminal device 122 of the contractant 3. Consequently, a total of eight intermediate keys are distributed to the terminal device 122 of the contractant 3. [0129] The process in which the key distribution server 102 distributes the intermediate key to each terminal device 122 will be briefly described with reference to FIG. 5. FIG. 5 is a flowchart showing a process in which the key distribution server 102 distributes the intermediate key to each terminal device 122 in time of system setup. [0130] As shown in FIG. 5, the key distribution server 102 determines the number of contractant n, number of bits X of the set key and the intermediate key, a predetermined parameter k, and the pseudo-random sequence generation algorithm by PRSG, and the like, and publicizes the same to all the terminal devices 122 (S102). The key distribution server 102 then divides the set of terminal devices 122 to a predetermined subset, and then determines the set system SS (see Equation (1)) expressed by the sum of sets, and publicizes the same to all the terminal devices 122 (S104). The key distribution server 102 determines the digraph H formed by a plurality of directional branches T, and publicizes partial or entire information to all the terminal devices 122 (S106). The intermediate key corresponding to each subset configuring the set system SS is then determined (S108). The intermediate key for each terminal device 122 to derive the desired set key based on the digraph is distributed to each terminal device 122 (S110). [0131] The method of distributing the intermediate key has been described above. Through the use of such distribution method, the intermediate key for the terminal device 122 of each permitted contractant to generate the set key can be efficiently distributed, and the amount of communication between the key distribution server 102 and the terminal device 122 and the amount of memory for each terminal device 122 to hold the key can be saved. [0132] (Method of distributing content key) A method of distributing the content key mek encrypted by the key distribution server 102 will now be described. [0133] The key distribution server 102 first encrypts the content key mek using the set key that can be generated only by the terminal device 122 of the permitted contractant. The key distribution server 102 determines the set R including the terminal device 122 of the contractant to be eliminated (hereinafter referred to as eliminating contractant), and determines the set N/R obtained by excluding the set R from the set N including the terminal devices 122 of all contractant 1 to n. [0134] One or a plurality of subsets Si(i = 1,2 ,..., m) is selected from the subset configuring the set system SS, and the set N/R = S1OS2O...OSm is expressed using the selected subset. In this case, the combination of the subset S1 exists in great numbers, but the subset Si in which the m becomes a minimum is desirably selected. [0135] The key distribution server 102 encrypts the content key mek using the set key k(Si) corresponding to each subset S; after selecting the subset Si, and generates m content keys mek encrypted by the set keys(S1), k(S2), .... k(Sm). The key distribution server 102 distributes the m encrypted content keys mek to the terminal devices 122 of all contractant 1 to n. In this case, the key distribution server 102 also distributes one or both of the information of the set N/R and the information of m subsets S; simultaneously to each terminal device 122. [0136] The distribution process of the content key mek encrypted by the key distribution server 102 will be briefly described with reference to FIG. 6. FIG. 6 is an explanatory view showing a flow of the distribution process of the content key. [0137] With reference to FIG. 6, the key distribution server 102 determines the set R of eliminating contractant, and determines the set N/R of permitted contractant (SI 12). Thereafter, the key distribution server 102 selects m subsets Si(i = 1,2 ,..., m) in which the sum of sets becomes N/R from the subsets configuring the set system SS (S114). The key distribution server 102 encrypts the content key mek using the set key k(Si) corresponding to each selected subset S1 (S116). The key distribution server 102 then distributes information representing the set N/R or each subset S1, and the m encrypted content keys mek to all the terminal devices 122 (S118). [0138] The encryption method and the distribution method of the content key mek by the key distribution server 102 have been described above. The subset Si can be selected such that the number of set keys necessary for encryption becomes a minimum by using the encryption method described above. Thus, the amount of calculation for the encryption can be reduced when encrypting the content key mek, the number of encrypted content keys mek to be distributed can be reduced, and the amount of communication can be reduced. [0139] (Decryption method of content key) A decryption process of the content or the content key in each terminal device 122 will now be described. The terminal device 122 decrypts the content key mek based on the information of the set N/R or m subsets S; received from the key distribution server and the m encrypted content keys. [0140] The terminal device 122 receives the encrypted content key mek and the information representing the set N/R or the information representing m subsets S1 from the key distribution server 102. The terminal device 122 then analyzes the information, and judges whether or not it is included in one of the m subsets S1. When judging that it is not included in any subset, the terminal device 122 judges that it is the terminal device 122 of the eliminating contractant, and terminates the decryption process. When the subset Si in which it is included is found, the terminal device 122 derives the set key k(Si) corresponding to the relevant subset Si using the PRSG. The configuration of the PRSG used by the terminal device 122 is similar to the configuration of the PRSG used by the key distribution server 102 in encryption. [0141] Assume that the terminal device 122 is distributed in advance with the intermediate key t(Si) corresponding to the subset S1 or the intermediate key t(Si) from which the intermediate key t(Si) can be derived from the key distribution server 102 in time of system setup. The terminal device 122 inputs the intermediate key t(Si) or t(Si), which it holds, to the PRSG so as to derive the set key k(Si) corresponding to the subset Si. In this case, the terminal device 122 repeatedly executes the process of the PRSG with reference to the information of the digraph, and calculates the set key k(Si). The terminal device 122 then decrypts the encrypted content key mek using the derived set key k(S1). [0142] Reference is again made to FIG. 4. A specific example of the method of deriving the set key k(Si) in the terminal device 122 will be described with reference to FIG. 4. [0143] (Example 1) A process in which the terminal device 122 of the contractant 3 derives the set key corresponding to the subset [1,8] based on the digraph H shown in FIG. 4 will be reviewed. The key distribution server 102 distributes the intermediate key of the subset [1,4] in advance to the terminal device 122 of the contractant 3 in time of the system setup. [0144] First, with reference to the digraph H(l→64), a directional branch extending from the coordinate point [1,4] to the coordinate point [1,8] exists. The directional branch is the directional branch which distance is the third shortest of the directional branches having the coordinate point [1,4] as the starting end. The terminal device 122 of the contractant 3 then extracts the portion of X bits third from the head of the output obtained by inputting the intermediate key t([l,4]) corresponding to the coordinate point [1,4] to the PRSG. The portion of X bits third of the output is the intermediate key t([l,8]) corresponding to the subset [1,8]. After extracting the intermediate key t([l,8]) from the output of the PRSG, the terminal device 122 of the contractant 3 extracts the final X bit of the output obtained by again inputting the intermediate key t(S[l,8]) to the PRSG. The final X bit of the output is the desired set key k([l,8]). The terminal device 122 of the contractant 3 can generate the desired set key k([l,8]) through the above processes. [0145] (Example 2) S1milarly, a case where the terminal device 122 of the contractant 1 generates the set key k([l,8]) based on the digraph H of FIG. 4 will be considered. The terminal device 122 of the contractant 1 holds the intermediate key t([l,l]) corresponding to the subset [1,1] in advance. The terminal device 122 of the contractant 1 extracts the portion (intermediate key t([l,2])) of A. bits first from the head of the output obtained by inputting the intermediate key t([l,l]) to the PRSG. The terminal device 122 of the contractant 1 then extracts the portion (intermediate key t([l,4])) of A, bits second from the head of the output obtained by again inputting the intermediate key t([l,2]) to the PRSG. Furthermore, the terminal device 122 of the contractant 1 extracts the portion (intermediate key t([l,8])) of  bits third from the head of the output obtained by again inputting the intermediate key t([l,4]) to the PRSG. Lastly, the terminal device 122 of the contractant 1 extracts the final  bit (set key k([l,8])) of the output obtained by inputting the intermediate key t([l,8]) to the PRSG, and acquires the desired set key k([l,8]). [0146] A decryption process of the encrypted content key mek in each terminal device 122 will now be described with reference to FIG. 7. FIG. 7 is an explanatory view showing a flow of the decryption process of the content key in the terminal device 122. [0147] With reference to FIG. 7, the terminal device 122 receives the m encrypted content keys mek and the information representing the set N/R or the information representing m subsets S;(i = 1, 2,..., m) from the key distribution server 102 (S120). The terminal device 122 then searches for the subset S; to which it is included (SI22), and determines whether or not included in one of the m subsets S; (S124). [0148] If a subset S; to which it is included exists, the terminal device 122 uses the PRSG to derive the set key k(Si) corresponding to such subset S; (SI26). The terminal device 122 then decrypts the encrypted content key mek using the derived set key k(Si) (S128). [0149] If not included in any of the subsets S1, the terminal device 122 displays and outputs a notification of not being the terminal device 122 of the permitted contractant (notification of being eliminating contractor) (SI 30), and terminates the decryption process of the content key. [0150] The decryption method of the content key in the terminal device 122 has been described above. The decryption method requires the information of the digraph and the PRSG on the terminal device 122 side. However, it is difficult for the terminal device 122 to hold all the information of the digraph as this oppresses the memory amount of the terminal device 122, and it is also difficult for the terminal device 122 to generate all digraphs as this increases the calculation load of the terminal device 122. It is also difficult to distribute all information of the digraph as this significantly increases the amount of calculation or oppresses the storage capacity of the distribution media. The key providing system 100 according to the present embodiment provides means for solving such issues, and the features will be hereinafter described. [0151] (Summary of AI05 system) The AI05 system to which the present embodiment can be applied has been described above. Through the use of the AI05 system, the number of intermediate keys to be held by each terminal device 122 can be suppressed to 0(k*log(n)). The amount of calculation (number of operations of PRSG) necessary for the generation of the set key can be suppressed to lower than or equal to about (2k-l)*(n1/k-l). However, as already pointed by the applicant of the subject application, the AI05 system still needs some improvement from the standpoint of efficiency. For instance, the A06(A) system succeeded in reducing the number of keys to be held by the terminal device 122, and the A06(B) system succeeded in reducing the amount of calculation necessary for the terminal device 122 to generate the key. The A06(A+B) system succeeded in reducing the number of keys to be held by the terminal device 122 and the amount of calculation necessary for generating the key in a satisfactorily balanced manner. The feature of the present embodiment lies in how to provide the information of the digraph necessary when the terminal device 122 generates the key, and thus can be applied to at least all of the systems described above. [0152] (A06(A+B) system) The A06(A+B) system to which the present embodiment can be applied will now be described. As described above, the A06(A+B) system is a system capable of realizing efficient key distribution compared to the AI05 system. Therefore, it is more efficient to apply the A06(A+B) system when applying the present embodiment. [0153] Prior to describing the A06(A+B) system, the efficiency of key distribution will be briefly described. First, the amount of calculation for the terminal device 122 to generate the desired key depends on the number of times the PRSG is executed to derive the desired intermediate key. The worst value corresponds to the number of directional branches that exist until reaching the coordinate point at the end most distant from the route (leaf from which the directional branch does not extend). With reference to the digraph H(l→64), eleven directional branches are passed from the route [1,1] until reaching the coordinate point [1,64] at the end, which means that the PRSG is executed eleven times for the terminal device 122 holding the intermediate key t([l,l]) to derive the intermediate key t([l,64]). Therefore, the amount of calculation of the terminal device 122 can be reduced by reducing the number of directional branches configuring the longest path of the digraph while ensuring the path that can reach all the coordinate points on the horizontal coordinate axis. One approach on the issue is the A06(B) system, and A06(A+B) system is the more improved system. A case of applying the present embodiment to the A06(A+B) system will be described in detail by way of example. [0154] [Configuration of key distribution server 102] The configuration of the key distribution server 102 according to the present embodiment will now be described with reference to FIG. 8. FIG. 8 is an explanatory view showing a configuration of the key distribution server 102 and the terminal device 122 according to the present embodiment. [0155] With reference to FIG. 8, the key distribution server 102 mainly includes a tree structure setting unit 104, a coordinate axis setting unit 106, a temporary digraph generation unit 108, a digraph generation unit 110, an initial intermediate key setting unit 112, a key generation unit 114, an encryption unit 116, a communication unit 118, and a subset determination unit 120. The tree structure setting unit 104, the coordinate axis setting unit 106, the temporary digraph generation unit 108, and the digraph generation unit 110 are collectively referred to as "key generation logic building block". S1milarly, the initial intermediate key setting unit 112 and the key generation unit 114 are collectively referred to as "key generation block". The coordinate axis setting unit 106, the temporary digraph generation unit 108, and the digraph generation unit 110 are examples of the set relationship information generation unit or the set relationship information acquiring unit. The communication unit 118 is an example of the key generation path information providing unit or the encrypted information providing unit. [0156] [Key generation logic building block] First, the key generation logic building block will be described in detail. [0157] (Tree structure setting unit 104) First, the tree structure setting unit 104 will be described. The tree structure setting unit 104 can generate the binary tree structure (see FIG. 3) similar to the AI05 system. The tree structure setting unit 104 first sets the binary tree structure formed by n leaf nodes 1 to n (n is a natural number), the root node, and a plurality of intermediate nodes other than the root node and the leaf node. The tree structure setting unit 104 then sets the number of the leaf node positioned at the left end as lv and the number of the leaf node positioned at the right end as rv of the plurality of leaf nodes arranged at the lower order of the intermediate node v or the root node v. The tree structure setting unit 104 assigns the set (l→n) and the set (2←n) with respect to the root node. The tree structure setting unit 104 corresponds the set (lv+l ←rv) if the intermediate node v is positioned on the left side of the parent node and corresponds the set (lv→rv-l) if the intermediate node v is positioned on the right side of the parent node with respect to an arbitrary intermediate node v forming the binary tree. [0158] (Coordinate axis setting unit 106) The coordinate axis setting unit 106 will be described. The coordinate axis setting unit 106 sets the horizontal coordinate axis based on a rule similar to the AI05 system. First, the coordinate axis setting unit 106 sets a plurality of horizontal coordinate axes. The coordinate axis setting unit 106 then corresponds the plurality of subsets contained in the set (l→n-l) to each coordinate point on one horizontal coordinate axis so that the inclusion relation becomes larger in order from the left side towards the right. S1milarly, coordinate axis setting unit 106 corresponds the plurality of subsets contained in the set (lv→rv-l) to each coordinate point on another one horizontal coordinate axis so that the inclusion relation becomes larger in order from the left side towards the right. The coordinate axis setting unit 106 repeats a similar process for all the sets (lv→rv-l) corresponded to the intermediate nodes forming the binary tree. [0159] The coordinate axis setting unit 106 then corresponds the plurality of subsets contained in the set (2←n) to each coordinate point on another further one horizontal coordinate axis so that the inclusion relation becomes larger in order from the right side towards the left. S1milarly, the coordinate axis setting unit 106 corresponds the plurality of subsets contained in the set (lv+l←rv) to the coordinate point on another further one horizontal coordinate axis so that the inclusion relation becomes larger in order from the right side towards the left. The coordinate axis setting unit 106 repeats a similar process for all the sets (lv+1 ←rv) corresponded to the intermediate nodes forming the binary tree. [0160] The coordinate axis setting unit 106 generates two temporary coordinate points on the right side of the coordinate point positioned at the right end of the horizontal coordinate axis corresponding to the set (1 →n-1). The coordinate axis setting unit 106 then generates two temporary coordinate points on the right side of the coordinate point positioned at the right end of the horizontal coordinate axis corresponding to the set (lv→rv-l). The coordinate axis setting unit 106 also generates two temporary coordinate points on the left side of he coordinate point positioned at the left end of the horizontal coordinate axis corresponding to the set (2←n) and the horizontal coordinate axis corresponding to the set (lv+l←rv). [0161] Through the above processes, the coordinate axis setting unit 106 can set the horizontal coordinate axis for forming the digraph with respect to the set corresponded to all the nodes forming the binary tree. Means for forming the digraph on each horizontal coordinate axis generated by the coordinate axis setting unit 106 will now be described below. [0162] (Temporary digraph generation unit 108) The temporary digraph generation unit 108 will be described. The temporary digraph generation unit 108 generates a temporary digraph I' through a method similar to the method of generating the digraph H in the AI05 system. First, the temporary digraph generation unit 108 sets a predetermined integer k as a parameter. The temporary digraph generation unit 108 determines the integer x satisfying n(x-1)/k < rv-lv+l < nx/k. The temporary digraph generation unit 108 forms a rightward directional branch having a length of nl/k(i = 0~x-l) on the horizontal coordinate axis corresponding to the set (l→n-1) and the set (lv→rv-1). The temporary digraph generation unit 108 forms a leftward directional branch having a length of nl (i = 0~x-1) on the horizontal coordinate axis corresponding to the set (2←n) and the set (lv+1←rv). [0163] As described above, the generation of the directional branch starts from the temporary coordinate point arranged adjacent to the coordinate point corresponding to the subset (i.e., subset including one user) having the least number of elements of the subsets in the AI05 system. It is to be noted that in the A06(A+B) system, the generation of the directional branch starts from the coordinate point corresponding to the subset (i.e., subset including one user) having the least number of elements of the subsets. [0164] The temporary digraph generation unit 108 then erases all directional branches having the temporary coordinate point on the horizontal coordinate axis as the starting end or the terminating end for the directional branches on all the horizontal coordinate axes. With respect to all coordinate points on all horizontal coordinate axes, if the directional branch reaching one coordinate point exists in plurals, the temporary digraph generation unit 108 erases all directional branches other than the directional branch of longest length from the plurality of directional branches reaching the relevant coordinate point. The temporary digraph generation unit 108 adds the rightward directional branch having length of one with the temporary coordinate point positioned on the left side as the terminating end of the temporary coordinate points generated on the horizontal coordinate axis corresponding to the set (l→n-l). That is, the temporary digraph generation unit 108 executes the process of following Equation (3) to generate the temporary digraph I'(l→n) corresponding to the set (1→n) corresponded to the root node. [0165] [Equation 3] (Equence Removed) [0166] Through the above processes, the temporary digraph generation unit 108 can form the temporary digraph I' configured by the directional branch longer than in the AI05 system. This algorithm is based on the fundamental concept of the A06(B) system. The amount of calculation for the terminal device 122 to generate the key can be reduced by applying such algorithm. [0167] (Algorithm) A flow of the process executed by the coordinate axis setting unit 106 and the temporary digraph generation unit 108 will be briefly organized with reference to FIG. 9. The flowchart shown in FIG. 9 shows, by way of example, a method of generating the digraph I'(lv→rv-l) corresponding to the set (lv→rv-l). [0168] (S140) First, the elements of the set (lv→rv-l) are lined so that the inclusion relation becomes larger from the left to the right on the horizontal line. The left most coordinate point is the starting point. Two temporary coordinate points are arranged on the right of the right most coordinate point. The length from the starting point to the right most temporary coordinate point is Lv = rv-lv+1. An integer x (l 1, whether or not #JP(CP)+t < DDT is determined (S168). If not #JP(CP)+t < DDT, the current path CP is determined as the directional path PLP, and the active mark is set to all the directional branches included in the current path (S176). If #JP(CP) +1 < DDT, a natural number j satisfying J = ^ is calculated (SI 70). [0184] The directional branch most distant from the stating point of the current path CP in the directional branches having length J included in the current path CP is extracted (SI72). One directional branch having a length of n(j-1)/k is added immediately after the t directional branches having length n(j-1)/k extending from the starting point of the directional branch extracted in step SI 72, and the directional branch extracted in step S172 is removed (S174), and the process returns to step SI62 to repeatedly execute the above processes. [0185] A loop process between step SI62 and step SI74 is terminated when all the directional paths from the starting point to the ending point of the digraph I' are configured by directional branches having length of one, or when the number of directional branches configuring the directional path exceeds DDT by executing the replacement of greater number of directional branches. [0186] (Details of SI54) The process (SI 80 to S202) of replacing the directional branch included in the temporary digraph I' with the short directional branch will be described in detail below with reference to FIG. 14. [0187] First, the directional branch having the longest length J' is extracted from the active and non-performed (without done mark) directional branch in the graph. If the maximum directional branch exists in plurals, the directional branch most distant from the starting point of the temporary digraph F is selected (SI 80). The selected directional branch is referred to as WJ (Working Jump). The starting point of the directional branch WJ is WJs and the ending point is WJE. The number of directional branches included in the directional path from the starting point to the WJE of the temporary digraph I' is noted as D. [0188] Whether the length J' of the directional branch is J' < 1 is determined (SI 82). If J' < 1, all the directional branches without the active mark are erased, and a collection of all the directional branches with the active mark are set as E(I(a→b)) or E(I(a←b)) (S202). On the other hand, if not J' < 1, the directional path from WJS to WJE-1 is set as the current path CP (SI84). Here, WJE-1 represents the element one before WJE. [0189] The longest directional branch is selected from the directional branches included in the current path CP, and the length thereof is set as J (S186). Whether or not the length J of the directional branch is J < 1 is determined (S188). If J < 1, the active mark is given to all the directional branches included in the current path CP (S198). The done mark is given to the WJ (S200), and the process returns to the process of step S180. If not J < 1, whether or not #JP(CP) +1 < DDT-D is determined (S190). If not #JP(CP) +1 < DDT-D, the process returns to step S180 after the processes of steps S198 and S200. If #JP(CP) +1 < DDT-D, j satisfying J = nj/k is calculated (S192). [0190] If the directional branch having length J included in the current path CP exists in plural, the directional branch at a position most distant from the starting point of the current path CP is extracted (S194). One directional branch having a length of n(j-1)/k is added immediately after the n1/k-l directional branches having length of n(j-1)/k extending from the starting point of the directional branch extracted in step SI 94, and the directional branch extracted in step S194 is erased (SI96). The process returns to the process of step SI 84. [0191] A loop process between step SI84 and step SI96 is terminated when all the directional paths from the WJs to the WJE-1 are configured by directional branches having length of one, or when the number of directional branches included in the directional path from the WJs to the WJE-1 exceeds DDT by replacing greater number of directional branches. The loop process between steps SI80 and S200 is terminated at the point the directional branch not set with done and having a length of greater than or equal to two are all erased from the directional branches included in the temporary digraph F. [0192] The digraph I shown in FIG. 15 is generated by applying the above-described algorithm to the temporary digraph I'. The digraph I is generated for a case of number of contractant n = 64, parameter k = 6. Through the use of such digraph I, the amount of calculation necessary for each terminal device 122 to generate the key, and the number of keys to be held by each terminal device 122 can be reduced compared to the AI05 system. [0193] [Key generation block] The details of the key generation block will be described below with reference again to FIG. 8. The key generation block is mainly configured by the initial intermediate key setting unit 112, the key generation unit 114, and the encryption unit 116. [0194] (Initial intermediate key setting unit 112) The initial intermediate key setting unit 112 generates an intermediate key corresponding to the route of the digraph I of all the intermediate nodes and the root nodes included in the logical binary tree. For instance, the initial intermediate key setting unit 112 may set the intermediate key corresponding to each route by generating the pseudo-random sequence by the PRSG, or may set the intermediate key of each route by a predetermined numerical value. [0194] (Key generation unit 114) The key generation unit 114 generates the intermediate key or the set key using the PRSG. The key generation unit 114 can generate the desired intermediate key or the set key by executing the pseudo-random sequence generation calculation based on the digraph H of the AI05 system, the digraph I of the A06(A+B) system, the digraph of the A06(A) system, the digraph of the A06(B) system, or the digraph of other systems. As described above, when the intermediate key corresponding to the starting end of the directional branch configuring the digraph is input, the PRSG outputs the set key corresponding to such intermediate key and the intermediate key corresponding to the terminating end of such directional branch. If a plurality of directional branches extends from a certain coordinate point on the horizontal coordinate axis of the digraph, a plurality of intermediate keys can be derived by inputting the intermediate key corresponding to such coordinate point. [0196] In the AI05 system, the input and output of the PRSG have been defined with Equation (2), but in the present embodiment, the input and output of the PRSG are defined by t(S1)||...||t(Sk)||k(S0)←PRSG(t(S0)). In other words, the output of the PRSG by the AI05 system is such that the output of (d+l)X, bits with respect to the input of  bits is output when the number of directional branches having the coordinate point corresponding to the input intermediate key as the starting point is d. The PRSG according to the present embodiment, on the other hand, the output of (k+l), bits is output irrespective of the value of d. Here, k is a system parameter. [0197] In thepresent embodiment, when the intermediate key t(S0) corresponding to the subset S0 is input to the PRSG, the output is t(S1)||...||t(Sk)||k(S0). The portion of t(S1)||...||t(Sk) contained in the output is the intermediate key of the corresponding subset S1, ..., Sk for each coordinate point or the ending point of the directional branch having the coordinate point corresponding to the subset S0 as the starting point. The length of the directional branch connecting the coordinate point corresponding to the subset S0 and the coordinate point corresponding to the subset S1 becomes n(i-i)/k. For instance, if the length of the directional branch connecting the coordinate point corresponding to the subset S0 and the coordinate point corresponding to the subset Si is n2/k, the portion of X bits third from the beginning of the output of the PRSG (t(S0)) becomes t(Si). If the directional branch having length of n(j-1)/k does not extend from the coordinate point corresponding to the subset S0, the portion of t(Si) will be output from the PRSG but will not be used. [0198] For instance, when the intermediate key t(S0) corresponding to the coordinate point S0 on the digraph I is input to the PRSG, the key generation unit 114 can derive the intermediate keys t(S1), t(S2), ..., t(Sm) corresponding to the coordinate points S1, S2, ..., Sm of the terminating end and the set key k(S0) for a plurality of directional branches having the coordinate point S0 as the starting end. Here, m indicates the number of directional branches extending from the coordinate point S0. If the intermediate key is not used, the set key k(S0) may be input to the PRSG to derive a plurality of set keys k(S1), k(S2), ..., k(Sm). [0199] (Encryption unit 116) The encryption unit 116 encrypts the content or the content key using the set key, and generates an encrypted text. The encryption unit 116 encrypts the content or the content key using one or more set keys corresponding to a predetermined subset of all the subsets configuring the set system SS. Therefore, a plurality of encrypted texts may be generated with respect to one content or content key. [0200] [Information generation block] The details of the information generation block will be described with reference again to FIG. 8. The information generation block is mainly configured by the subset determination unit 120, and the path information generation unit 121. The communication unit 118 will also be described. [0201] (Subset determination unit 120) The subset determination unit 120 determines the set key for encrypting the content or the content key. That is, the subset determination unit 120 extracts at least one subset including the terminal device 122 of a predetermined permitted contractant, and determines the type of set key to be distributed to each terminal device 122. For instance, the subset determination unit 120 determines the set (R) of the eliminating contractant not permitted to reproduce the content or the content key, and the set (N/R) of the permitted contractant excluding the set (R) of the eliminating contractant from the set (N) of all the contractant. That is, the set (S1, S2,..., Sm) of subsets configuring the set (N/R = S1OS2O .. .OSm) of permitted contractant is determined by the subset contained in the set system SS. [0202] (Path information generation unit 121) The path information generation unit 121 references the information of the directional branches included in the digraph to extract the information of the directional path reaching a predetermined coordinate point from the starting point of the digraph. The predetermined coordinate point is a coordinate point corresponding to each subset selected by the subset determination unit 120. The path information generation unit 121 is an example of a key generation path information extracting unit. [0203] As previously described, the key distribution system such as the AI05 system assumes that all terminal devices 122 hold the information of the digraph or each terminal device 122 calculates the digraph based on the algorithm of each key distribution system. However, this assumption oppresses the memory amount of the terminal device 122 and significantly increases the calculation load, and thus is not realistic. [0204] For instance, in the case of the digraph H (see FIG. 16) of the AI05 system, the terminal device 122 of the contractant 3 holds in advance the intermediate key t(S Si= {SPi, SPi+1, ..., TPi} (2) If the coordinate point S1 is included in the leftward digraph SPi: largest number in the elements of the subset S1 TPI: smallest number in the elements of the subset Si => S1={SPi,SPi.1,...,TPi} (3) If SP;-TPj => S1= {SPi} [0210] Here, SPi and TPi are values greater than or equal to one and smaller than or equal to n. SPi represents the number of the vertical line (number of the contractant) intersecting the starting point of the digraph, and TPi represents the number of the vertical line (number of the contractant) intersecting the coordinate point of the selected subset. [0211] First, the path information generation unit 121 generates the information of the directional path necessary to derive the subset Si and adds the same to the information of the contractant included in the subset Si, as shown with the following Equation (5). The path information generation unit 121 according to the present embodiment adds the information (number of the intersecting vertical line IPIJ; 1 < IPij < n) representing the terminating end of each directional branch contained in the directional path as information of the directional path. Assume that p (p < DDT) directional branches exist in the directional path connecting the coordinate point [SPi,SPj] and the coordinate point [SPi,TPi] on the digraph. [0212] [Equation 5] (Equence Removed) [0213] (Example 1) For instance, consider a case where the subset determination unit 120 selects the subset S = [1,8] in the AI05 system in which the number of contractant is n = 64 and the parameter is k = 6. The path information generation unit 121 generates (see heavy line (directional path) of FIG. 16) S = (1, 2, 4, 8) as information of the subset S including the information of the directional path. [0214] (Example 2) In another example, consider a case where the contractant 45 and the contractant 55 are eliminated in the AI05 system in which the number of contractant is n = 64 and the parameter is k = 6. In this case, if the subset determination unit 120 selects the subsets S1 = [1,44], S2 = [48,46], S3 = [49,54], S4 = [64,56], the path information generation unit 121 generates (see heavy line (directional path) of FIG. 17) the following information in which the information of the directional path is added to each subset. S1 = (1, 2, 4, 8 ,16, 32, 40, 44), 52 = (48, 47, 46), 53 = (49, 50, 52, 54), 54 = (64,63,61, 57, 56). [0215] (Example 3) In another further example, consider a case where the contractant 45 and the contractant 55 are eliminated in the A06(A+B) system in which the number of contractant is n = 64 and the parameter is k = 6. In this case, if the subset determination unit 120 selects the subsets S1 = [1,44], S2 = [48,46], S3 = [49,54], S4 = [64,56], the path information generation unit 121 generates (see heavy line (directional path) of FIG. 18) the following information in which the information of the directional path is added to each subset. S1 = (1, 33, 37, 41, 42, 43,44), 52 - (48, 47, 46), 53 = (49, 53, 54), 54 = (64, 60, 56). [0216] As described above, the information of the directional path is expressed by p+1 number IPij for one subset. S1nce p < DDT and a memory region of log(n) bits is required to express each number IPij, it can be recognized that a maximum of (DDT+l)*log(n) bits is required to represent one subset. However, the value of DDT differs for every key distribution system adopted. For instance, DDT = (2k-l)*(n1/k-l) in the AI05 system, and DDT = k(n1/k-l) in the A06(A+B) system. [0217] (Communication unit 118) The communication unit 118 distributes the content or the content key encrypted by the encryption unit 116 to all terminal devices 122 corresponding to the leaf nodes. The communication unit 118 also distributes a predetermined intermediate key to the terminal device 122 based on the digraph I. In this case, the communication unit 118 distributes the minimum intermediate key such that each terminal device 122 can derive all the intermediate keys corresponding to the subset to which it is included. The communication unit 118 also distributes information of a predetermined digraph to each terminal device 122. Furthermore, the communication unit 118 also distributes the information of the subsets (S1, S2, ..., Sm) configuring the set configuring the set (N/R) of permitted contractant or the set (N/R = S1OS2O...OSm) of the permitted contractant to each terminal device 122. In this case, the communication unit 118 also distributes the information of the directional path added by the path information generation unit 121. [0218] [Configuration of terminal device 122] The configuration of the terminal device 122 according to the present embodiment will now be described with reference to FIG. 19. FIG. 19 is an explanatory view showing the configuration of the terminal device 122. [0219] With reference to FIG. 19, the terminal device 122 is mainly configured by a communication unit 124, a judgment unit 126, a key generation unit 128, and a decryption unit 130. The terminal device 122 corresponds to the above-described user. The communication unit 124 is an example of the key generation path information acquiring unit and the encrypted information acquiring unit. The key generation unit 128 is an example of a key information generation unit. The decryption unit 130 is an example of an encrypted information decryption unit. [0220] (Communication unit 124) The communication unit 124 receives the information distributed from the key distribution server 102. For instance, the communication unit 124 receives information related to content, content key, intermediate key, and digraph, information related to permitted contractant, or the like distributed from the key distribution server 102. The communication unit 124 may also be configured to acquire information from a plurality of information sources (e.g., key distribution server 102) connected to wire or wireless network or an information source (e.g., information media such as optical disc device, magnetic disc device, or portable terminal device) directly or indirectly connected without through the network. [0221] (Judgment unit 126) The judgment unit 126 judges whether or not it is included as an element in one of the subsets corresponding to the set key. The judgment unit 126 judges whether or not it is included in one of the subsets selected by the subset determination unit 120 of the key distribution server 102. In this case, the judgment unit 126 references the information of the subset acquired from the key distribution server 102. [0222] (Key generation unit 128) The key generation unit 128 generates the desired intermediate key or the set key using the intermediate key distributed in advance and the PRSG. In this case, the key generation unit 128 references the information of the directional path acquired from the key distribution server 102, and generates the desired intermediate key or the set key based on the relevant information. If judged that a subset to which it is included does not exist by the judgment unit 126, the generation process of the intermediate key or the set key is terminated. The PRSG is substantially the same as the PRSG held by the key distribution server 102, where when the intermediate key corresponding to the starting end of the directional branch is input based on a predetermined digraph, the set key corresponding to the relevant intermediate key and the intermediate key corresponding to the terminating end of the relevant directional branch are output. It is to be noted that if a plurality of directional branches extends from one coordinate point, a plurality of intermediate keys corresponding to the terminating end of each directional branch is obtained when the intermediate key corresponding to the coordinate point is input. [0223] (Algorithm) The key deriving algorithm by the terminal device 122 of the contractant u will now be described with reference to FIG. 20. FIG. 20 is an explanatory view showing a process in which the terminal device 122 of the contractant u derives the key. This process is mainly executed by the key generation unit 128. [0224] First, the terminal device 122 of the contractant u is provided with information representing m subsets (S1, ..., Sm) selected by the subset determination unit 120 of the key distribution server 102, and information Si = (SPj,IPj,i,...,IPj,(p-i),TPj) (here, j = 1, ..., m) of the directional path added for every subset by the path information generation unit 121. Suppose the judgment unit 126 judges that it is included in the subset Si = [SPj,TPi]. Therefore, the key generation unit 128 references the information Si = (SPi,IPi,i,...,IPi,(P-1),TPi) of the directional path in the process of generating the desired intermediate key or the set key. The process will be specifically described along the flowchart showing in FIG. 20. [0225] With reference to FIG. 20, first, the value of TP; is set to the variable IPi,P (S402). The counter j is then initialized to 1 (S404). Whether or not the terminal device 122 of the contractant u is included in the subset [SPi,JPi,j] is judged (S406). If not included, the counter j is incremented (S408), and the process again returns to step S406. If included, SPj is set to the variable sp and IPi,j is set to the variable ep (S410). In this case, the terminal device 122 of the contractant u holds in advance the intermediate key t([sp,ep]) corresponding to the subset [sp,ep]. [0226] The intermediate key t([sp,ep]) is then set to the variable tcurrent (S412). Whether or not ep = TPi is then judged (S414). If ep = TPi, tcurrent is input to the PRSG, the set key k(correspond to [SPj,TPj])) of the k+lth portion (subset[SPi5TPj] of when the output PRSG (tcurrent) is sectionalized by X bits is taken out (S424), and the generation process of the set key is terminated. [0227] If not ep = TPi, the variable logd (see Equation (6)) is calculated (S416). In other words, logd is a numerical value indicating to what power of n1/k the length of the directional branch from IPjj to IPij+i is. The counter j is then incremented (S418), and IPjj is set to the ep (S420). Then, tcurrent is input to the PRSG, and the logd+lth portion of when the output PRSG (tcurrent) is sectionalized by X bits is set as the new tcurrent (S422). The process thereafter returns to step S414. [0228] [Equation 6] (Equence Removed) [0229] (Decryption unit 130) The decryption unit 130 decrypts the content or the content key using the set key generated by the key generation unit 128. The decryption unit 130 can also execute the process of decrypting the content using the content key. [0230] The configuration of the terminal device 122 according to the present embodiment has been described above. According to the above configuration, the terminal device 122 can generate the desired set key using the information of the directional path acquired from the key distribution server 102. As a result, the terminal device 122 may not hold or generate all the enormous amount of information of the digraph, and the memory amount and the calculation load can be suppressed to a realistic level. [0231]