Distributed group key management scheme for secure many-to-many communication

• US 6,240,188 B1
• Filed: 11/11/1999
• Issued: 05/29/2001
• Est. Priority Date: 07/06/1999
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Dondeti, Lakshminath R., Mukherjee, Sarit, Samal, Ashok
• Primary Examiner(s): Swann, Tod
• Assistant Examiner(s): Callahan, Paul E.
• Application Number:
  US09/439,426
• Time in Patent Office: 565 Days
• Field of Search: 380/255, 380/259, 380/260, 380/277, 380/278, 380/283, 380/284, 380/285, 380/286, 380/28, 380/30, 705/50, 705/51, 705/64, 705/71, 713/150, 713/162, 713/163
• US Class Current: 380/284
• CPC Class Codes: G06Q 20/3829 involving key management
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 2209/046 of operations, operands or results of the operations
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/0442 wherein the sending and receiving network entities apply asymmetric encryption, i.e. different keys for encryption and decryption cryptographic mechanisms or cryptographic arrangements for public-key encryption H04L9/30
• 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 63/0823 using certificates cryptographic mechanisms or cryptographic arrangements for entity authentication involving certificates H04L9/3263
• CPC Class Codes: H04L 63/104 Grouping of entities
• 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

Abstract

A group key management system and method for providing secure many-to-many communication is presented. The system employs a binary distribution tree structure. The binary tree includes a first internal node having a first branch and a second branch depending therefrom. Each of the branches includes a first member assigned to a corresponding leaf node. The first member has a unique binary ID that is associated with the corresponding leaf node to which the first member is assigned. A first secret key of the first member is operable for encrypting data to be sent to other members. The first member is associated with a key association group that is comprised of other members. The other members have blinded keys. A blinded key derived from the first secret key of the first member is transmitted to the key association group. Wherein, the first member uses the blinded keys received from the key association group and the first secret key to calculate an unblinded key of the first internal node. The unblinded key is used for encrypting data that is communicated between members located on branches depending from the first internal node.

Claims

1. A distributed group key management system for providing secure communication between a plurality of members, comprising:

a binary distribution tree for defining a communication structure including an internal node having a first branch and a second branch depending therefrom, said internal node having a blinded key and an unblinded key, each of said branches including a first member assigned to a corresponding leaf node, said first member being associated with a key association group comprised of at least one other member;

said first member including;

a unique binary ID associated with the corresponding leaf node to which the first member is assigned;

a first secret key for contributing to the generation of the internal node blinded key; and

a blinded key derived from said first secret key for exchanging with a blinded key of the at least one other member;

wherein said first member uses the blinded key of the at least one other member and the first member first secret key to calculate an unblinded key of the first internal node to be used for encrypting data that is communicated between members located on branches depending from the first internal node.

2. The distributed group key management system of claim 1 wherein said first member further includes a secret key generator for generating said first member first secret key.

3. The distributed group key management system of claim 1 wherein said first member further includes a key association group module for determining the key association group associated with the first member.

4. The distributed group key management system of claim 1 wherein said first member further includes a blinded key module for generating the first member blinded key from the first member first secret key.

5. The distributed group key management system of claim 4 wherein the blinded key module includes a one way function for generating the first member blinded key.

6. The distributed group key management system of claim 1 wherein the first internal node is a root node.

7. The distributed group key management system of claim 1 wherein said first member further includes:

a key association group module for determining the key association group associated with the first member;

a secret key generator for generating the first member first secret key; and

a blinded key module for generating the first member blinded key from the first member first secret key.

8. The distributed group key management system of claim 1 wherein said second branch includes a first member that is a member of the key association group associated with the first branch first member;

and

the first member further includes an unblinded key module having a mixing function for determining the unblinded key of the first internal node from the blinded key of the first branch first member and the blinded key of the second branch first member that is a key association group member associated with the first branch first member.

9. The distributed group key management system of claim 1 wherein said first member further includes;

a key association group module for determining the key association group associated with the first member;

a secret key generator for generating the first member first secret key; and

a blinded key module having a one way function for generating the first member blinded key from the first member first secret key; and

an unblinded key module having a mixing function for determining the unblinded key of the first internal node.

10. A method of providing secure communications between at least two present members, comprising the steps of:

