Data protection system that protects data by encrypting the data

• US 20030182565A1
• Filed: 03/24/2003
• Published: 09/25/2003
• Est. Priority Date: 03/29/2001
• Status: Active Grant

• Current Assignee: Panasonic Corporation (Panasonic Holdings Corporation)
• Original Assignee: Panasonic Corporation (Panasonic Holdings Corporation)
• Inventors: Nakano, Toshihisa, Tatebayashi, Makoto, Ohmori, Motoji, Matsuzaki, Natsume
• Granted Patent: US 7,395,425 B2
• Time in Patent Office: Days
• US Class Current: 713/193
• CPC Class Codes: G06F 21/10 Protecting distributed programs or content, e.g. vending or licensing of copyrighted material protection in video systems or pay television H04N7/16 ; Digital rights management [DRM]
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: G11B 20/00086 Circuits for prevention of unauthorised reproduction or copying, e.g. piracy indicating unauthorised use of record carriers in general G11B23/28; scrambling for television signal recording H04N5/913; network architectures or network protocols for network security H04L63/00; cryptographic mechanisms or cryptographic arrangements for secret or secure communication H04L9/00
• CPC Class Codes: G11B 20/0021 involving encryption or decryption of contents recorded on or reproduced from a record carrier
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 2209/80 Wireless network architectures or network communication protocols for wireless network security H04W12/00
• CPC Class Codes: H04L 2463/101 applying security measures for digital rights management data processing systems or methods, specially adapted for commerce, e.g. marketing, shopping, billing, auctions or e-commerce G06Q30/00
• CPC Class Codes: H04L 63/064 Hierarchical key distribution, e.g. by multi-tier trusted parties
• CPC Class Codes: H04L 63/065 for group communications cryptographic mechanisms or cryptographic arrangements for key management involving conference or group key H04L9/0833
• CPC Class Codes: H04L 9/08 Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords network architectures or network communication protocols for supporting key management in a packet data network H04L63/06
• CPC Class Codes: H04L 9/0822 using key encryption key
• CPC Class Codes: H04L 9/0836 using tree structure or hierarchical structure
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• CPC Class Codes: H04N 2005/91364 the video signal being scrambled
• CPC Class Codes: H04N 21/2347 involving video stream encryption
• CPC Class Codes: H04N 21/26606 for generating or managing entitlement messages, e.g. Entitlement Control Message [ECM] or Entitlement Management Message [EMM] arrangements for conditional access to broadcast information or to broadcast-related services H04H60/14
• CPC Class Codes: H04N 21/4325 by playing back content from the storage medium reproduction of recorded television signals H04N5/76; reproduction of recorded television signals H04N9/79
• CPC Class Codes: H04N 21/4405 involving video stream decryption
• CPC Class Codes: H04N 5/913 for scrambling ; for copy protection
• CPC Class Codes: H04N 7/1675 Providing digital key or authorisation information for generation or regeneration of the scrambling sequence pseudo-random number generators in general G06F7/58

Abstract

The object of the present invention is to provide a data protection system that reduces to a degree the amount of encrypted data that is distributed to a multiplicity of terminals, and that has a structure in which a terminal whose decryption keys are exposed by a dishonest party is made unable to decrypte the data correctly, while other terminals are able to decrypt the data correctly. The present invention is a data protection system that includes a multiplicity of terminals, and an encryption device that encrypts distribution data that is distributed to each terminal. Each terminal is corresponded with one node on a lowest level of 4-ary tree structure or the like that has a plurality of hierarchies. The data protection system, for each node in the tree structure, excluding those on the lowest level, determines a plurality of combination patterns that include combinations of two or more of all four nodes that are reached one level below the node, decides an individual decryption key for each determined combination pattern, further decides an individual decryption key for each node on the lowest level, and has each terminal store all decryption keys decided for the nodes on the path from the node on the lowest level that corresponds to the terminal through to the node on the highest level. The data protection system prescribes reached from the node on the lowest level that corresponds to the terminal through to the node on the highest level that correspond to a terminal that has been dishonestly analyzed as invalid nodes. For invalid nodes, other than invalid nodes on the lowest level, the data protection system designates an encryption key that corresponds to the decryption key decided in correspondence with the combination pattern that combines all nodes, excluding invalid nodes, of the four nodes that are reached one level below the node, and has the encryption device encrypt distribution data that uses each of the designated encryption keys.

Claims

1. A data protection system that comprises three or more terminals, an encryption device, and an encryption key designation device, and protects distribution data that is to be distributed to the terminals, according to the encryption device encrypting the distribution data, characterized in that:

each terminal stores a decryption key group assigned individually to the terminal according to a predetermined key assignment method, obtains an encrypted distribution data group that has been output from the encryption device, and uses a stored decryption key to decrypt encrypted distribution data;

the predetermined key assignment method

