Systems and methods for identity-based encryption and related cryptographic techniques

• US 7,113,594 B2
• Filed: 08/13/2002
• Issued: 09/26/2006
• Est. Priority Date: 08/13/2001
• Status: Active Grant

• Current Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.), Regents of the University of California (University of California)
• Original Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.), University of California Davis (University of California)
• Inventors: Boneh, Dan, Franklin, Matthew
• Primary Examiner(s): Smithers, Matthew
• Assistant Examiner(s): FIELDS, COURTNEY D
• Application Number:
  US10/218,697
• Publication Number:
  US 20030081785A1
• Time in Patent Office: 1,505 Days
• Field of Search: 380/28, 380/277, 380/30, 380/280
• US Class Current: 380/28
• CPC Class Codes: H04L 2209/04 Masking or blinding
• CPC Class Codes: H04L 9/0847 involving identity based encryption [IBE] schemes
• 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

Abstract

A method and system for encrypting a first piece of information M to be sent by a sender [100] to a receiver [110] allows both sender and receiver to compute a secret message key using identity-based information and a bilinear map. In a one embodiment, the sender [100] computes an identity-based encryption key from an identifier ID associated with the receiver [110]. The identifier ID may include various types of information such as the receiver'"'"'s e-mail address, a receiver credential, a message identifier, or a date. The sender uses a bilinear map and the encryption key to compute a secret message key g_ID^r, which is then used to encrypt a message M, producing ciphertext V to be sent from the sender [100] to the receiver [110] together with an element rP. An identity-based decryption key d_ID is computed by a private key generator [120] based on the ID associated with the receiver and a secret master key s. After obtaining the private decryption key from the key generator [120], the receiver [110] uses it together with the element rP and the bilinear map to compute the secret message key g_ID^r, which is then used to decrypt V and recover the original message M. According to one embodiment, the bilinear map is based on a Weil pairing or a Tate pairing defined on a subgroup of an elliptic curve. Also described are several applications of the techniques, including key revocation, credential management, and return receipt notification.

Claims

1. In a cryptographic system, a method for sharing an identity-based secret message key between a sender and a receiver, the method comprising:

(a) at a private key generator;

obtaining an element Q of a first algebraic group, wherein Q represents an identity-based public encryption key of the receiver;

computing sQ, where s is an integer representing a secret master key, and where sQ represents a private decryption key of the receiver;

sending sQ to the receiver;

obtaining an element P of a second algebraic group;

computing sP; and

sending sP to the sender;

(b) at the sender;

obtaining the element Q;

obtaining the element P;

obtaining an element sP from the private key generator;

selecting a secret rε

;

computing rP;

computing the secret message key from r, sP, Q, and a bilinear map; and

sending rP to the receiver;

(c) at the receiver;

obtaining rP from the sender;

obtaining sQ from the private key generator; and

computing the secret message key from rP, sQ, and the bilinear map.

2. The method of claim 1 wherein sP and P are system parameters published by the private key generator.

3. The method of claim 1 wherein the bilinear map is an admissible map.

4. The method of claim 1 wherein the bilinear map is a symmetric map and the first algebraic group is equal to the second algebraic group.

5. The method of claim 1 wherein the bilinear map is an asymmetric map.

6. The method of claim 1 wherein obtaining the element Q at the receiver comprises obtaining a public identifier ID associated with the receiver and computing Q from the ID.

7. A method for generating a decryption key based on a public identifier ID, the method comprising:

(a) obtaining a master key and a set of system parameters associated with an identity-based encryption system;

(b) obtaining an element Q_ID of an algebraic group, wherein the element Q_ID is derived from the public identifier ID; and

(c) computing the decryption key d_ID from the master key and Q_ID using an action of the master key on Q_ID, wherein the decryption key d_ID is a member of the algebraic group.

8. The method of claim 7 wherein the algebraic group is a prime-order subgroup of an elliptic curve group.

9. The method of claim 7 wherein computing the decryption key comprises calculating d_ID=sQ_ID, where s represents the master key.

10. The method of claim 7 wherein obtaining the element Q_ID comprises:

obtaining the public identifier ID;

computing the element Q_ID from the public identifier ID.

11. The method of claim 7 wherein the public identifier ID is an identifier selected from the group consisting of the finite combinations of:

a personal name, a name of an entity, a domain name, an IP address, an email address, a social security number, a passport number, a license number, a serial number, a zip code, an address, a telephone number, a URL, a date, a time, a subject, a case, a jurisdiction, a state, a country, a credential, a security clearance level, and a title.

