Certificate-based encryption and public key infrastructure

• US 7,657,748 B2
• Filed: 08/28/2003
• Issued: 02/02/2010
• Est. Priority Date: 08/28/2002
• Status: Expired due to Fees

• Current Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Original Assignee: NTT Docomo Incorporated (Nippon Telegraph and Telephone Corporation)
• Inventors: Gentry, Craig B.
• Primary Examiner(s): Barron, Jr.; Gilberto
• Assistant Examiner(s): ARMOUCHE, HADI S
• Application Number:
  US10/521,741
• Publication Number:
  US 20050246533A1
• Time in Patent Office: 2,350 Days
• Field of Search: 380/28, 380/30, 380/286, 713/170, 713/173, 713/176
• US Class Current: 713/170
• CPC Class Codes: H04L 9/0836 using tree structure or hierarchical structure
• 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
• CPC Class Codes: H04L 9/3265 using certificate chains, trees or paths; Hierarchical trust model

Abstract

A digital message is sent from a sender to a recipient in a public-key based cryptosystem comprising an authorizer. The authorizer can be a single entity or comprise a hierarchical or distributed entity. In some embodiments, no key status queries or key escrow are needed. The recipient can decrypt the message only if the recipient possesses up-to-date authority from the authorizer. Other features are also provided.

Claims

1. A method for operating a public-key encryption scheme which provides for sending a digital message M between a sender and a recipient with participation of an authorizer, wherein the digital message is encrypted by the sender and decrypted by the recipient, the method comprising encrypting, by at least one machine in a set of one or more machines, the digital message M using at least a recipient public key RPUB and a recipient encryption key RENC to create an encrypted digital message for decryption with a recipient private key RPRIV and a recipient decryption key RDEC, wherein:

the recipient public key RPUB and the recipient private key RPRIV form a public key/private key pair 1, wherein the recipient private key RPRIV is a secret of the recipient;

the recipient decryption key RDEC is generated using at least a key generation secret of the authorizer and the recipient encryption key RENC, wherein a key formed from the recipient encryption key RENC and a key formed from the recipient decryption key RDEC are a public key/private key pair 2;

wherein the recipient decryption key RDEC is generated by the authorizer to have a value S=s_cP_B, wherein;

s_c is the key generation secret of the authorizer; and

P_B is the recipient encryption key RENC and is equal to H₁(Inf_B), wherein Inf_B is an element of a first cyclic group G₁ of elements, wherein P_B is an element of a second cyclic group G₂ of elements, and H₁ is a predefined function (“

first function H₁”

), wherein the first and second cyclic groups G₁ and G₂ and the function H₁ are system parameters made available to the sender, and also available to the sender are system parameters comprising;

a generator P of the first cyclic group G₁;

a key generation parameter Q=s_cP;

a second function H₂ capable of generating a second string of binary digits from an element of the second cyclic group G₂,

wherein Inf_B comprises the identity of the recipient, ID_rec, the recipient public key RPUB, and a parameter defining a validity period for the recipient decryption key RDEC.

2. The method of claim 1, wherein the recipient encryption key RENC is generated from information comprising the identity of the recipient.

3. The method of claim 1, wherein the recipient encryption RENC key is generated from information comprising a parameter defining a validity period for the recipient decryption key RDEC.

4. The method of claim 1, wherein the recipient encryption key RENC is generated from information comprising the recipient public key RPUB.

5. The method of claim 1, wherein the recipient encryption key RENC is generated from information comprising the identity of the recipient, the recipient public key RPUB, and a parameter defining a validity period for the recipient decryption key RDEC.

6. The method of claim 1, wherein the recipient decryption key RDEC is generated by the authorizer according to a schedule known to the sender.

7. The method of claim 6, wherein the recipient encryption key RENC is generated using at least information comprising the schedule.

8. The method of claim 1, wherein the recipient private key RPRIV and the recipient public key RPUB are generated using at least one system parameter issued by the authorizer.

9. The method of claim 1, wherein both the first group G₁ and the second group G₂ are of the same prime order q.

10. The method of claim 1, wherein the first cyclic group G₁ is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group G₂ is a multiplicative subgroup of a finite field.

11. The method of claim 1 wherein the system parameters available to the sender further comprise a function ê

which is a bilinear, non-degenerate, and efficiently computable pairing which maps G₁×

G₁ into G₂.

