Method and system for generating implicit certificates and applications to identity-based encryption (IBE)

• US 8,457,307 B2
• Filed: 07/10/2008
• Issued: 06/04/2013
• Est. Priority Date: 07/17/2007
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Certicom Corporation (Blackberry Limited)
• Inventors: Vanstone, Scott A.
• Primary Examiner(s): LEMMA, SAMSON B
• Application Number:
  US12/170,658
• Publication Number:
  US 20090046852A1
• Time in Patent Office: 1,790 Days
• Field of Search: 380/30, 380/44, 380/277, 713155-156, 713/175
• US Class Current: 380/30
• CPC Class Codes: H04L 9/3073 involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing
• 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

Abstract

The invention relates to a method of generating an implicit certificate and a method of generating a private key from a public key. The method involves a method generating an implicit certificate in three phases. The public key may be an entity'"'"'s identity or derived from an entity'"'"'s identify. Only the owner of the public key possesses complete information to generate the corresponding private key. No authority is required to nor able to generate an entity'"'"'s private key.

Claims

1. In a communication system comprising at least a certification authority computer of a certification authority, a sender computer of a sender and a recipient computer of a recipient, the certification authority computer, the sender computer and the recipient computer communicating with each other over communication network, a computer-implemented method of transmitting messages encrypted with identity-based public keys derived from information provided by the certification authority, said certification authority having a pair of public and private keys, said method comprising:

the recipient computer providing a recipient'"'"'s registration request to the certification authority computer over the communication network, said registration request correlating to a first secret value selected by the recipient computer;

upon receiving a request from the sender computer, said request from the sender computer including an identity information of the recipient selected by the sender, the certification authority computer generating a public key reconstruction data from said registration request, said identity information selected by the sender, a second secret value selected by the certification authority computer and a certificate information selected by the certification authority computer;

the certification authority computer transmitting an implicit certificate to the sender computer over the communication network, said implicit certificate including said public key reconstruction data and said certificate information;

the sender computer reconstructing a public key of the recipient from said implicit certificate, said certificate information and the certification authority'"'"'s public key;

the sender computer transmitting to the recipient computer over the communication network a message encrypted with said public key of the recipient together with an indication that said public key is reconstructed from said implicit certificate, said indication including said sender selected identity information.

2. The computer-implemented method of claim 1, further including the step of

providing another identity information of the recipient to the certification authority computer over the communication network, said another identity information being selected by the recipient,

wherein said public key reconstruction data incorporates contribution from said another identity information.

3. The computer-implemented method of claim 1, wherein

said certificate information includes a third identity information of the recipient selected by the certification authority computer.

4. The computer-implemented method of claim 1, further comprising:

the recipient computer transmitting a private key request to the certification authority computer, said private key request including all identity information of the recipient used during generating said implicit certificate,

the certification authority computer providing a private key reconstruction data and said public key reconstruction data to the recipient computer, said private key reconstruction data being generated by combining mathematically the certification authority'"'"'s private key, said all identity information, said public key reconstruction data, and said second secret value,

wherein a private key of the recipient is generated by the recipient computer from said implicit certificate, said certification information, said private key reconstruction data and said first secret value.

5. The computer-implemented method of claim 1, further comprising:

the certification authority computer establishing a correspondence between said second secret value and the request from the sender computer.

6. The computer-implemented method of claim 5, wherein said correspondence is established using a secret deterministic function incorporating contributions from all identity information used during generating said implicit certificate.

7. The computer-implemented method of claim 1, wherein an elliptic curve encryption scheme is used, and the public key reconstruction data is determined mathematically by the certification authority computer from the formula R+kG, wherein R is the registration request, k is the second secret value selected by the certification authority computer and G is a generator of an elliptic curve group E selected for the elliptic curve encryption scheme.

8. The computer-implemented method of claim 7, wherein the private key reconstruction data is determined mathematically by the certification authority computer from the formula kh+c mod n, wherein h is a hash value derived from the implicit certificate, c is the certification authority'"'"'s private key and n is the order of the elliptic curve group E.

9. The computer-implemented method of claim 8, wherein the recipient'"'"'s public key is determined mathematically by the sender computer from the formula hP+C and the recipient'"'"'s private key is determined mathematically by the recipient computer from the formula rh+s mod n, wherein P is the public key reconstruction data, C is the certification authority'"'"'s public key, r is the first secret value selected by the recipient computer and s is the private key reconstruction data.

10. A computer-implemented method of providing a recipient'"'"'s public key to a sender computer of a sender and a private key corresponding to said public key to a recipient computer of the recipient, the sender computer, the recipient computer and a certification authority computer of a certification authority communicating with each other over communication network, said method comprising the steps of:

said recipient computer selecting a secret contribution to said public key and generating a registration request information from said secret contribution,

said recipient computer providing said registration request information and a first identify information associated with the recipient to the certification authority computer over the communication network;

said sender computer transmitting to the certification authority computer over the communication network a request for an implicit certificate of the public key, said implicit certificate request including said first identity information and a second identity information of the recipient selected by the sender computer;

the certificate authority computer generating a public key reconstruction data from the registration request information, the first and second identity information, a certificate information selected by the certification authority computer and a private contribution selected by the certification authority computer;

the certification authority computer transmitting said implicit certificate to the sender computer over the communication network, the implicit certificate including said public key reconstruction data and said certificate information;

the sender computer computing the public key from the implicit certificate and the certification authority'"'"'s public key;

upon receiving a private key request from the recipient computer, the certification authority computer providing a privatization information and the implicit certificate to the recipient computer over the communication network; and

the recipient computer computing the private key from the implicit certificate and the privatization information.

11. The computer-implemented method of claim 10, wherein the privatization information is generated by combining mathematically the implicit certificate, the private contribution selected by the certification authority computer and the certification authority'"'"'s private key.

12. In a communication system comprising at least a certification authority computer, a sender computer of a sender and a recipient computer of a recipient, the certification authority computer, the sender computer and the recipient computer communicating with each other over communication network, a computer-implemented method of providing the recipient'"'"'s public key to the sender computer, said public key being based on identity information of the recipient, said method comprising:

the recipient computer providing the recipient'"'"'s registration request to the certification authority computer the communication network, said registration request including the recipient'"'"'s first identity information and registration information correlating to a first secret value selected by the recipient computer;

the recipient computer providing said first identity information to the sender computer over the communication network;

the sender computer transmitting to the certification authority computer over the communication network a request for an implicit certificate, said request including said first identity information and a second identity information of the recipient selected by the sender computer;

the certification authority computer generating a public key reconstruction data from said registration request, said first and second identity information, a third identity information of the recipient selected by the certification authority computer and a second secret value selected by the certification authority computer;

the certification authority computer transmitting an implicit certificate to the sender computer over the communication network, said implicit certificate including said public key reconstruction data and said third identity information; and

the sender computer reconstructing a public key of the recipient from said public key reconstruction data, said first, second and third identity information and the certification authority'"'"'s public key.