Patent ID: 8050409

Claim:
A method of generating and distributing keys used to secure communications between a plurality of network nodes each having a unique identity in an ad hoc network having neither a centralized trusted authority nor dedicated nodes to generate and distribute the keys, said method comprising: distributing a key generation mechanism to each network; using the distributed key generation mechanism to generate one unique master private key sub-share per each network node; distributing the master private key sub-shares generated to the respective network nodes; each network node using the distributed sub-shares to compute a share S i of a master private key S, wherein i is i=1, 2, . . . n such that S i represents a respective share of the i th node, wherein n is a total number of network nodes; sharing the share S i of the master private key S among the network nodes along with a common parameter P; using the distributed key generation to generate a master public key Q M using the share S i of the master private key S along with the common parameter P; generating and distributing an individual public key Q ID and an individual private key sk; wherein the generating and distributing of the individual public key Q ID comprises hashing the unique identity of a network node with a time stamp; wherein the generating of the individual private key sk comprises: a requesting node requesting private key generation service from at least k neighbor nodes and presenting the individual public key Q ID and a temporary public key to said k neighbor nodes; each of k neighbor nodes computing a share sk i of the individual private key sk as S i Q ID , where S i (i=1, . . . , k) is the share of the master private key S of the neighbor node and Q ID is the individual public key of the requesting node; each neighbor node encrypting its share sk i of the individual private key sk using the requesting node's temporary public key; each neighbor node sending its encrypted share sk i of the individual private key sk to the requesting node; the requesting node decrypting the encrypted shares of the individual private key sk with a temporary private key corresponding to the temporary public key; and the requesting node computing its individual private key sk as ∑ i = 1 k ⁢ ⁢ sk i = ∑ i = 1 k ⁢ ⁢ S i ⁢ ⁢ Q ID .