12. A method for encrypting a message in an identity-based cryptosystem to produce corresponding ciphertext, the method comprising:

(a) obtaining a set of parameters associated with a cryptographic system, wherein the parameters comprise a bilinear map ê

;

₀×

₁→

₂, where ₀, ₁ and ₂ are (not necessarily distinct) algebraic groups;

(b) selecting a public identifier ID comprising information identifying an intended receiver of the message;

(c) computing an element Q_IDε

₀ from the public identifier ID;

(d) computing a secret message key gε

₂ using ê and

Q_ID; and

(e) computing the ciphertext from the message using the message key g.

13. The method of claim 12 wherein computing the ciphertext comprises computing a bit mask from the message key g, and masking the message using the bit mask.

14. The method of claim 12 wherein computing the ciphertext comprises computing a bit mask from a hash of a random bit string σ

, masking the message using the bit mask, and masking the random bit string σ

using a hash of the secret message key.

15. The method of claim 12 wherein computing the ciphertext comprises computing an element rPε

₁, where rε

is a randomly selected secret, and where Pε

₁.

16. The method of claim 12 wherein computing the message key also uses rε

, where r is a randomly selected secret.

17. The method of claim 12 wherein computing the secret message key uses an element sPε

₁, where s is a secret master key.

18. The method of claim 12 wherein computing the message key gε

₂ uses multiple elements sPε

₁, where the sare shares of a secret master key.

19. The method of claim 12 wherein computing the element Q_ID comprises:

using a character encoding scheme to map the public identifier ID to a binary string, and hashing the binary string to the element Q_ID of ₀.

20. The method of claim 12 wherein ₀ and ₁ are derived from an elliptic curve defined over a field.

21. The method of claim 20 wherein ê

is derived from a Weil pairing on the elliptic curve.

22. The method of claim 20 wherein ê

is derived from a Tate pairing on the elliptic curve.

23. The method of claim 12 wherein the public identifier ID is an identifier selected from the group consisting of the finite combinations of:

a personal name, a name of an entity, a domain name, an IP address, an email address, a social security number, a passport number, a license number, a serial number, a zip code, an address, a telephone number, a URL, a date, a time, a subject, a case, a jurisdiction, a state, a country, a credential, a security clearance level, and a title.

24. A method for decrypting ciphertext in an identity-based cryptosystem to produce an original message, the method comprising:

(a) obtaining a set of parameters associated with a cryptographic system, wherein the parameters comprise a bilinear map ê

;

₀×

₁→

₂, where ₀, ₁ and ₂ are (not necessarily distinct) algebraic groups;

(b) selecting a public identifier ID comprising information identifying an intended receiver of the message;

(c) obtaining a private key d_IDε

₀ corresponding to the public identifier ID;

(d) computing a secret message key gε

₂ using ê and

the private key d_ID; and

(e) computing the original message from the ciphertext using the message key g.

25. The method of claim 24 wherein computing the original message comprises computing a bit mask from the message key, and unmasking the ciphertext using the bit mask.

26. The method of claim 24 wherein computing the original message comprises unmasking a random bit string or using a hash of the message key, and unmasking the message using a hash of the random bit string σ

.

27. The method of claim 24 wherein the private key d_IDε

₁ is derived from Q_ID and a secret master key s.

28. The method of claim 24 wherein obtaining the private key d_IDε

₁ comprises providing authentication of identity to a private key generator and receiving the private key from the private key generator.

29. The method of claim 24 wherein obtaining the private key d_IDε

₀ corresponding to the public identifier ID comprises obtaining multiple private key portions dε

₀ from multiple corresponding private key generators.

30. The method of claim 24 wherein ₀, ₁ and ₂ are cyclic groups having orders divisible by a prime number q.

31. The method of claim 24 wherein ₀ and ₁ are (not necessarily proper) subgroups of an elliptic curve defined over a field.

32. The method of claim 31 wherein ê

is derived from a Weil pairing on the elliptic curve.

33. The method of claim 31 wherein ê

is derived from a Tate pairing on the elliptic curve.

34. The method of claim 24 wherein the public identifier ID is an identifier selected from the group consisting of the finite combinations of:

a personal name, a name of an entity, a domain name, an IP address, an email address, a social security number, a passport number, a license number, a serial number, a zip code, an address, a telephone number, a URL, a date, a time, a time interval, a subject, a case, a jurisdiction, a state, a country, a credential, a security clearance level, and a title.

35. A method for encrypting a message to produce ciphertext, the method comprising:

(a) obtaining a set of parameters associated with a cryptographic system, wherein the parameters comprise a bilinear map ê

;

₁×

₁→

₂, where ₁ and ₂ are algebraic groups, and elements P, sPε

₁, where sε

is a secret master key;

(b) obtaining a public key xPε

₁ corresponding to an intended receiver, where xε

is a secret of the intended receiver;

(c) computing a message key gε

₂ using ê

, sP, the public key xP, and a randomly selected rε

; and

(d) computing the ciphertext from the message using the message key g.

36. A method for decrypting a ciphertext to produce message, the method comprising:

(a) obtaining a set of parameters associated with a cryptographic system, wherein the parameters comprise a bilinear map ê

;

₁×

₁→

₂, where ₁ and ₂ are algebraic groups, and elements P, sPε

₁, where sε

is a secret master key;

(b) computing a message key gε

₂ using ê

, sP, a private key x and an element rPε

₁ received from a sender, where rε

is a secret of the sender; and

(c) computing the message from the ciphertext using the message key g.

37. A method for decrypting a ciphertext to produce a message, the method comprising:

(a) obtaining a secret master key sε

and a set of parameters associated with a cryptographic system, wherein the parameters comprise an admissible map ê

;

₁×

₁→

₂, where ₁ and ₂ are algebraic groups;

(b) obtaining a public key xPε

₁ corresponding to an intended receiver of the message, where xε

is a secret of the intended receiver;

(c) computing a message key gε

₂ using ê

, the public key xP, the secret master key s, and an element rPε

₁ received from a sender, where rε

is a secret of the sender; and

(d) computing the message from the ciphertext using the message key g.

38. A method for encrypting an e-mail message addressed to a receiver, the method comprising:

(a) obtaining a set of parameters associated with a cryptographic system, wherein the parameters comprise a bilinear map ê

;

₀×

₁→

₂, where ₀, ₁ and ₂ are algebraic groups;

(b) selecting a public identifier ID comprising an e-mail address of the receiver;

(c) computing an element Q_IDε

₀ corresponding to the public identifier ID;

(d) computing a message key gε

₂ using ê

, Q_ID and a randomly selected secret rε

; and

(e) computing an encrypted message from the message using the message key g.

39. The method of claim 38 wherein the public identifier ID further comprises an identifier selected from the group consisting of:

a personal name, a name of an entity, a domain name, an IP address, a social security number, a passport number, a license number, a serial number, a zip code, an address, a telephone number, a URL, a date, a time, a subject, a case, a jurisdiction, a state, a country, a credential, a security clearance level, and a title.

40. A computer-readable storage medium having stored thereon ciphertext comprising:

a first component representing an element computed from a randomly selected secret integer of a sender, and a second component representing a message encrypted by the sender using a secret message key, wherein the secret message key computed by the sender using a bilinear map, the secret integer, and an identity-based public key of an intended receiver.

41. A method of encrypting a first piece of information to be sent by a sender to a receiver, the method comprising:

providing a second piece of information;

generating an encryption key from the second piece of information; and

using a bilinear map and the encryption key to encrypt at least a portion of the first piece of information to be sent from the sender to the receiver.

42. The method of claim 41 wherein the bilinear map is symmetric.

43. The method of claim 41 wherein the bilinear map is admissible.

44. The method of claim 41 wherein the bilinear map is based on a Weil pairing.

45. The method of claim 41 wherein the bilinear map is based on a Tate pairing.

46. The method of claim 41 wherein the second piece of information includes information associated with the receiver.

47. The method of claim 41 wherein the second piece of information comprises an e-mail address.

48. The method of claim 41 wherein the second piece of information includes information corresponding to a time.

49. The method of claim 41 wherein the second piece of information includes a message identifier.

50. The method of claim 41 wherein the second piece of information includes a credential identifier.

51. The method of claim 41 wherein the second piece of information includes a subject identifier for the message.

52. A method of decrypting ciphertext encrypted by a sender with an identity-based encryption key associated with a receiver, the method comprising:

obtaining a decryption key derived from the encryption key; and

using a bilinear map and the decryption key to decrypt at least a portion of the ciphertext.

53. The method of claim 52 wherein the bilinear map is symmetric.

54. The method of claim 52 wherein the bilinear map is admissible.

55. The method of claim 52 wherein the bilinear map is based on a Weil pairing.

56. The method of claim 52 wherein the bilinear map is based on a Tate pairing.

57. The method of claim 52 further comprising:

obtaining the ciphertext prior to obtaining the decryption key.