providing a binary tree having at least one internal node and at least two leaf nodes, one of said internal nodes being a root node, each of said internal nodes having two branches extending therefrom, a first branch ending at one of said leaf nodes and another branch ending at another of said leaf nodes, a root path extending from each of said leaf nodes to said root node;

assigning each of said present members to said leaf nodes, whereby each of said present members has a root path extending from a leaf node to said root node;

assigning a binary ID to said internal nodes and leaf nodes;

associating a secret key and a blinded key with each of said leaf nodes, wherein the blinded key is derived from the secret key;

determining a key association group that is associated with a present member for dividing key distribution tasks, the key association group including a group node corresponding to each internal node in the root path of the present member, each group node having an associated member, said present member being assigned to a leaf node in the first branch of said root path internal node, each associated member being assigned to a leaf node in the other branch of said root path internal node;

the present member sending to the associated member of the key association group a blinded key associated with the group node in the first branch of the root path internal node;

the key association group associated member sending to the first member a blinded key associated with the group node in the other branch of the root path internal node;

determining an unblinded key of the root path internal node from the blinded key associated with the other branch group node and the blinded key associated with the first branch group node;

encrypting data with the root path internal node unblinded key; and

communicating the encrypted data between members located on branches depending from the root path internal node.

11. The method of claim 10 wherein the step of associating a secret key further comprises generating the secret key.

12. The method of claim 10 wherein the step of associating a secret key further comprises generating the blinded key from the secret key using a one way function.

13. The method of claim 10 wherein the steps of sending further include using a secure channel.

14. The method of claim 13 wherein the step of using the secure channel further includes using a public key to encrypt the blinded key of the present member and the blinded keys of the associated members.

15. The method of claim 10 wherein the step of determining the root path internal node unblinded key further includes applying a mixing function to the blinded key associated with the second branch node and the blinded key associated with the first branch node.

16. The method of claim 10 further comprising the step of removing a leaving member from the binary tree.

17. The method of claim 16 wherein the step of removing includes the steps of:

updating the binary ID of the present members;

generating a new secret key for a neighbor of the leaving member, wherein the neighbor is the present member located next to the leaving member, said neighbor having a root path and a key association group including at least one associated member;

initiating a swap of blinded keys between the neighbor and the associated member of the key association group of the neighbor, wherein the neighbor initiates the key swap; and

determining the unblinded keys of the internal nodes on the root path of the neighbor.

18. The method of claim 10 further comprising the step of joining a new member to the binary tree.

19. The method of claim 18 wherein the step of joining further comprises:

sending a request to join from the new member to a local member of said present members;

granting the request to join;

splitting the binary ID of the local member into a first ID and a second ID, wherein the first ID is assigned to the local member and the second ID is assigned to the new member;

generating a new secret key for the local member;

generating a first secret key for the new member;

generating a blinded key of the local member from the new secret key;

generating a blinded key of the new member from the first secret key;

exchanging the blinded key of the new member with the blinded key of the local member;

determining a key association group that is associated with the new member for dividing key distribution tasks, the new member key association group including a group node corresponding to each internal node in the root path of the new member, said new member being assigned to a leaf node in the first branch of said root path internal node, said group node having an associated member, each associated member being assigned to a leaf node in the other branch of the root path internal node of the new member;

the new member sending to the associated member of the new member key association group a blinded key associated with a first node in the first branch of the root path internal node;

the new member key association group associated member sending to the new member a blinded key associated with the group node in the other branch of the root path internal node; and

determining an unblinded key of the new member root path internal node from the blinded key associated with the new member other branch group node and the blinded key associated with the new member first node.

20. A method of joining a new member to a distributed communications system for secure communications between a plurality of local members, comprising the steps of:

providing a binary tree having at least one internal node and at least two leaf nodes, one of said internal nodes being a root node, each of said internal nodes having two branches extending therefrom, a first branch extending to at least one of said leaf nodes, and a second branch extending to at least another of said leaf nodes, a root path extending from each of said leaf nodes to said root node;

each of said local members having a binary ID, and being assigned to a leaf node;

sending a request to join from a new member to one of said local members of the communications system;