12. The method of claim 9 wherein:

s_c is an element of the cyclic group Z/qZ.

14. The method of claim 1, wherein the recipient encryption key RENC is generated from a document and the recipient decryption key RDEC is the authorizer'"'"'s signature on the document.

16. The method of claim 1, wherein the method further comprises the recipient performing, by at least one machine in the set of the one or more machines, operations of:

generating the recipient public key RPUB and the recipient private key RPRIV;

decrypting the encrypted digital message using at least the recipient private key RPRIV and the recipient decryption key RDEC.

17. The method of claim 1 wherein the method further comprises the authorizer selecting, by at least one machine in the set of the one or more machines, said key generation secret and generating the recipient decryption key RDEC and sending the recipient decryption key to the recipient.

18. The method of claim 17 wherein the method further comprises the recipient performing, by at least one machine in the set of the one or more machines, operations of:

generating the recipient public key RPUB and the recipient private key RPRIV;

decrypting the encrypted digital message using at least the recipient private key RPRIV and the recipient decryption key RDEC.

19. The method of claim 1 further comprising generating, by at least one machine in the set of the one or more machines, the recipient encryption key RENC by the authorizer and/or the recipient and/or the sender.

20. The method of claim 2 further comprising generating, by at least one machine in the set of the one or more machines, the recipient encryption key RENC.

21. The method of claim 3 further comprising generating, by at least one machine in the set of the one or more machines, the recipient encryption key RENC.

22. The method of claim 4 further comprising generating, by at least one machine in the set of the one or more machines, the recipient encryption key RENC.

23. The method of claim 5 further comprising generating, by at least one machine in the set of the one or more machines, the recipient encryption key RENC.

24. The method of claim 6 wherein the method further comprises the authorizer selecting, by at least one machine in the set of the one or more machines, said key generation secret and generating, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC and sending, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC to the recipient.

25. The method of claim 7 further comprising generating, by at least one machine in the set of the one or more machines, the recipient encryption key RENC.

26. The method of claim 4 wherein the method further comprises the authorizer selecting, by at least one machine in the set of the one or more machines, said key generation secret and generating, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC and sending, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC to the recipient.

28. The method of claim 9, wherein the method further comprises the authorizer selecting, by at least one machine in the set of the one or more machines, said key generation secret and generating, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC and sending, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC to the recipient.

29. The method of claim 10, wherein the method further comprises the authorizer selecting, by at least one machine in the set of the one or more machines, said key generation secret and generating, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC and sending, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC to the recipient.

30. The method of claim 11 wherein the method further comprises the authorizer selecting, by at least one machine in the set of the one or more machines, said key generation secret and generating, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC and sending, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC to the recipient.

32. The method of claim 14, wherein the method further comprises the authorizer selecting, by at least one machine in the set of the one or more machines, said key generation secret and generating, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC and sending, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC to the recipient.

33. The method of claim 14, wherein the method further comprises the recipient performing, by at least one machine in the set of the one or more machines, operations of:

generating the recipient public key RPUB and the recipient private key RPRIV;

decrypting the encrypted digital message using at least the recipient private key RPRIV and the recipient decryption key RDEC.

37. The method of claim 14, If further comprising generating, by at least one machine in the set of the one or more machines, the recipient encryption key RENC.

39. The method of claim 6 further comprising generating, by at least one machine in the set of the one or more machines, the recipient encryption key RENC.

40. The method of claim 8 further comprising generating, by at least one machine in the set of the one or more machines, the recipient encryption key RENC.

41. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 1.

42. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 5.

43. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 9.

44. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 11.

46. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 14.

51. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 16.

52. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 17.

53. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 18.

54. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 19.

55. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 22.

56. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 25.

58. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 33.

61. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 37.

62. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 39.

13. A method for operating a public-key encryption scheme which provides for sending a digital message M between a sender and a recipient with participation of an authorizer, wherein the digital message is encrypted by the sender and decrypted by the recipient, the method comprising encrypting, by at least one machine in a set of one or more machines, the digital message M using at least a recipient public key RPUB and a recipient encryption key RENC to create an encrypted digital message for decryption with a recipient private key RPRIV and a recipient decryption key RDEC, wherein:

the recipient public key RPUB and the recipient private key RPRIV form a public key/private key pair 1, wherein the recipient private key RPRIV is a secret of the recipient;