(a) determines two or more terminal groups, which are groups having two or more terminals as members, so that each of the terminals is a member of at least one of the terminal groups, and

so that a relationship is satisfied such that any of the terminal groups that shares a same terminal as a member with another one or gore of the terminal groups does not completely include and is not completely included in the other one or more of the terminal groups,

(b) decides one or more decryption keys individually in correspondence with each terminal and each determined terminal group, and

(c) assigns to each terminal the decryption key decided in correspondence with the terminal and all decryption keys decided in correspondence with all terminal groups that include the terminal;

the encryption key designation device designates encryption keys, and includes;

an invalid terminal designation unit for designating one or more terminals as invalid terminals;

an encryption key designation unit,

when all the decryption keys assigned to the terminals, other than decryption keys assigned to the one or more invalid terminals, are prescribed as valid decryption keys, and supposing that a procedure for selecting an assigned valid decryption key for the most terminals to which a selected valid decryption key is not assigned is repeated until all terminals have been assigned a selected valid decryption key,

for designating encryption keys that respectively correspond to all of the valid decryption keys that are selected as a result of the procedure; and

the encryption device includes;

an encryption unit for encrypting distribution data by successively using all the designated encryption keys to encrypt distribution data, generating the encrypted distribution data group, and outputting the generated encrypted distribution data group.

2. The data protection system of claim 1, wherein

the predetermined key assignment method further performs the determining of terminal groups so that a terminal group exists that completely includes the plurality of terminal groups, and

so that a relationship is satisfied such that any plurality of terminal groups within the plurality of terminal groups that shares a same terminal group as a member with another one or more of the terminal groups does not completely include and is not completely included in the other one or more of the terminal groups.

3. The data protection system of claim 2, wherein

the predetermined key assignment method further performs the determining of the terminal groups so that each terminal group includes three or more terminals as members, and

so that a terminal group exists that contains three or more terminal groups.

4. The data protection system of claim 3, comprising:

a key storage device that,

when it is supposed that each terminal is corresponded with a node on a lowest level in an N-ary (N being a natural number equal to or greater than three) tree structure having a plurality of hierarchies,

determines, for each node other than the nodes on the lowest level, a plurality of combination patterns, for each one of N nodes that are reached from the node (parent node), that are combinations of two or more of the N nodes including the one of the N nodes, and that include a combination of all of the N nodes,

decides an individual decryption key for each determined combination pattern and stores each decided decryption key in correspondence with the node (parent node), and

further stores an individual decryption key in correspondence with each node in the lowest level; and

a decryption key determining device that executes the predetermined key assignment method, and that determines the decryption key group that is assigned to each terminal,

determines decryption keys to be assigned to each terminal, the decryption keys being (a) from among the decryption keys stored in the key storage device in correspondence with each node on a same path, the path being a path from the node corresponding to the terminal on the lowest level to a node on the highest level, excluding the node that corresponds to the terminal, all of the combination patterns that include a node that is one level below the node on the same path, and (b) the decryption key stored in the key storage device in correspondence with the terminal, wherein

the terminal groups have a one-to-one correspondence with the combination patterns, and each terminal group is a group whose members are all the terminals that correspond to all nodes on the lowest level that are reached from all the combined nodes in the corresponding combination pattern, and

the encryption key designation unit, when the tree structure is supposed, prescribes all nodes from which a node on the lowest level that corresponds to an invalid terminal is reached as invalid nodes, and performs encryption key designation processing first with a node on the highest level as a processing target node, and repeatedly performs the encryption key designation processing until all processing target nodes have been processed,

wherein the encryption key designation processing is performed on one processing target node at a time that has not been processed, and is processing that

(c) when a combination pattern exists that relates to a combination that includes all nodes, other that invalid nodes, one level below the processing target node, designates a decryption key that corresponds to the decryption key stored by the key storage device in correspondence with the combination pattern,

(d) when a combination pattern does not exist that relates to a combination including all nodes, other than invalid nodes, one level below the processing target node, designates encryption keys stored in correspondence with all the nodes, other than the invalid nodes, by the key storage device in the level one level below if one level below is the lowest level, and if one level below is not the lowest level, newly sets all the nodes one level below, other than invalid nodes, processing target nodes, and

(e) if one or more invalid nodes exists one level below the processing target node, and if the one level below is not the lowest level, newly makes all of the one or more invalid nodes processing target nodes.

5. The data protection system of claim 4, wherein

the determination of the plurality of combination patterns by the key storage device for each node excluding the nodes on the lowest level when the tree structure is supposed, is performed by prescribing combination patterns so that each combination pattern corresponds to one of all combinations of two or more of the N nodes that are one level below and are reached from the node (parent node), and the key storage device stores the determined decryption keys in correspondence with the node (parent node).

6. The data protection system of claim 4, wherein

