Method and apparatus for negotiating Diffie-Hellman keys among multiple parties using a distributed recursion approach

A method of generating a shared secret for a plurality of members of a multicast group to use in a secure communication session, the method comprising the computer-implemented steps of:

• creating and storing a tree that represents the group, wherein each node of the tree is associated with a group member;
• and
• generating the shared secret by traversing the tree in post-order, and at each node of the tree, recursively generating a partial key value for use in the shared secret and a base value for use in subsequent recursive partial key generation, wherein the base value is accumulated and computed by performing at least one exponential operation with an exponent that is a local random number that is associated with a specific node of a specific subtree that is rooted at that node of the tree, by the steps of:
• selecting an initial base value g and prime number value p;
• sending a key computation message that includes the initial base value g and the prime number value p to a first node of a left subtree L that is rooted at the root node;
• forwarding the key computation message to each successor nodes in post-order traversal of the subtree, collecting an accumulated exponent value xj, jεM;
• repeating the sending step and forwarding step for a right subtree R that is rooted at the root node;
• upon completion of the post-order traversal, receiving at the root node a value
• X
• L
• +
• R
• =
• (
• g
• ∏
• j
• ∈
• L
• +
• R
• ⁢
• x
• j
• )
• ⁢
• mod
• ⁢
• p
• computing the shared secret value as
• X
• M
• =
• (
• X
• l
• +
• R
• )
• x
• i
• ⁢
• mod
• ⁢
• p
• =
• g
• ∏
• j
• ∈
• M
• ⁢
• x
• j
• ⁢
• mod
• ⁢
• p
• =
• K
• ;

A computer-readable medium carrying one or more sequences of instructions for generating a shared secret for a plurality of members of a multicast group to use in a secure communication session, which instructions, when executed by one or more processors, cause the one or more processors to carry out the steps of:

• creating and storing a tree that represents the group, wherein each node of the tree is associated with a group member;
• and
• generating the shared secret by traversing the tree in post-order, and at each node of the tree, recursively generating a partial key value for use in the shared secret and a base value for use in subsequent recursive partial key value generation;
• wherein the base value is accumulated and computed by performing at least one exponential operation with an exponent that is a local random number that is associated with a specific node of a specific subtree that is rooted at that node of the tree.

An apparatus for generating a shared secret for a plurality of members of a multicast group to use in a secure communication session, comprising:

• means for creating and storing a tree that represents the group, wherein each node of the tree is associated with a group member;
• and
• means for generating the shared secret by traversing the tree in post-order, and at each node of the tree, recursively generating a partial key value for use in the shared secret and a base value for use in subsequent recursive partial key value generation;
• wherein the base value is accumulated and computed by performing at least one exponential operation with an exponent that is a local random number that is associated with a specific node of a specific subtree that is rooted at that node of the tree.

An apparatus for generating a shared secret for a plurality of members of a multicast group to use in a secure communication session, comprising:

• a network interface that is coupled to the data network for receiving one or more packet flows therefrom;
• a processor;
• one or more stored sequences of instructions which, when executed by the processor, cause the processor to carry out the steps of:
• creating and storing a tree that represents the group, wherein each node of the tree is associated with a group member;
• and
• generating the shared secret by traversing the tree in post-order, and at each node of the tree, recursively generating a partial key value for use in the shared secret and a base value for use in subsequent recursive partial key value generation;
• wherein the base value is accumulated and computed by performing at least one exponential operation with an exponent that is a local random number that is associated with a specific node of a specific subtree that is rooted at that node of the tree.