the recipient decryption key RDEC is generated using at least a key generation secret of the authorizer and the recipient encryption key RENC, wherein a key formed from the recipient encryption key RENC and a key formed from the recipient decryption key RDEC are a public key/private key pair 2;

wherein the recipient decryption key RDEC is generated by the authorizer to have a value S=s_cP_B, wherein;

s_c is the key generation secret of the authorizer; and

P_B is the recipient encryption key RENC and is equal to H₁(Inf_B), wherein Inf_B is an element of a first cyclic group G₁ of elements, wherein P_B is an element of a second cyclic group G₂ of elements, and H₁ is a predefined function (“

first function H₁”

), wherein the first and second cyclic groups G₁ and G₂ and the function H₁ are system parameters made available to the sender, and also available to the sender are system parameters comprising;

a generator P of the first cyclic group G₁;

a key generation parameter Q=s_cP;

a second function H₂ capable of generating a second string of binary digits from an element of the second cyclic group G₂;

wherein encrypting the digital message M comprises;

generating an element P′

_B=H_1′

(ID_rec), wherein ID_rec comprises the identity of the recipient and wherein H_1′

is a function capable of generating an element of the first cyclic group G₁ from a string of binary digits;

selecting a random key generation secret r; and

encrypting the digital message M to form a ciphertext C, wherein C is set to be;

C=[rP, M⊕

H₂(g^r)], where g=ê

(Q, P_B)ê

(PK_B, P′

_B)∈

G₂, where PK_B is the recipient public key RPUB and wherein ê

is a bilinear non-degenerate pairing which maps G₁×

G₁ into G₂.

27. The method of claim 13 wherein the method further comprises the authorizer selecting, by at least one machine in the set of the one or more machines, said key generation secret and generating, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC and sending, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC to the recipient.

34. The method of claim 13, wherein the method further comprises the recipient performing, by at least one machine in the set of the one or more machines, operations of,

generating the recipient public key RPUB and the recipient private key RPRIV;

and

decrypting the encrypted digital message to recover the digital message using at least the recipient private key RPRIV and the recipient decryption key RDEC.

36. The method of claim 13, further comprising generating, by at least one machine in the set of the one or more machines, the recipient encryption key RENC.

45. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 13.

48. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 27.

50. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 36.

59. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 34.

60. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 36.

15. A method for operating a public-key encryption scheme which provides for sending a digital message M between a sender and a recipient with participation of an authorizer, wherein the digital message is encrypted by the sender and decrypted by the recipient, the method comprising encrypting, by at least one machine in a set of one or more machines, the digital message M using at least a recipient public key RPUB and a recipient encryption key RENC to create an encrypted digital message for decryption with a recipient private key RPRIV and a recipient decryption key RDEC, wherein:

the recipient public key RPUB and the recipient private key RPRIV form a public key/private key pair 1, wherein the recipient private key RPRIV is a secret of the recipient;

the recipient decryption key RDEC is generated using at least a key generation secret of the authorizer and the recipient encryption key RENC, wherein a key formed from the recipient encryption key RENC and a key formed from the recipient decryption key RDEC are a public key/private key pair 2;

wherein the recipient decryption key RDEC is generated by the authorizer to have a value S=s_cP_B, wherein;

s_c is the key generation secret of the authorizer; and

P_B is the recipient encryption key RENC and is equal to H₁(Inf_B), wherein Inf_B is an element of a first cyclic group G₁ of elements, wherein P_B is an element of a second cyclic group G₂ of elements, and H₁ is a predefined function (“

first function H₁”

), wherein the first and second cyclic groups G₁ and G₂ and the function H₁ are system parameters made available to the sender, and also available to the sender are system parameters comprising;

a generator P of the first cyclic group G₁;

a key generation parameter Q=s_cP;

a second function H₂ capable of generating a second string of binary digits from an element of the second cyclic group G₂;

wherein both the first group G₁ and the second group G₂ are of the same prime order q;

wherein encrypting the digital message M comprises;

generating an element P′

_B=H_1′

(ID_rec), wherein H_1′

is a function capable of generating an element of the first cyclic group G₁ from a string of binary digits;

choosing a random parameter σ

∈

{0,1}ⁿ;

set a random key generation secret r=H₃(σ

, M); and

encrypting the digital message M to form a ciphertext C, wherein C is set to be;