the determination of the plurality of combination patterns by the key storage device for each node excluding the nodes on the lowest level when the tree structure is supposed, is performed by prescribing combination patterns so that each combination pattern corresponds to one of all combinations of all N of the nodes and (N−

1) of the N nodes that are one level below and are reached from the node (parent node), and the key storage device stores the determined decryption keys in correspondence with the node (parent node).

7. The data protection system of claim 4, wherein

the encryption unit outputs in correspondence, for each encryption key designated by the encryption key designation device, encrypted distribution data generated by encrypting using the designated encryption key, and encryption key node identification information for designating a position in the tree structure of the node that is corresponded by the key storage device with the decryption key corresponding to the encryption key, and

each terminal stores the decryption key that has been individually assigned according to the predetermined key assignment method, in correspondence with decryption key node identifying information of the node with which the decryption key is corresponded, obtains the encrypted distribution data group and an encryption key node identification information group, and decrypts the encrypted distribution data that corresponds to encryption key node identification information that is stored by the terminal and that matches the decryption key node identification, using the decryption key that corresponds with the decryption key node identification information.

8. The data protection system of claim 4, wherein

the encryption key designation device includes:

an encryption key storage unit for storing the corresponding encryption key of each decryption key that is stored by the key storage device,

the corresponding encryption key and decryption key being different.

9. The data protection system of claim 1, wherein

the output by the encryption unit is recording of the generated encrypted distribution data group on at least one data recording medium, and

each terminal reads the encrypted distribution data from one of the at least one data recording mediums, and decrypts the encrypted distribution data.

10. The data protection system of claim 9, wherein

the encryption unit includes:

a content storage unit for storing content data that is a digital work;

a random number generation unit for generating the distribution data that is a random number;

a content encryption unit for encrypting the content data, using the generated distribution data as a key, to generate encrypted content data,

the encryption unit generating an encrypted distribution data group by encrypting the generated distribution data successively using each of the encryption keys designated by the encryption key designation device, and recording the encrypted distribution data group and the generated encrypted content on the at least one data recording mediums, and

each terminal reading the encrypted content and the encrypted distribution data group from one of the at least one recording mediums, decrypting the encrypted distribution data, and using the resulting distribution data to decrypt the encrypted content data.

11. The data protection system of claim 9, further comprising:

an encryption key designation information recording device for recording encryption key designation information that designates the encryption key designated by the encryption key designation device;

each terminal including;

a random number generation unit for generating the distribution data that is a random number;

a content storage unit for storing content data that is a digital work;

an encryption key selection unit for reading the encryption key designation from the data recording medium, and selecting the encryption key designated by the encryption key designation information, from amongst the encryption key group that corresponds to the decryption key group stored by the terminal,

wherein the encryption unit encrypts distribution data by successively using all the encryption keys designated by the encryption keys designated by the encryption designation device to generate an encrypted distribution data group, and outputs the generated encrypted distribution data group.

12. The data protection system of claim 1, wherein

the output according to the encryption unit is transmission of the generated encrypted distribution data group to each terminal, and

each terminal receives the transmitted encrypted distribution data group and decrypts the received encrypted distribution data group.

13. A decryption key determining device that determines decryption key groups for use in decryption to be individually assigned to at least three terminals that obtain encrypted data and decrypt the obtained encrypted data, comprising:

a decryption key setting unit for

(a) determining two or more terminal groups, which are groups having two or more terminals as members, so that each of the terminals is a member of at least one of the terminal groups, and

so that a relationship is satisfied such that any of the terminal groups that shares a same terminal as a member with another one or more of the terminal groups does not completely include and is not completely included in the other one or more of the terminal groups, and

(b) corresponding an individual decryption key with each terminal and each determined terminal group; and

a decryption key group assignment unit for determining, for each terminal, the corresponded decryption key and all the decryption keys corresponded with each terminal group in which the terminal is included, as a decryption key group to be assigned to the terminal.

14. The decryption key determining device of claim 13, wherein

the predetermined key assignment method further performs the determining of terminal groups so that a terminal group exists that completely includes the plurality of terminal groups, and

so that a relationship is satisfied such that any plurality of terminal groups within the plurality of terminal groups that shares a same terminal group as a member with another one or more of the terminal groups does not completely include and is not completely included in the other one or more of the terminal groups.

15. The decryption key determining device of claim 14, wherein

the predetermined key assignment method further performs the determining of the terminal groups so that each terminal group includes three or more terminals as members, and

so that a terminal group exists that contains three or more terminal groups.

16. The decryption key determining device of claim 15, wherein

the decryption key setting unit,

when it is supposed that each terminal is corresponded with a node on a lowest level in an N-ary (N being a natural number equal to or greater than three) tree structure having a plurality of hierarchies,

determines, for each node other than the nodes on the lowest level, a plurality of combination patterns, of reach one of N nodes that are reached from the node (parent node), that are combinations of two or more of the N nodes including the one of the N nodes, and that include a combination of all of the N nodes,

