Granted Patent B1

US 7,043,024 · App. 09/836,238 · Granted May 9, 2006

Abstract

Claims (51)

1. A method for reducing bandwidth needed to transmit key update information for a plurality of members forming a group, comprising:

(a) associating a subgroup of said group with a leaf node of a hierarchical tree, said leaf node having associated therewith a leaf key common to members of said subgroup, wherein upon eviction of at least one member of said group, said leaf key enables said members of said subgroup to receive an update message for an interior node above said leaf node;

wherein said subgroup is a self-repairing group, said self-repairing group being operative to update said leaf key independently;

wherein each of said members of said subgroup is capable of independently updating a shared interior node key;

wherein said self-repairing uses a reusable power set;

wherein said reusable power set uses a power set of said members in said subgroup as a basis for group key updates;

wherein said reusable power set includes 2 N sets, where N includes the number of said members.

2. The method of claim 1 , wherein said evicted member is not a part of said subgroup.

3. The method of claim 1 , wherein said evicted member is part of said subgroup.

4. The method of claim 1 , wherein said group key updates are performed using a logical key hierarchy method.

5. The method of claim 1 , wherein said group key updates are performed using a one-way function tree method.

6. The method of claim 1 , wherein said group key updates are performed using a one-way function chain method.

7. The method of claim 1 , wherein said hierarchical tree is a binary tree.

8. The method of claim 1 , wherein said updating of said shared interior node key is carried out in a single step.

9. The method of claim 1 , wherein said updating of said shared interior node key is not dependent on key distribution messages from a root node that update further node keys descending from said shared interior node key.

10. A key distribution method, comprising:

(a) evicting at least one member of a group, said group having a plurality of members that share a common node key;

(b) notifying a plurality of members of said group that said at least one member has been evicted; and

(c) determining a new value for said common node key, wherein said determination is capable of being performed independently by said plurality of members of said group;

wherein said plurality of members of said group and said at least one evicted member form a self-repairing group;

wherein each of said members of said group is capable of independently updating the common node key;

wherein said self-repairing group uses a reusable power set;

wherein said reusable power set uses a power set of said members in said self-repairing group as a basis for group key updates;

wherein said reusable power set includes 2 N sets, where N includes the number of said members.

11. The method of claim 10 , wherein said evicting comprises evicting one member of said group.

12. The method of claim 10 , wherein said evicting comprises evicting more than one member of said group.

13. The method of claim 10 , wherein said notifying comprises transmitting identities of said at least one evicted member.

14. A key distribution method, comprising:

(a) grouping a plurality of said members of said group to form a subgroup of said group, said subgroup having a common key known only to said members of said subgroup, said common key being associated with a common node in a hierarchical tree, said subgroup members being operative to independently update said common key upon eviction of one or more members of said subgroup; and

(b) distributing key update messages for said hierarchical tree upon eviction of one or more members of said subgroup, wherein said distributed key update messages do not update keys associated with nodes below said common node;

wherein said subgroup is self-repairing, and each of said members of said subgroup is capable of independently updating the common key;

wherein said self-repairing subgroup uses a reusable power set;

wherein said reusable power set uses a power set of said members in said subgroup as a basis for said key update messages;

wherein said reusable power set includes 2 N −1 sets where N includes the number of said members.

15. The method of claim 14 , wherein said key update messages are based on a logical key hierarchy method.

16. The method of claim 14 , wherein said key update messages are based on a one-way function tree method.

17. The method of claim 14 , wherein said key update messages are based on a one-way function chain method.

18. The method of claim 14 , wherein said hierarchical tree is a binary tree.

19. A secret sharing system, comprising:

a key server that is operative to associate a subgroup of a group having a plurality of members with a leaf node of a hierarchical tree, said leaf node having associated therewith a leaf key common to members of said subgroup, wherein upon eviction of at least one member of said group, said key server uses said leaf key to transmit an update message to said members of said subgroup for a key associated with an interior node above said leaf node;

wherein said subgroup is self-repairing, and each of said members of said subgroup is capable of independently updating a shared interior node key;

wherein said self-repairing subgroup uses a reusable power set;

wherein said reusable power set uses a power set of said members in said subgroup as a basis for said update message;

wherein said reusable power set includes 2 N −1 sets where N includes the number of said members.

20. A computer program product, comprising:

computer-readable program code for causing a computer to associate a subgroup of a group having a plurality of members with a leaf node of a hierarchical tree, said leaf node having associated therewith a leaf key common to members of said subgroup, wherein upon eviction of at least one member of said group, said leaf key enables said members of said subgroup to receive an update message for a key associated with an interior node above said leaf node; and

a computer-usable medium configured to store the computer-readable program codes;

wherein said subgroup is self-repairing, and each of said members of said subgroup is capable of independently updating a shared interior node key;

wherein said self-repairing subgroup uses a reusable power set;

wherein said reusable power set uses a power set of said members in said subgroup as a basis for said update message;

wherein said reusable power set includes 2 N −1 sets, where N includes the number of said members.

Assignments (10)