C=[rP, M⊕

H₂(g^r), E<sub>H4(σ

)</sub>(M)], where g=ê

(Q, P_B)ê

(PK_B, P′

_B)∈

G₂, wherein PK_B is the recipient public key RPUB, wherein H₃ is a function capable of generating an integer of the cyclic group Z/qZ from two strings of binary digits, H₄ is a function capable of generating one binary string from another binary string, E is a symmetric encryption scheme, ê

is a bilinear non-degenerate pairing which maps G₁×

G₁ into G₂, and H₄(σ

) is the key used with E.

31. The method of claim 15 wherein the method further comprises the authorizer selecting, by at least one machine in the set of the one or more machines, said key generation secret and generating, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC and sending, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC to the recipient.

35. The method of claim 15 further comprising the recipient performing, by at least one machine in the set of the one or more machines, operations of,

generating the recipient public key RPUB and the recipient private key RPRIV;

and

decrypting the encrypted digital message to recover the digital message using at least the recipient private key RPRIV and the recipient decryption key RDEC.

38. The method of claim 15 further comprising generating, by at least one machine in the set of the one or more machines, the recipient encryption key RENC.

47. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 15.

49. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 35.

57. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 31.

63. A method for operating a public-key encryption scheme which provides for sending a digital message M between a sender and a recipient with participation of an authorizer, wherein the digital message M is encrypted by the sender using at least a recipient public key RPUB and a recipient encryption key RENC to create an encrypted digital message and is decrypted by the recipient, the method comprising decrypting, by at least one machine in a set of one or more machines, the encrypted digital message using at least a recipient private key RPRIV and a recipient decryption key RDEC, wherein:

the recipient public key RPUB and the recipient private key RPRIV form a public key/private key pair 1, wherein the recipient private key RPRIV is a secret of the recipient;

the recipient decryption key RDEC is generated using at least a key generation secret of the authorizer and the recipient encryption key RENC, wherein a key formed from the recipient encryption key RENC and a key formed from the recipient decryption key RDEC are a public key/private key pair 2;

wherein the recipient decryption key RDEC is generated by the authorizer to have a value S=s_cP_B, wherein;

s_c is the key generation secret of the authorizer; and

P_B is the recipient encryption key RENC and is equal to H₁(Inf_B), wherein Inf_B is an element of a first cyclic group G₁ of elements, wherein P_B is an element of a second cyclic group G₂ of elements, and H₁ is a predefined function (“

first function H₁”

), wherein the first and second cyclic groups G₁ and G₂ and the function H₁ are system parameters made available to the sender, and also available to the sender are system parameters comprising;

a generator P of the first cyclic group G₁;

a key generation parameter Q=s_cP;

a second function H₂ capable of generating a second string of binary digits from an element of the second cyclic group G₂,

wherein Inf_B comprises the identity of the recipient, ID_rec, the recipient public key RPUB, and a parameter defining a validity period for the recipient decryption key RDEC.

64. The method of claim 63, wherein the recipient encryption key RENC is generated from information comprising the identity of the recipient.

65. The method of claim 63, wherein the recipient encryption key RENC is generated from information comprising a parameter defining a validity period for the recipient decryption key RDEC.

66. The method of claim 63, wherein the recipient encryption key RENC is generated from information comprising the recipient public key RPUB.

67. The method of claim 63, wherein the recipient encryption key RENC is generated from information comprising the identity of the recipient, the recipient public key RPUB, and a parameter defining a validity period for the recipient decryption key RDEC.

68. The method of claim 63, wherein the recipient decryption key RDEC is generated by the authorizer according to a schedule known to the sender.

69. The method of claim 68, wherein the recipient encryption key RENC is generated using at least information comprising the schedule.

70. The method of claim 63, wherein the recipient private key RPRIV and the recipient public key RPUB are generated using at least one system parameter issued by the authorizer.

71. The method of claim 63, wherein both the first group G₁ and the second group G₂ are of the same prime order q.

72. The method of claim 63, wherein the first cyclic group G₁ is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group G₂ is a multiplicative subgroup of a finite field.

73. The method of claim 63 wherein the system parameters available to the sender further comprise a function ê

which is a bilinear, non-degenerate, and efficiently computable pairing which maps G₁×

G₁ into G₂.

74. The method of claim 71 wherein:

s_C is an element of the cyclic group Z/qZ.