decides an individual decryption key for each determined combination pattern and stores the decided decryption key in correspondence with the node (parent node),

and further stores an individual decryption key in correspondence with each node in the lowest level, and

the decryption key group assignment unit determines decryption keys to be assigned to each terminal, the decryption keys being (a) from among the decryption keys stored in the decryption key setting unit in correspondence with each node on a same path, the path being a path from the node corresponding to the terminal on the lowest level to a node on the highest level, excluding the node that corresponds to the terminal, all the combination patterns that include a node that is one level below the node on the same path, and (b) the decryption key stored in the decryption key setting unit in correspondence with the terminal, wherein

the terminal groups have a one-to-one correspondence with the combination patterns, and each terminal group is a group whose members are all the terminals that correspond to all nodes on the lowest level that are reached from all the combined nodes in the corresponding combination pattern.

17. The decryption key determining device of claim 16, wherein

the determination of the plurality of combination patterns by the key setting unit for each node excluding the nodes on the lowest level when the tree structure is supposed, is performed by prescribing combination patterns so that each combination pattern corresponds to one of all combinations of two or more of the N nodes that are one level below and are reached from the node (parent node), and the decryption key setting unit stores the determined decryption keys in correspondence with the node (parent node).

18. The decryption key determining device of claim 16, wherein

the determination of the plurality of combination patterns by the key setting unit for each node excluding the nodes on the lowest level when the tree structure is supposed, is performed by prescribing combination patterns so that each combination pattern corresponds to one of all combinations of all N of the nodes and (N−

1) of the N nodes that are one level below and are reach from the node (parent node), and the key setting unit stores the determined decryption keys in correspondence with the node (parent node).

19. A decryption key determining method that determines decryption key groups for use in decryption to be individually assigned to at least three terminals that obtain encrypted data and decrypt the obtained encrypted data, comprising:

a terminal group determination step for determining two or more terminal groups, which are groups having two or more terminals as members, so that each of the terminals is a member of at least one of the terminal groups, and

so that a relationship is satisfied such that any of the terminal groups that shares a same terminal as a member with another one or more of the terminal groups does not completely include and is not completely included in the other one or more of the terminal groups;

a decryption key correspondence step for corresponding an individual decryption key with each terminal and each determined terminal group; and

a decryption key group assignment step for determining, for each terminal, the corresponded decryption key and all the decryption keys corresponded with each terminal group in which the terminal is included, as a decryption key group to be assigned to the terminal.

20. A computer program for executing on a computer decryption key determining processing that determines decryption key groups for use in decryption to be individually assigned to at least three terminals that obtain encrypted data and decrypt the obtained encrypted data, the decryption key determining processing comprising:

a terminal group determination step for determining two or more terminal groups, which are groups having two or more terminals as members, so that each of the terminals is a member of at least one of the terminal groups, and

so that a relationship is satisfied such that any of the terminal groups that shares a same terminal as a member with another one or more of the terminal groups does not completely include and is not completely included in the other one or more of the terminal groups;

a decryption key correspondence step for corresponding an individual decryption key with each terminal and each determined terminal group; and

a decryption key group assignment step for determining, for each terminal, the corresponded decryption key and all the decryption keys corresponded with each terminal group in which the terminal is included, as a decryption key group to be assigned to the terminal.

21. A recording medium having stored thereon a computer program for executing on a computer decryption key determining processing that determines decryption key groups for use in decryption to be individually assigned to at least three terminals that obtain encrypted data and decrypt the obtained encrypted data, the decryption key determining processing comprising:

a terminal group determination step for determining two or more terminal groups, which are groups having two or more terminals as members, so that each of the terminals is a member of at least one of the terminal groups, and

so that a relationship is satisfied such that any of the terminal groups that shares a same terminal as a member with another one or more of the terminal groups does not completely include and is not completely included in the other one or more of the terminal groups;

a decryption key correspondence step for corresponding an individual decryption key with each terminal and each determined terminal group; and

a decryption key group assignment step for determining, for each terminal, the corresponded decryption key and all the decryption keys corresponded with each terminal group in which the terminal is included, as a decryption key group to be assigned to the terminal.

22. A decryption terminal system including three or more terminals for obtaining encrypted data and decrypting the obtained encrypted data, each terminal comprising:

a decryption key group storage unit for storing a decryption key group that has been individually assigned to the terminal according to a predetermined key assignment method;

an encrypted data obtaining unit for obtaining encrypted data; and

a decryption unit for decrypting the obtained encrypted data using one of the stored decryption keys,

wherein the predetermined key assignment method

(a) determines two or more terminal groups, which are groups having two or more terminals as members, so that each of the terminals is a member of at least one of the terminal groups, and

so that a relationship is satisfied such that any of the terminal groups that shares a same terminal as a member with another one or more of the terminal groups does not completely include and is not completely included in the other one or more of the terminal groups,