determining a key association group that is associated with the local member for dividing key distribution tasks, the local member key association group including a group node corresponding to each internal node in the root path of the local member, said local member being assigned to a leaf node in the first branch of said root path internal node, said group node having an associated member, each associated member being assigned to a leaf node in the other branch of the root path internal node of the local member;

granting the request to join;

splitting the binary ID of the local member into a first ID and a second ID, wherein the first ID is assigned to the local member and the second ID is assigned to the new member;

generating a local member new secret key;

generating a new member first secret key;

generating a local member blinded key from the local member new secret key;

generating a new member blinded key from the new member first secret key;

sending the new member blinded key to the local member;

sending the local member blinded key to the new member;

calculating the blinded key and the unblinded key of the local member root path internal node;

sending the local member root path internal node blinded key to the local member key association group associated member corresponding to the group node corresponding to the local member root path internal node;

sending a blinded key of the group node corresponding to the local member root path internal node to the local member; and

forwarding the group node blinded key corresponding to the local member root path internal node to the new member.

21. The method of claim 20 wherein the step of sending the new member blinded key further comprises unicasting the blinded key of the new member to the local member.

22. The method of claim 20 wherein the step of sending the group node blinded key further comprises unicasting the group node blinded key to the local member.

23. The method of claim 20 wherein said internal nodes further include a blinded key further comprising the steps of:

maintaining a version associated with the blinded key of the internal node;

receiving the blinded key of the internal node;

determining whether more than one version of the internal node blinded key has been received; and

using a mixing function to combine the versions of the internal node blinded key.

24. The method of claim 20 wherein each of said internal nodes further includes an old blinded key, further comprising the steps of:

receiving a new blinded key corresponding to an internal node; and

applying a mixing function to the old blinded key and the new blinded key.

25. The method of claim 20 wherein the binary ID includes a length, further comprising the step of:

determining the present member having the binary ID with the shortest length;

wherein the binary ID of the present member with the shortest length binary ID is split into the first ID and the second ID.

26. A method of merging a first secure communications system with a second secure communications system, each of said communications systems including a plurality of members having a binary ID, each of said communications systems having a binary tree structure with a root node, said root node having a blinded key, comprising the steps of:

sending a request to merge the first communications system with the second communications system;

granting the request to merge;

using a mixing function to combine the blinded key of the first communications system root node with the blinded key of the second communications system root node;

appending a 1 to the binary ID of said first communications system plurality of members; and

appending a 0 to the binary ID of each member of the second communications system.

27. A distributed group key management system for providing secure communication between a plurality of members, comprising:

at least one sender binary distribution tree for forming a senders group;

said at least one sender binary distribution tree defining a communication structure having a sender internal node with a first branch and a second branch depending therefrom, each of said branches including a first member assigned to a corresponding leaf node, said first member being associated with a key association group including at least one other member;

said senders group first member including;

a unique binary ID associated with the corresponding leaf node to which the senders group first member is assigned;

a first secret key; and

a blinded key derived from said first secret key for exchanging with a blinded key of the other senders group member;

wherein said senders group first member uses the blinded key of the at least one other senders group member and the first secret key to calculate an unblinded key of the sender internal node to be used for encrypting and decrypting sending group data that is communicated between sending group members located on branches depending from the sender internal node; and

at least one receiver binary distribution tree for forming a receivers group, said receivers group including at least one sender for communicating with said senders group;

said at least one receiver binary distribution tree defining a communication structure having a receiver internal node with a first branch and a second branch depending therefrom, each of said branches including a first member assigned to a corresponding leaf node, said first member being associated with a key association group including at least one other member;

said receivers group first member including;

a unique binary ID associated with the corresponding leaf node to which the receivers group first member is assigned;

a first secret key operable for encrypting data; and

a blinded key derived from said first secret key for exchanging with a blinded key of the other receivers group member;

wherein, each of said senders is one of said senders group first members and one of said receivers group first members, said sender uses the blinded key of the other receivers group member and the first secret key of the sender to calculate an unblinded key of the receiver internal node to be used for encrypting and decrypting receivers group data that is communicated between said receivers group members located on branches depending from the receiver internal node.

28. The distributed group key management system of claim 27 wherein the receivers group data and the senders group data is a session key for decrypting second data that is encrypted with the session key.

29. The distributed group key management system of claim 27 wherein the receivers group data and the senders group data is communications data for communicating between senders group members and receivers group members.