76. The method of claim 63, wherein the recipient encryption key RENC is generated from a document and the recipient decryption key RDEC is the authorizer'"'"'s signature on the document.

78. The method of claim 63 further comprising the authorizer selecting, by at least one machine in the set of the one or more machines, said key generation secret and generating, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC and sending, by at least one machine in the set of the one or more machines, the recipient decryption key RDEC to the recipient.

79. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 63.

97. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 64.

75. A method for operating a public-key encryption scheme which provides for sending a digital message M between a sender and a recipient with participation of an authorizer, wherein the digital message M is encrypted by the sender using at least a recipient public key RPUB and a recipient encryption key RENC to create an encrypted digital message and is decrypted by the recipient, the method comprising decrypting, by at least one machine in a set of one or more machines, the encrypted digital message using at least a recipient private key RPRIV and a recipient decryption key RDEC, wherein:

the recipient public key RPUB and the recipient private key RPRIV form a public key/private key pair 1, wherein the recipient private key RPRIV is a secret of the recipient;

the recipient decryption key RDEC is generated using at least a key generation secret of the authorizer and the recipient encryption key RENC, wherein a key formed from the recipient encryption key RENC and a key formed from the recipient decryption key RDEC are a public key/private key pair 2;

wherein the recipient decryption key RDEC is generated by the authorizer to have a value S=s_cP_B, wherein;

s_c is the key generation secret of the authorizer; and

P_B is the recipient encryption key RENC and is equal to H₁(Inf_B), wherein Inf_B is an element of a first cyclic group G₁ of elements, wherein P_B is an element of a second cyclic group G₂ of elements, and H₁ is a predefined function (“

first function H₁”

), wherein the first and second cyclic groups G₁ and G₂ and the function H₁ are system parameters made available to the sender, and also available to the sender are system parameters comprising;

a generator P of the first cyclic group G₁;

a key generation parameter Q=s_cP;

a second function H₂ capable of generating a second string of binary digits from an element of the second cyclic group G₂;

wherein encrypting the digital message M comprises;

generating an element P′

_B=H_1′

(ID_rec), wherein ID_rec comprises the identity of the recipient and wherein H_1′

is a function capable of generating an element of the first cyclic group G₁ from a string of binary digits;

selecting a random key generation secret r; and

encrypting the digital message M to form a ciphertext C, wherein C is set to be;

C=[rP, M⊕

H₂(g^r)], where g=ê

(Q, P_B)ê

(PK_B, P′

_B)∈

G₂, where PK_B is the recipient public key RPUB and wherein ê

is a bilinear non-degenerate pairing which maps G₁×

G₁into G₂.

95. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 75.

77. A method for operating a public-key encryption scheme which provides for sending a digital message M between a sender and a recipient with participation of an authorizer, wherein the digital message M is encrypted by the sender using at least a recipient public key RPUB and a recipient encryption key RENC to create an encrypted digital message and is decrypted by the recipient, the method comprising decrypting, by at least one machine in a set of one or more machines, the encrypted digital message using at least a recipient private key RPRIV and a recipient decryption key RDEC, wherein:

the recipient public key RPUB and the recipient private key RPRIV form a public key/private key pair 1, wherein the recipient private key RPRIV is a secret of the recipient;

the recipient decryption key RDEC is generated using at least a key generation secret of the authorizer and the recipient encryption key RENC, wherein a key formed from the recipient encryption key RENC and a key formed from the recipient decryption key RDEC are a public key/private key pair 2;

wherein the recipient decryption key RDEC is generated by the authorizer to have a value S=s_cP_B, wherein;

s_c is the key generation secret of the authorizer; and

P_B is the recipient encryption key RENC and is equal to H₁(Inf_B), wherein Inf_B is an element of a first cyclic group G₁ of elements, wherein P_B is an element of a second cyclic group G₂ of elements, and H₁ is a predefined function (“

first function H₁”

), wherein the first and second cyclic groups G₁ and G₂ and the function H₁ are system parameters made available to the sender, and also available to the sender are system parameters comprising;

a generator P of the first cyclic group G₁;

a key generation parameter Q=s_cP;

a second function H₂ capable of generating a second string of binary digits from an element of the second cyclic group G₂;

wherein both the first group G₁ and the second group G₂, are of the same prime order q;

wherein encrypting the digital message M comprises;

generating an element P′