(b) decides one or more decryption keys individually in correspondence with each terminal and each determined terminal group, and

(c) assigns to each terminal the decryption key decided in correspondence with the terminal and all decryption keys decided in correspondence with all terminal groups that include the terminal.

23. The decryption terminal system of claim 22, wherein

the encrypted data obtaining unit obtains the encrypted data by reading the encrypted data from a data recording medium.

24. The decryption terminal system of claim 23, wherein

the data recording medium has recorded thereon encryption key designation information for designating at least one encryption key,

each terminal further includes:

a random number generation unit for generating key data that is a random number;

a content storage unit for storing digital content that is a digital work;

an encryption key selection unit for reading the encryption key designation information from the data recording medium, and selecting from the stored decryption key group at least one decryption key that corresponds to the at least one encryption key designated by the encryption key designation information;

a key data encryption unit for generating an encrypted data group by encrypting the generated key data successively using all of the at least one selected encryption keys, and recording the encrypted key data group on the data recording medium;

a content encryption unit for generating encrypted content data by encrypting the stored content data using the generated key data, and recording the encrypted content data on the data recording medium,

wherein the encryption data obtaining unit obtains the recorded encrypted key data and the recorded encrypted content data,

the decryption unit obtains key data by decrypting the obtained encrypted key data using one of the stored decryption keys, and

each terminal further includes;

a content decryption unit for decrypting the obtained encrypted content data using the generated key data.

25. The decryption terminal system of claim 22, wherein

the encrypted data has been transmitted from an external transmission device, and

the encrypted data obtaining unit obtains the encrypted data by receiving the encrypted data.

26. An encryption key designation device that designates one or more encryption keys to be used in encrypting distribution data that is distributed to three or more terminals, comprising:

a decryption key setting unit for

(a) determining two or more terminal groups, which are groups having two or more terminals as members, so that each of the terminals is a member of at least one of the terminal groups, and

so that a relationship is satisfied such that any of the terminal groups that shares a same terminal as a member with another one or more of the terminal groups does not completely include and is not completely included in the other one or more of the terminal groups, and

(b) deciding one or more decryption keys individually in correspondence with each terminal and each determined terminal group;

a decryption key group correspondence unit for corresponding with each terminal the decryption key decided in correspondence with the terminal and all decryption keys decided in correspondence with all terminal groups that include the terminal;

an invalid terminal designation unit for designating one or more terminals as invalid terminals; and

a encryption key designation unit,

when all the decryption keys corresponded with the terminals by the decryption key group correspondence unit, other than decryption keys assigned to the one or more invalid terminals, are prescribed as valid decryption keys, and supposing that a procedure for selecting an assigned valid decryption key for the most terminals to which a selected valid decryption key is not assigned is repeated until all terminals have been assigned a selected valid decryption key,

for designating encryption keys that respectively correspond to all of the valid decryption keys that are selected as a result of the procedure.

27. The encryption key designation device of claim 26, wherein

the predetermined key assignment method further performs the determining of terminal groups so that a terminal group exists that completely includes the plurality of terminal groups, and

so that a relationship is satisfied such that any plurality of terminal groups within the plurality of terminal groups that shares a same terminal group as a member with another one or more of the terminal groups does not completely include and is not completely included in the other one or more of the terminal groups.

28. The encryption key designation device of claim 27, wherein

the predetermined key assignment method further performs the determining of the terminal groups so that each terminal group includes three or more terminals as members, and

so that a terminal group exists that contains three or more terminal groups.

29. The encryption key designation device of claim 28, wherein

the decryption key setting unit,

when it is supposed that each terminal is corresponded with a node on a lowest level in an N-ary (N being a natural number equal to or greater than three) tree structure having a plurality of hierarchies,

determines, for each node other than the nodes on the lowest level, a plurality of combination patterns, for each one of N nodes that are reached from the node (parent node), that are combinations of two or more of the N nodes including the one of the N nodes, and that include a combination of all of the N nodes,

decides an individual decryption key for each determined combination pattern and stores each decided decryption key in correspondence with the node (parent node), and

further stores an individual decryption key in correspondence with each node in the lowest level;

and

the decryption key group correspondence unit corresponds decryption keys with each terminal, the decryption keys being (a) from among the decryption keys stored in the decryption key setting unit in correspondence with each node on a same path, the path being a path from the node corresponding to the terminal on the lowest level to a node on the highest level, excluding the node that corresponds to the terminal, all of the combination patterns that include a node that is one level below the node on the same path, and (b) the decryption key stored in the decryption key setting unit in correspondence with the terminal, wherein

the terminal groups having a one-to-one correspondence with the combination patterns, and each terminal group being a group whose members are all the terminals that correspond to all nodes on the lowest level that are reached from the combined nodes in the corresponding combination pattern, and

