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

• US 9,071,445 B2
• Filed: 05/03/2013
• Issued: 06/30/2015
• 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:
  US13/887,120
• Publication Number:
  US 20130318342A1
• Time in Patent Office: 788 Days
• Field of Search: 380/30, 380/44, 380/277, 713155-156, 713/175
• US Class Current: 1/1
• 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 a 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;

wherein said implicit certificate, said certificate information and the certification authority'"'"'s public key is configured for subsequent use by the sender computer for allowing the sender computer in reconstructing a public key of the recipient; and

,

wherein said public key of the recipient is configured for subsequent use by the sender computer for allowing the sender computer to encrypt a message with said public key of the recipient and a private key of the sender for transmission of the message to the recipient computer over the communication network.

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

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

4. 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.

5. The computer-implemented method of claim 1, wherein the private key of the sender is determined in dependence upon an indication that said public key is reconstructed from said implicit certificate, said indication including said sender selected identity information.

6. A method of issuing certificates at a certificate authority in an identity based encryption system (IBE) to a sender computer and a recipient computer configured for communicating messages encrypted with identity-based public keys derived from information provided by the certification authority, the method comprising:

receiving, during a registration phase, a first value comprising;

a registration request R and registration information I₁ from the recipient computer which is configured to receive an encrypted message from a sender computer, the registration request derived from a secret value known by the recipient;

receiving, during a publication phase, a request for an implicit certificate P and receiving a second value comprising a second information I₂, the second information associated with the recipient and provided by the sender computer;

generating the implicit certificate at the certificate authority in dependence upon the first value and the second value, the implicit certificate for use by the sender computer in generating the recipient'"'"'s public key B and wherein the recipient'"'"'s public key is for subsequent use by the sender computer in encrypting the message for transmission to the recipient;

receiving, during a privatization phase, a request from the recipient comprising the registration information and the second information to verify the registration request; and

,

providing to the recipient, in response to the request, a private key reconstruction data, for permitting the recipient to decrypt the message provided by the sender.

7. The method of claim 6, wherein the recipient'"'"'s public key is further configured to be generated in dependence upon the implicit certificate and a public key C of the certificate authority.

8. The method of claim 6 wherein generating the implicit certificate P is further in dependence upon identity related information I3 associated with the recipient'"'"'s credentials as provided to the certificate authority.

9. The method of claim 6, wherein the registration request R is confidential between the recipient and the certificate authority.

10. The method of claim 9, wherein the registration request R is derived based on a cryptographic operation on the secret value such that the secret value is confidential to the recipient.

11. The method of claim 10, wherein the registration request R is based on a product of the secret value and a generator point G on an elliptic curve cryptographic system.

12. The method of claim 10, wherein the private key reconstruction data comprises:

the implicit certificate and a secret contribution s.

13. The method of claim 6, wherein the implicit certificate provided to the sender is in determined mathematically by the certification authority from the formula R+kG, wherein R is the registration request, k is a 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.

14. The method of claim 6, wherein the second information provided by the recipient is received from the sender at the recipient.

15. A non-transitory computer readable medium 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 a communication network, the computer readable medium for 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, the computer readable medium comprising instructions for:

providing a recipient'"'"'s registration request from the recipient computer 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 including an identity information of the recipient selected by the sender, generating at the certification authority computer 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;

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

wherein said implicit certificate, said certificate information and the certification authority'"'"'s public key is configured for subsequent use by the sender computer for allowing the sender computer in reconstructing a public key of the recipient; and

,

wherein said public key of the recipient is configured for subsequent use by the sender computer for allowing the sender computer to encrypt a message with said public key of the recipient and a private key of the sender for transmission of the message to the recipient computer over the communication network.

16. The non-transitory computer readable medium of claim 15, further comprising computer readable instructions for:

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.

17. The non-transitory computer readable medium of claim 15, further comprising computer readable instructions for:

transmitting at the recipient computer 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,

providing at the certification authority computer 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.

18. The non-transitory computer readable medium of claim 15, 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.

19. The non-transitory computer readable medium of claim 15, wherein the private key of the sender is determined in dependence upon an indication that said public key is reconstructed from said implicit certificate, said indication including said sender selected identity information.