_B=H_1′

(ID_rec) wherein H_1′

is a function capable of generating an element of the first cyclic group G₁ from a string of binary digits;

choosing a random parameter σ

∈

{0,1}ⁿ;

set a random key generation secret r=H₃(σ

, M); and

encrypting the digital message M to form a ciphertext C, wherein C is set to be;

C=[rP, M⊕

H₂(g^r), E<sub>H4(σ

)</sub>(M)], where g=ê

(Q, P_B)ê

(PK_B, P′

_B)∈

G₂, wherein PK_B is the recipient public key RPUB, wherein H₃ is a function capable of generating an integer of the cyclic group Z/qZ from two strings of binary digits, H₄ is a function capable of generating one binary string from another binary string, E is a symmetric encryption scheme, ê

is a bilinear non-degenerate pairing which maps G₁×

G₁ into G₂, and H₄(σ

) is the key used with E.

96. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 77.

80. A method for operating a public-key encryption scheme which provides for sending a digital message M between a sender and a recipient with participation of an authorizer, wherein the digital message is encrypted by the sender using at least a recipient public key RPUB and a recipient encryption key RENC, wherein the recipient public key RPUB and a recipient private key RPRIV form a recipient public key!recipient private key pair, wherein the recipient private key RPRIV is a secret of the recipient, and the digital message is decrypted by the recipient using at least the recipient private key RPRIV and a recipient decryption key RDEC, the method comprising the authorizer performing, by at least one machine in a set of one or more machines, operations of:

selecting a key generation secret that is a secret of the authorizer;

generating the recipient decryption key RDEC using at least the key generation secret of the authorizer and the recipient encryption key RENC, wherein a key formed from the recipient encryption key RENC and a key formed from the recipient decryption key RDEC are a public key!private key pair;

sending the recipient decryption key RDEC to the recipient;

wherein the recipient decryption key RDEC is generated by the authorizer to have a value S=s_cP_B, wherein;

s_c is the key generation secret of the authorizer; and

P_B is the recipient encryption key RENC and is equal to H₁(Inf_B), wherein Inf_B is an element of a first cyclic group G₁ of elements, wherein P_B is an element of a second cyclic group G₂ of elements, and H₁ is a predefined function (“

first function H₁”

), wherein the first and second cyclic groups G₁ and G₂ and the function H₁ are system parameters made available to the sender, and also available to the sender are system parameters comprising;

a generator P of the first cyclic group G₁;

a key generation parameter Q=s_cP;

a second function H₂ capable of generating a second string of binary digits from an element of the second cyclic group G₂;

wherein Inf_B comprises the identity of the recipient, ID_rec, the recipient public key RPUB, and a parameter defining a validity period for the recipient decryption key RDEC.

81. The method of claim 80, wherein the recipient encryption key RENC is generated from information comprising the identity of the recipient.

82. The method of claim 80, wherein the recipient encryption key RENC is generated from information comprising a parameter defining a validity period for the recipient decryption key RDEC.

83. The method of claim 80, wherein the recipient encryption key RENC is generated from information comprising the recipient public key RPUB.

84. The method of claim 80, wherein the recipient encryption key RENC is generated from information comprising the identity of the recipient, the recipient public key RPUB, and a parameter defining a validity period for the recipient decryption key RDEC.

85. The method of claim 80, wherein the recipient decryption key RDEC is generated by the authorizer according to a schedule known to the sender.

86. The method of claim 85, wherein the recipient encryption key RENC is generated using at least information comprising the schedule.

87. The method of claim 80, wherein both the first group G₁ and the second group G₂ are of the same prime order q.

88. The method of claim 80 wherein the first cyclic group G₁ is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group G₂ is a multiplicative subgroup of a finite field.

89. The method of claim 80 wherein the system parameters available to the sender further comprise a function ê

which is a bilinear, non-degenerate, and efficiently computable pairing which maps G₁×

G₁ into G₂.

90. The method of claim 87 wherein:

s_c is an element of the cyclic group Z/qZ.

91. The method of claim 80, wherein the recipient encryption key RENC is generated from a document and the recipient decryption key RDEC is the authorizer'"'"'s signature on the document.

92. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 80.

93. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 89.

94. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 91.

98. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 81.

99. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 82.

100. A computer-readable manufacture comprising a computer-readable computer program operable to cause a computer to perform the method of claim 83.