the encryption key designation unit, when the tree structure is supposed, prescribes all nodes from which a node on the lowest level that corresponds to an invalid terminal is reached as invalid nodes, and performs encryption key designation processing first with a node on the highest level as a processing target node, and repeatedly performs the encryption key designation processing until all processing target nodes have been processed,

the encryption key designation processing being processing performed on one processing target node at a time that has not been processed, and being processing that

(c) when a combination pattern exists that relates to a combination that includes all nodes, other that invalid nodes, one level below the processing target node, designates a decryption key that corresponds to the decryption key stored by the decryption key setting unit in correspondence with the combination pattern,

(d) when a combination pattern does not exist that relates to a combination including all nodes, other than invalid nodes, one level below the processing target node, designates encryption keys stored in correspondence with all the nodes, other than the invalid nodes, by the decryption key setting unit in the level one level below if one level below is the lowest level, and if one level below is not the lowest level, newly sets all the nodes one level below, other than invalid nodes, processing target nodes, and

(e) if one or more invalid nodes exists one level below the processing target node, and if the one level below is not the lowest level, newly makes all of the one or more invalid nodes processing target nodes.

30. The encryption key designation device of claim 29, wherein

the determination of the plurality of combination patterns by the decryption key setting unit for each node excluding the nodes on the lowest level when the tree structure is supposed, is performed by prescribing combination patterns so that each combination pattern corresponds to one of all combinations of two or more of the N nodes that are one level below and are reached from the node (parent node), and the decryption key setting unit stores in correspondence with the node (parent node) all combination patterns determined for the node (parent node) as invalidation pattern information that is made by connecting values in a predetermined order, each value showing whether one of the N nodes that are reached from the node (parent node) is a target of combination, and also decides an individual decryption key for each invalidation pattern information and stores the individual decryption key in correspondence with the node (parent node) and the invalidation information for which the individual decryption key has been decided, and

the encryption key designation unit, when the tree structure is supposed, prescribes all nodes that are reached from a node on the lowest level that corresponds to an invalid terminal as invalid nodes, and after designating, for each node excluding the nodes on the lowest level, invalidation information that shows whether the N nodes that are one level below and are reached from the node are invalid nodes, performs the encryption key designation processing,

the encryption key designation processing being performed on one processing target node at a time that has not been processed, and being processing that

(a) when invalidation pattern information exists that matches invalidation information designated for the processing target node, designates an encryption key that corresponds to the decryption key stored by the decryption key setting unit in correspondence with the invalidation pattern information,

(b) when invalidation pattern information does not exist that matches invalidation information designated for the processing target node, designates encryption keys corresponding to the decryption keys stored by the decryption key setting unit in correspondence with all the nodes, other than the invalid nodes, in the level one level below if one level below is the lowest level, and if one level below is not the lowest level, newly makes all the nodes one level below, other than invalid nodes, processing target nodes, and

(c) if an invalid node exists one level below the processing target node, and if the one level below is not the lowest level, newly makes all invalid nodes processing target nodes.

31. The encryption key designation device of claim 29, wherein

the determination of the plurality of combination patterns by the key storage device for each node excluding the nodes on the lowest level when the tree structure is supposed, is performed by prescribing combination patterns so that each combination pattern corresponds to one of all combinations of all N of the nodes and (N−

1) of the N nodes that are one level below and are reached from the node (parent node), and the key storage device stores the determined decryption keys in correspondence with the node (parent node).

32. An encryption device for encrypting distribution data that is to be distributed to three or more terminals, comprising:

a decryption key setting unit for

(a) determining two or more terminal groups, which are groups having two or more terminals as members, so that each of the terminals is a member of at least one of the terminal groups, and

so that a relationship is satisfied such that any of the terminal groups that shares a same terminal as a member with another one or more of the terminal groups does not completely include and is not completely included in the other one or more of the terminal groups, and

(b) deciding one or more decryption keys individually in correspondence with each terminal and each determined terminal group;

a decryption key group correspondence unit for corresponding with each terminal the decryption key decided in correspondence with the terminal and all decryption keys decided in correspondence with all terminal groups that include the terminal;

an invalid terminal designation unit for designating one or more terminals as invalid terminals;

an encryption key designation unit,

when all the decryption keys corresponded with the terminals by the decryption key group correspondence unit, other than decryption keys assigned to the one or more invalid terminals, are prescribed as valid decryption keys, and supposing that a procedure for selecting an assigned valid decryption key for the most terminals to which a selected valid decryption key is not assigned is repeated until all terminals have been assigned a selected valid decryption key,

for designating encryption keys that respectively correspond to all of the valid decryption keys that are selected as a result of the procedure;

an encryption unit for encrypting the distribution data successively using all designated encryption keys, to generate an encrypted distribution data group; and

an output unit for outputting the generated encrypted distribution data externally.

33. The encryption device of claim 32, wherein

the output unit outputs externally key designation information for identifying each encryption key designated by the encryption key designation unit, together with the encrypted distribution data group.

