Systems and methods for identity-based encryption and related cryptographic techniques
First Claim
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.
7 Assignments
0 Petitions
Accused Products
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 gIDr, 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 dID 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 gIDr, 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.
-
Citations
82 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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 QID of an algebraic group, wherein the element QID is derived from the public identifier ID; and
(c) computing the decryption key dID from the master key and QID using an action of the master key on QID, wherein the decryption key dID is a member of the algebraic group. - View Dependent Claims (8, 9, 10, 11)
-
-
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 ê
;
0×
1>
2, where 0, 1 and 2 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 QIDε
0 from the public identifier ID;
(d) computing a secret message key gε
2 using ê and
QID; and
(e) computing the ciphertext from the message using the message key g. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
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 ê
;
0×
1→
2, where 0, 1 and 2 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 dIDε
0 corresponding to the public identifier ID;
(d) computing a secret message key gε
2 using ê and
the private key dID; and
(e) computing the original message from the ciphertext using the message key g. - View Dependent Claims (25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
-
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 ê
;
1×
1→
2, where 1 and 2 are algebraic groups, and elements P, sPε
1, where sε
is a secret master key;
(b) obtaining a public key xPε
1 corresponding to an intended receiver, where xε
is a secret of the intended receiver;
(c) computing a message key gε
2 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 ê
;
1×
1→
2, where 1 and 2 are algebraic groups, and elements P, sPε
1, where sε
is a secret master key;
(b) computing a message key gε
2 using ê
, sP, a private key x and an element rPε
1 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 ê
;
1×
1→
2, where 1 and 2 are algebraic groups;
(b) obtaining a public key xPε
1 corresponding to an intended receiver of the message, where xε
is a secret of the intended receiver;
(c) computing a message key gε
2 using ê
, the public key xP, the secret master key s, and an element rPε
1 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 ê
;
0×
1→
2, where 0, 1 and 2 are algebraic groups;
(b) selecting a public identifier ID comprising an e-mail address of the receiver;
(c) computing an element QIDε
0 corresponding to the public identifier ID;
(d) computing a message key gε
2 using ê
, QID and a randomly selected secret rε
; and
(e) computing an encrypted message from the message using the message key g. - View Dependent Claims (39)
-
-
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. - View Dependent Claims (42, 43, 44, 45, 46, 47, 48, 49, 50, 51)
- providing a second piece of information;
-
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. - View Dependent Claims (53, 54, 55, 56, 57, 58)
- obtaining a decryption key derived from the encryption key; and
-
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. - View Dependent Claims (60, 61, 66, 67, 68, 69)
- providing an algebraic group having a group action;
-
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 1 and an algebraic group 2; and
providing a system parameter representing a bilinear map ê
mapping pairs of elements of 1 to elements of 2. - View Dependent Claims (75)
- providing a system parameter representing an algebraic group 1 and an algebraic group 2; and
-
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 G1 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. - View Dependent Claims (77, 78, 79)
- encrypting a message to be sent from the sender to the receiver using an encryption key derived in part from a message identifier;
-
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.
- obtaining identifying information of the receiver;
-
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 ê
;
0×
1→
2, where 0, 1 and 2 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 QIDε
0 from the public identifier ID;
(d) a resource that computes a secret message key gε
2 using ê and
QID; 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 ê
;
0×
1→
2, where 0, 1 and 2 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 QIDε
0 from the public identifier ID; and
(d) computing the message key gε
2 using ê and
QID.
-
Specification