58. The method of claim 52 wherein obtaining the decryption key comprises sending a request to a private key generator, wherein the request comprises information sent by a sender together with the ciphertext.

59. A method of generating a decryption key corresponding to an encryption key, wherein the encryption key is based on a first piece of information, the method comprising:

providing an algebraic group having a group action;

providing a master key;

generating the encryption key based on the first piece of information; and

generating the decryption key based on the group action applied to the master key and the encryption key.

60. The method of claim 59 wherein the algebraic group is defined by at least a portion of an elliptic curve.

61. The method of claim 59 wherein the first piece of information comprises information associated with an entity.

66. The method of claim 59 wherein the first piece of information includes information corresponding to a time, wherein the decryption key is generated on a user system, and wherein the method further comprises storing the decryption key on a target system.

67. The method of claim 59 wherein the first piece of information includes information corresponding to a responsibility;

and wherein the method further comprises providing respective decryption keys to an entity associated with the responsibility.

68. The method of claim 59 further comprising receiving a request for the decryption key from a receiver, and providing the key to the receiver if the receiver is authenticated.

69. The method of claim 59 wherein the master key is a share of a shared master key.

62. The method of 59 wherein the first piece of information comprises an e-mail address.

63. The method of 59 wherein the decryption key is generated in response to a request from a receiver of an encrypted message, and the first piece of information includes a message identifier.

64. The method of 59 wherein the decryption key is generated in response to a request from a receiver and the first piece of information includes an attribute associated with the receiver.

65. The method of 59 wherein the first piece of information includes information corresponding to a time.

70. A method of providing system parameters for a cryptographic system comprising:

providing a system parameter representing an algebraic group ₁ and an algebraic group ₂; and

providing a system parameter representing a bilinear map ê

mapping pairs of elements of ₁ to elements of ₂.

75. The method of claim 70 wherein the algebraic group G₁ is derived from at least a portion of the elliptic curve y²=x³+1.

71. The method of 70 wherein the bilinear map is symmetric.

72. The method of 70 wherein the bilinear map is based on a Weil pairing.

73. The method of 70 wherein the bilinear map is based on a Tate pairing.

74. The method of 70 wherein the algebraic group G₁ is derived from at least a portion of an elliptic curve.

76. A method for communicating between a sender and a receiver, the method comprising:

encrypting a message to be sent from the sender to the receiver using an encryption key derived in part from a message identifier;

sending the encrypted message from the sender to the receiver;

receiving a request from the receiver for a decryption key, wherein the request includes the message identifier;

after receiving the request for the decryption key, generating receipt information indicating that the receiver has received the message, and providing the decryption key to the receiver.

77. The method of claim 76 comprising:

sending to the sender the generated receipt information.

78. The method of claim 76 wherein the encryption key is derived in part from an identifier associated with the sender.

79. The method of claim 76 wherein the encryption key is derived in part from an identifier associated with the receiver.

80. A method for communicating between a sender and a receiver, the method comprising:

obtaining identifying information of the receiver;

specifying a credential required for the receiver to gain a decryption key;

deriving an encryption key from the identifying information of the receiver and the credential;

encrypting a message using the encryption key and a bilinear map;

sending the encrypted message from a sender to the receiver;

receiving a request from the receiver of the message for a decryption key;

determining whether the receiver has the credential;

if the receiver has the credential, providing the decryption key to the receiver;

decrypting the encrypted message using the decryption key and the bilinear map.

81. A system for encrypting a message in an identity-based cryptosystem to produce corresponding ciphertext, the system comprising:

(a) a resource that obtains a set of parameters associated with a cryptographic system, wherein the parameters comprise a bilinear map ê

;

₀×

₁→

₂, where ₀, ₁ and ₂ are (not necessarily distinct) algebraic groups;

(b) a resource that selects a public identifier ID comprising information identifying an intended receiver of the message;

(c) a resource that computes an element Q_IDε

₀ from the public identifier ID;

(d) a resource that computes a secret message key gε

₂ using ê and

Q_ID; and

(e) a resource that computes the ciphertext from the message using the message key g.

82. An electronic message comprising ciphertext computed from a message and a message key g, wherein g is generated by:

(a) obtaining a set of parameters associated with a cryptographic system, wherein the parameters comprise a bilinear map ê

;

₀×

₁→

₂, where ₀, ₁ and ₂ are (not necessarily distinct) algebraic groups;

(b) selecting a public identifier ID comprising information identifying an intended receiver of the message;

(c) computing an element Q_IDε

₀ from the public identifier ID; and

(d) computing the message key gε

₂ using ê and

Q_ID.