34. The encryption device of claim 32, further comprising:

a content storage unit for storing content data that is a digital work;

a random number generation unit for generating the distribution data, the distribution data being a random number;

a content encryption unit for encrypting the content data using the generated distribution data as a key, to generate encrypted content data; and

an output unit for externally outputting the generated encrypted content data together with the encrypted distribution data group.

35. The encryption device of claim 32, wherein

the output by the output unit is recording of the encrypted distribution data group to a data recording medium.

36. The encryption device of claim 32, wherein

the output by the output unit is transmission of the encrypted distribution data group to each terminal.

37. An encryption key designation method that designates an encryption key to be used in encrypting distribution data that is distributed to three or more terminals, comprising:

a terminal group determination step for

determining two or more terminal groups, which are groups having two or more terminals as members, so that each of the terminals is a member of at least one of the terminal groups, and

so that a relationship is satisfied such that any of the terminal groups that shares a same terminal as a member with another one or more of the terminal groups does not completely include and is not completely included in the other one or more of the terminal groups,

a decryption key group correspondence step for

corresponding one or more decryption keys individually in correspondence with each terminal and each determined terminal group;

a decryption key group correspondence step for corresponding with each terminal, in addition to the decryption key corresponded with the terminal, all decryption keys prescribed in correspondence with all terminal groups that include the terminal;

an invalid terminal designation step for designating one or more terminals as invalid terminals; and

an encryption key designation step,

when all the decryption keys corresponded with the terminals by the decryption key group correspondence step, other than decryption keys assigned to the one or more invalid terminals, are prescribed as valid decryption keys, and supposing that a procedure for selecting an assigned valid decryption key for the most terminals to which a selected valid decryption key is not assigned is repeated until all terminals have been assigned a selected valid decryption key,

for designating encryption keys that respectively correspond to all of the valid decryption keys that are selected as a result of the procedure.

38. A computer program for executing on a computer designation processing that designates one or more encryption keys to be used in encrypting distribution data that is distributed to three or more terminals, the designation processing comprising:

a terminal group determination step for

determining two or more terminal groups, which are groups having two or more terminals as members, so that each of the terminals is a member of at least one of the terminal groups, and

so that a relationship is satisfied such that any of the terminal groups that shares a same terminal as a member with another one or more of the terminal groups does not completely include and is not completely included in the other one or more of the terminal groups,

a decryption key group correspondence step for

corresponding one or more decryption keys individually in correspondence with each terminal and each determined terminal group;

a decryption key group correspondence step for corresponding with each terminal, in addition to the decryption key corresponded with the terminal, all decryption keys prescribed in correspondence with all terminal groups that include the terminal;

an invalid terminal designation step for designating one or more terminals as invalid terminals; and

an encryption key designation step,

when all the decryption keys corresponded with the terminals by the decryption key group correspondence step, other than decryption keys assigned to the one or more invalid terminals, are prescribed as valid decryption keys, and supposing that a procedure for selecting an assigned valid decryption key for the most terminals to which a selected valid decryption key is not assigned is repeated until all terminals have been assigned a selected valid decryption key,

for designating encryption keys that respectively correspond to all of the valid decryption keys that are selected as a result of the procedure.

39. A program recording medium having stored thereon a computer program for executing on a computer designation processing that designates one or more encryption keys to be used in encrypting distribution data that is distributed to three or more terminals, the designation processing comprising:

a terminal group determination step for

determining two or more terminal groups, which are groups having two or more terminals as members, so that each of the terminals is a member of at least one of the terminal groups, and

so that a relationship is satisfied such that any of the terminal groups that shares a same terminal as a member with another one or more of the terminal groups does not completely include and is not completely included in the other one or more of the terminal groups,

a decryption key group correspondence step for

corresponding one or more decryption keys individually in correspondence with each terminal and each determined terminal group;

a decryption key group correspondence step for corresponding with each terminal, in addition to the decryption key corresponded with the terminal, all decryption keys prescribed in correspondence with all terminal groups that include the terminal;

an invalid terminal designation step for designating one or more terminals as invalid terminals; and

an encryption key designation step,

when all the decryption keys corresponded with the terminals by the decryption key group correspondence step, other than decryption keys assigned to the one or more invalid terminals, are prescribed as valid decryption keys, and supposing that a procedure for selecting an assigned valid decryption key for the most terminals to which a selected valid decryption key is not assigned is repeated until all terminals have been assigned a selected valid decryption key,

for designating encryption keys that respectively correspond to all of the valid decryption keys that are selected as a result of the procedure.

40. A computer-readable recording medium having stored thereon a plurality of pieces of encrypted distribution data that have been generated by using each of a plurality of encryption keys to encrypt distribution data that is distributed to three or more terminals, the plurality of encryption keys having been designated by designation processing, the designation processing comprising:

a terminal group determination step for

