Threshold and identity-based key management and authentication for wireless ad hoc networks

• US 8,050,409 B2
• Filed: 04/04/2005
• Issued: 11/01/2011
• Est. Priority Date: 04/02/2004
• Status: Expired due to Fees

• Current Assignee: University of Cincinnati
• Original Assignee: University of Cincinnati
• Inventors: Mukherjee, Anindo, Deng, Hongmei, Agrawal, Dharma P.
• Primary Examiner(s): Barron, Jr.; Gilberto
• Assistant Examiner(s): Ho; Virginia T
• Application Number:
  US11/098,250
• Publication Number:
  US 20060023887A1
• Time in Patent Office: 2,402 Days
• Field of Search: 713/156, 380/278, 380/281, 380 44- 47, 380283-285
• US Class Current: 380/278
• CPC Class Codes: H04L 2209/80 Wireless network architectures or network communication protocols for wireless network security H04W12/00
• CPC Class Codes: H04L 63/06 for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 9/083 involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP]
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
• CPC Class Codes: H04L 9/321 involving a third party or a trusted authority
• CPC Class Codes: H04L 9/3263 involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements network architectures or network communication protocols for supporting authentication of entities using certificates in a packet data network H04L63/0823
• CPC Class Codes: H04L 9/3271 using challenge-response
• CPC Class Codes: H04W 12/041 Key generation or derivation
• CPC Class Codes: H04W 12/047 without using a trusted network node as an anchor
• CPC Class Codes: H04W 12/06 Authentication
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

As various applications of wireless ad hoc network have been proposed, security has become one of the big research challenges and is receiving increasing attention. The present invention provides for a distributed key management and authentication approach by deploying the recently developed concepts of identity-based cryptography and threshold secret sharing. Without any assumption of pre-fixed trust relationship between nodes, the ad hoc network works in a self-organizing way to provide the key generation and key management service, which effectively solves the problem of single point of failure in the traditional public key infrastructure (PKI)-supported system. The identity-based cryptography mechanism provided not only to provide end-to-end authenticity and confidentiality, but also saves network bandwidth and computational power of wireless nodes.

Claims

1. 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_iQ_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

2. The method of claim 1, wherein the unique identity comprises an IP address, email address, or name.

3. The method of claim 1, wherein the ad hoc network comprises a wireless ad hoc telecommunications system.

4. The method of claim 1, wherein all network nodes share the master private key S without construction of the master private key at a single node.

5. The method of claim 1, wherein all network nodes share the master private key S in threshold (k, n) fashion, where n is the total number of network nodes and k is minimum number of network nodes required to generate master private key S.

6. The method of claim 1, wherein generation of the master private key S comprises:

each of the network nodes randomly choosing a secret x_i and a polynomial f_i(z) over Zq of degree k−

1, such that f_i(0)=x_i, wherein i is i=1, 2, . . . k such that x_i represents a respective secret of the i^th node;

each of the network nodes computing a sub-share ss_ij of the master private key S for one network node C_j as f_i(j) for j=1, 2. . . n;

each of the network nodes securely sending its sub-share ss_ij of the master private key S to one network node C_j;

node C_j computing a share S_j of the master private key S by adding the sub-shares ss_ij of the master private key S as

7. The method of claim 1, wherein sharing the master private key share comprises publishing S_iP to the network, wherein P is a common parameter.

8. The method of claim 1, wherein the master public key Q_M is computed as

9. The method of claim 1, wherein the neighbor nodes broadcast the requesting node'"'"'s individual public key Q_ID information to the network.

10. The method of claim 1, wherein the neighbor nodes register the requesting node'"'"'s individual public key in register tables.

11. The method of claim 1, wherein any network node that holds a share of the master private key S is a private key generation service node.

12. The method of claim 1, further comprising generation of a master private key share for a node joining the network after network inception.

13. The method of claim 1, wherein secure communications comprises:

a source node sn signing a message to a receiving node rn using its individual private key, encrypting the message using the unique identity of a receiving node, and sending the encrypted message to the receiving node; and

the receiving node rn receiving the encrypted message and decrypting the message using its individual private key and an individual public key of the source node.

14. 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, and

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 a master private key share for a node joining the network after network inception and;

wherein the generation of a master private key share comprises;

joining node C_p generating an individual public key Q_ID;

the joining node C_p presenting its unique identity, individual public key Q_ID, and a required physical proof to k neighbor nodes;

the joining node C_p requesting the master public key Q_M and a share S_P of the master private key S;

each of the k neighbor nodes verifying the unique identity of the joining node C_p;

each of the k neighbor nodes generating a sub-share ss_ip of the master private key S for the joining node C_p as ss_ip=S_i·

l_i(p), where l_i(p) is the Lagrange coefficient;

each of the k neighbor nodes encrypting its sub-share ss_ip of the master private key S using the individual public key Q_ID of the joining node C_p;

each of the k neighbor nodes sending its sub-share of the master private key S to the joining node C_p; and

the joining node C_p computing its new share of the master private key S as

15. The method of claim 14, wherein the sub-shares of the master private key S are shuffled before being sent to the joining node C_p.