determining two or more terminal groups, which are groups having two or more terminals as members, so that each of the terminals is a member of at least one of the terminal groups, and

so that a relationship is satisfied such that any of the terminal groups that shares a same terminal as a member with another one or more of the terminal groups does not completely include and is not completely included in the other one or more of the terminal groups,

a decryption key group correspondence step for

corresponding one or more decryption keys individually in correspondence with each terminal and each determined terminal group;

a decryption key group correspondence step for corresponding with each terminal, in addition to the decryption key corresponded with the terminal, all decryption keys prescribed in correspondence with all terminal groups that include the terminal;

an invalid terminal designation step for designating one or more terminals as invalid terminals; and

an encryption key designation step,

when all the decryption keys corresponded with the terminals by the decryption key group correspondence step, other than decryption keys assigned to the one or more invalid terminals, are prescribed as valid decryption keys, and supposing that a procedure for selecting an assigned valid decryption key for the most terminals to which a selected valid decryption key is not assigned is repeated until all terminals have been assigned a selected valid decryption key,

for designating encryption keys that respectively correspond to all of the valid decryption keys that are selected as a result of the procedure.

41. A decryption terminal that obtains encrypted data and decrypts the obtained encrypted data, comprising:

a decryption key group storage unit for storing a decryption key group that has been individually assigned to the terminal according to a predetermined key assignment method;

an encrypted data obtaining unit for obtaining encrypted data; and

a decryption unit for decrypting the obtained encrypted data using one of the stored decryption keys,

wherein the predetermined key assignment method,

(a) when it is supposed that there are three or more terminals including the terminal, determines two or more terminal groups so that the terminal belongs to a plurality of terminal groups, each of which includes two or more terminals as members, and

so that the plurality of terminal groups exist so as to satisfy a relationship that a terminal group that includes the terminal as a member does not completely include and is not completely included in another of the two or more terminal groups,

(b) decides one or more individual decryption keys in correspondence with the terminal and in correspondence with each determined terminal group, and

(c) assigns to the terminal the one or more individual decryption keys decided in correspondence with the terminal and the one or more individual decryption keys decided in correspondence with all the terminal groups that include the terminal.

42. (New claims) A decryption terminal that obtains encrypted data and decrypts the obtained encrypted data, comprising:

decryption key group storage unit for storing a decryption key group that has been individually assigned to the terminal according to a predetermined key assignment method;

encrypted data obtaining unit for obtaining encrypted data; and

decryption unit for decrypting the obtained encrypted data using one of the stored decryption keys,

wherein the predetermined key assignment method

(a) performs a first procedure of determining, for each node other than leaves in an N-ary (N being a natural number equal to or greater than three) tree structure that has a plurality of hierarchies and whose leaves are in one-to-one correspondence with a plurality of decryption terminals that includes the terminal, a plurality of combination patterns that each combine at least two of N nodes that are one level below and are reached from the node (parent node), deciding an individual decryption key for each determined combination pattern, and corresponding the decided decryption keys with the node (parent node),

(b) performs a second procedure of, for each node, other than a leaf, on a path from the leaf corresponding to the terminal to a root, designating from among the decryption keys corresponded with the node by the first procedure, decryption keys that correspond to all the combination patterns that relate to combinations that include a node that is one level below the node on the path, and

(c) assigns the designated decryption keys to the terminal.

43. (New claims) A computer-readable recording medium having stored thereon a plurality of pieces of encrypted distribution data that have been generated by using each of a plurality of encryption keys to encrypt distribution data that is distributed to three or more terminals, the plurality of encryption keys having been designated by designation processing, the designation processing comprising:

a decryption key correspondence step for determining, for each node, other than leaves, in an N-ary (N being a natural number equal to or greater than three) tree structure that has a plurality of hierarchies and whose leaves are in one-to-one correspondence with the terminals, a plurality of combination patterns that each combine at least two of N nodes that are one level below and are reached from the node (parent node), deciding an individual decryption key for each determined combination pattern, and corresponding the decided decryption keys with the node (parent node);

a decryption key group correspondence step for designating, for each terminal, decryption keys to each node, other than a leaf, on a path from the leaf corresponding to the terminal to a root, the decryption keys being from among the decryption keys corresponded with the node by the decryption key correspondence step and corresponding to all the combination patterns that relate to combinations that include a node that is one level below the node on the path, and corresponding all the designated decryption keys with the terminal;

an invalid terminal designation step for designating one or more terminals as invalid terminals; and

an encryption key designation step, when all the decryption keys assigned to the terminals, other than decryption keys assigned to the one or more invalid terminals, are prescribed as valid decryption keys, repeating a procedure for selecting an assigned valid decryption key that is in correspondence with the most terminals to which a selected valid decryption key is not assigned until all terminals have been assigned a selected valid decryption key, and designating encryption keys that correspond to all of the valid decryption keys that are selected as a result of the procedure.