Method of public key cryptography that includes key escrow

• US 5,920,630 A
• Filed: 02/25/1997
• Issued: 07/06/1999
• Est. Priority Date: 02/25/1997
• Status: Expired due to Fees

• Current Assignee: US Government As Represented By The Director National Security Agency, US Government The As Represented BT The Director National Security Agency
• Original Assignee: Government of the United States of America
• Inventors: Bielefeld, Benjamin M., Pendergrass, J. William, White, Tad P., Livingston, Boyd T., Monroe, Thomas H., Wertheimer, Michael A.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Callahan, Paul E.
• Application Number:
  US08/805,967
• Time in Patent Office: 861 Days
• Field of Search: 380/25, 380/28, 380/29, 380/30, 380/43, 380/45, 380/46, 380/47, 380/49
• US Class Current: 380/286
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• 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

A key escrow encryption method, where two users each have secret encryption keys and corresponding public encryption keys. One user receives the public encryption keys of the other user and generates a first datum based on them, an identifier of the other user, the secret encryption keys and identifier of the user, and an access restriction. The user generates a second datum based on the first datum and another access restriction. The user generates a key based on the first and second datums. The user encrypts a message using the key and sends it to the other user. Key escrow is included by requiring each user to distribute its secret encryption keys among escrow agents. The escrow agents transform, sign, and transmit it to a certifying authority. The certifying authority signs and publishes it as user'"'"'s public key certificate. To communicate, a user retrieves the certificate of the other user, forms a key, encrypts a message, and transmits it to the other user. The other user retrieves the certificate of the user, forms the key, and decrypts the message. A key encryption key scheme may be used. A third party may intercept the message, receive authorization, receive portions of the key from the escrow agents, recover the key, and recover the message. A data recovery scheme may be used.

Claims

1. A method of encryption that includes key escrow, comprising the steps of:

a) having, by a first user, n secret encryption keys, where n is a positive integer, and where Si₁ denotes the i^th secret encryption key of the first user;

b) having, by the first user, n public encryption keys corresponding to the n secret encryption keys of the first user, where Pi₁ denotes the i^th public encryption key of the first user;

c) having, by a second user, n secret encryption keys, where Si₂ denotes the i^th secret encryption key of the second user;

d) having, by the second user, n public encryption keys corresponding to the n secret encryption keys of the second user, where Pi₂ denotes the i^th public encryption key of the second user;

e) receiving, by the first user, the n public encryption keys of the second user;

f) receiving, by the first user, a unique identifier ID₂ of the second user;

g) generating, by the first user, n values a_i =F₁ (Si₁, Pi₂, ID₁, ID₂, r₁), where a_i =F₁ (Si₂, Pi₁, ID₁, ID₂, r₁), where a_i does not equal F₁ (Si₁, Pi₂, ID₂, ID₁, r₁), where F₁ is a first function, where ID₁ is a unique identifier of the first user, where r₁ is a first of m access restriction values r₁, r₂, . . . ,r_m, and where m is a positive integer;

h) generating, by the first user, n values b_i =h_m-1 ( . . . h₂ (h₁ (a₁,r₂),r₃), . . . ,r_m), where h₁,h₂, . . . ,h_m-1 are one-way hash functions;

i) generating, by the first user, key=h(F₂ (b₁, b₂, . . . ,b_n),x), where F₂ is a second function, where h is a one-way hash function, and where x is a random number;

j) encrypting, by the first user, a message using key;

k) appending, by the first user, r₁,r₂, . . . ,r_m, x, ID₁, and ID₂ to the encrypted message; and

l) transmitting, by the first user, the result of step (k) to a storage medium.

2. The method of claim 1, wherein the step of transmitting the result of step (k) to a storage medium is comprised of transmitting the result of step (k) to a storage medium of the second user.

3. The method of claim 2, further comprising the steps of:

a) retrieving, by the second user, the result of step (k) stored in the storage medium of the second user;

b) receiving, by the second user, a unique identifier ID₁ of the first user;

c) receiving, by the second user, the n public encryption keys of the first user;

d) reconstructing, by the second user, the n values a_i =F₁ (Si₂, Pi₁, ID₂, r₁);

e) reconstructing, by the second user, the n values b_i =h_m-1 ( . . . h₂ (h₁ (a₁,r₂),r₃), . . . ,r_m);

f) reconstructing, by the second user, key=h(F₂ (b₁, b₂, . . . ,b_n),x); and

g) decrypting, by the second user, the encrypted message using key.

4. The method of claim 1, wherein the step of transmitting the result of step (k) to a storage medium is comprised of transmitting the result of step (k) to a storage medium of the first user.

5. The method of claim 4, further comprising the steps of:

a) retrieving, by the first user, the result of step (k) stored in the storage medium of the first user;

b) reconstructing, by the first user, key; and

c) decrypting, by the first user, the encrypted message using key.

6. The method of claim 4, further comprising the steps of:

a) transmitting, by the first user, r₁,r₂, . . . ,r_m, x, ID₁, and ID₂ to the second user;

b) requesting, by the first user, that the second user reconstruct key;

c) reconstructing key by the second user;

d) transmitting, by the second user, key to the first user;

e) retrieving, by the first user, the encrypted message from the storage medium of the first user; and

f) decrypting, by the first user, the encrypted message using key.

7. The method of claim 1, wherein the step of encrypting, by the first user, a message using key is comprised of encrypting, by the first user, a message using key, where the message is a second key key₂.

8. The method of claim 6, further comprising the steps of:

a) encrypting, by the first user, a second message using key₂ ;

b) storing, by the first user, the result of step (a) in the storage medium of the first user;

c) retrieving, by the first user, the result of step (b) from the storage medium of the first user;

d) reconstructing, by the first user, key;

e) retrieving, by the first user, the encrypted key₂ from the storage medium of the first user;

f) decrypting, by the first user, the encrypted key₂ using key;

g) retrieving, by the first user, the encrypted second message from the storage medium of the first user; and

h) decrypting, by the first user, the encrypted second message using key₂.

9. The method of claim 7, further comprising the steps of:

a) encrypting, by the first user, a second message using key₂ ;

b) storing, by the first user, the result of step (a) in the storage medium of the first user;

c) transmitting, by the first user, r₁,r₂, . . . ,r_m, x, ID₁, and ID₂ to the second user;

d) requesting, by the first user, the second user reconstruct key;

e) reconstructing key by the second user;

f) transmitting, by the second user, key to the first user;

g) retrieving, by the first user, the encrypted key₂ from the storage medium of the first user;

h) decrypting, by the first user, the encrypted key₂ using key;

i) retrieving, by the first user, the encrypted second message from the storage medium of the first user; and

j) decrypting, by the first user, the encrypted second message using key₂.

10. The method of claim 1, further comprising the steps of:

a) distributing, by the first user, the n secret encryption keys of the first user among at least one escrow agent of the first user; and

b) distributing, by the second user, the n secret encryption keys of the second user among at least one escrow agent of the second user.

11. The method of claim 10, further comprising the steps of:

a) transforming, by at least one escrow agent of the first user, at least one of the n secret encryption keys of the first user into at least one corresponding public encryption key of the first user;

b) signing digitally, by at least one escrow agent of the first user, the result of step (a);

c) sending, by at least one escrow agent of the first user, the result of step (b) to a certifying authority of the first user;

d) transforming, by at least one escrow agent of the second user, at least one of the n secret encryption keys of the second user into at least one corresponding public encryption key of the second user;

e) signing digitally, by at least one escrow agent of the second user, the result of step (d); and

f) sending, by at least one escrow agent of the second user, the result of step (e) to a certifying authority of the second user.

12. The method of claim 11, further comprising the steps of:

a) verifying, by the certifying authority of the first user, the digital signature of at least one escrow agent of the first user;

b) signing digitally, by the certifying authority of the first user, at least one public encryption key of the first user;

c) sending, by the certifying authority of the first user, the result of step (b) to a public directory;

d) verifying, by the certifying authority of the second user, the digital signature of at least one escrow agent of the second user;

e) signing digitally, by the certifying authority of the second user, at least one public encryption key of the second user; and

f) sending, by the certifying authority of the second user, the result of step (e) to the public directory.

13. The method of claim 12, wherein the step of transmitting the result of step (k) to a storage medium is comprised of transmitting the result of step (k) to a storage medium of the second user.

14. The method of claim 13, further comprising the steps of:

a) retrieving, by the second user, the result of step (k) stored in the storage medium of the second user;

b) receiving, by the second user, a unique identifier ID₁, of the first user;

c) receiving, by the second user, the n public encryption keys of the first user;

d) reconstructing, by the second user, the n values a_i =F₁ (Si₂, Pi₁, ID₁, ID₂, r₁);

e) reconstructing, by the second user, the n values b_i =h_m-1 ( . . . h₂ (h₁ (a₁,r₂),r₃), . . . ,r_m);

f) reconstructing key=h(F₂ (b₁, b₂, . . . ,b_n),x); and

g) decrypting, by the second user, the encrypted message using key.

15. The method of claim 13, further comprising the steps of:

a) obtaining authorization, by a third party, from an appropriate authority to gain access to secure communications from the first user to the second user restricted by at least one of the access restriction values r₁,r₂, . . . ,r_k, where k is a positive integer;

b) relaying the authorization, by the appropriate authority to each of the escrow agents of the first user;

c) generating, by each of the escrow agents of the first user, a portion of key that depends upon the first user'"'"'s secret encryption key held by the escrow agent generating the portion of key and the access restriction values included in the authorization, where the portion of key depending on the i^th secret encryption key of the first user is h_k-1 ( . . . h₂ (h₁ (a_i, r₂), r₃), . . . ,r_k);

d) transmitting securely, by each escrow agent of the first user, the portion of key generated and the at least one access restriction values in sequence to the third party;

e) obtaining, by the third party, the transmission from the first user to the second user;

f) reconstructing, by the third party, key using the portions of key received and the access restriction values and random number obtained; and

g) decrypting the message sent from the first user to the second user that was encrypted with key.

16. The method of claim 13, further comprising the steps of:

a) obtaining authorization, by a third party, from an appropriate authority to gain access to secure communications from the first user to the second user restricted by at least one of the access restriction values r₁,r₂, . . . ,r_k, where k is a positive integer;

b) relaying the authorization, by the appropriate authority to each of the escrow agents of the second user;

c) generating, by each of the escrow agents of the second user, a portion of key that depends upon the second user'"'"'s secret encryption key held by the escrow agent generating the portion of key and the access restriction values included in the authorization, where the portion of key depending on the i^th secret encryption key of the second user is h_k-1 ( . . . h₂ (h₁ (a_i,r₂),r₃), . . . ,r_k);

d) transmitting securely, by each escrow agent of the second user, the portion of key generated and the at least one access restriction values in sequence to the third party;

e) obtaining, by the third party, the transmission from the first user to the second user;

f) reconstructing, by the third party, key using the portions of key received and the access restriction values and random number obtained; and

g) decrypting the message sent from the first user to the second user that was encrypted with key.

17. The method of claim 12, wherein the step of transmitting the result of step (k) to a storage medium is comprised of transmitting the result of step (k) to a storage medium of the first user.

18. The method of claim 17, further comprising the steps of:

a) transmitting, by the first user, r₁,r₂, . . . ,r_m, x, ID₁, and ID₂ to the second user;

b) requesting, by the first user, that the second user reconstruct key;

c) reconstructing key by the second user;

d) transmitting, by the second user, key to the first user;

e) retrieving, by the first user, the encrypted message from the storage medium of the first user; and

f) decrypting, by the first user, the encrypted message using key.

19. The method of claim 17, further comprising the steps of:

a) obtaining authorization, by a third party, from an appropriate authority to gain access to secure communications from the first user to the second user restricted by at least one of the access restriction values r₁,r₂, . . . ,r_k, where k is a positive integer;

b) relaying the authorization, by the appropriate authority to each of the escrow agents of the first user;

c) generating, by each of the escrow agents of the first user, a portion of key that depends upon the first user'"'"'s secret encryption key held by the escrow agent generating the portion of key and the access restriction values included in the authorization, where the portion of key depending on the i^th secret encryption key of the first user is h_k-1 ( . . . h₂ (h₁ (a_i,r₂),r₃), . . . ,r_k));

d) transmitting securely, by each escrow agent of the first user, the portion of key generated and the at least one access restriction values in sequence to the third party;

e) obtaining, by the third party, the transmission from the first user to the storage medium of the first user;

f) reconstructing, by the third party, key using the portions of key received and the access restriction values and random number obtained; and

g) decrypting the message sent from the first user to the second user that was encrypted with key.

20. The method of claim 17, further comprising the steps of:

a) obtaining authorization, by a third party, from an appropriate authority to gain access to secure communications from the first user to the second user restricted by at least one of the access restriction values r₁,r₂, . . . ,r_k, where k is a positive integer;

b) relaying the authorization, by the appropriate authority to each of the escrow agents of the second user;

c) generating, by each of the escrow agents of the second user, a portion of key that depends upon the second user'"'"'s secret encryption key held by the escrow agent generating the portion of key and the access restriction values included in the authorization, where the portion of key depending on the i^th secret encryption key of the second user is h_k+1 ( . . . h₂ (h₁ (a_i,r₂),r₃), . . . ,r_k);

d) transmitting securely, by each escrow agent of the second user, the portion of key generated and the at least one access restriction values in sequence to the third party;

e) obtaining, by the third party, the transmission from the first user to the storage medium of the first user;

f) reconstructing, by the third party, key using the portions of key received and the access restriction values and random number obtained; and

g) decrypting the message sent from the first user to the second user that was encrypted with key.

21. The method of claim 1, wherein the step of having, by the first user, n secret encryption keys is comprised of the step of having, by the first user, two secret encryption keys S1₁ and S2₁.

22. The method of claim 21, wherein the step of having, by the first user, n public encryption keys is comprised of the step of having, by the first user, two public encryption keys P1₁ =gS1₁ mod p and P2₁ =gS2₁ mod p, where g is a base, where "" denotes exponentiation, and where p is a prime number.

23. The method of claim 22, wherein the step of having, by the second user, n secret encryption keys is comprised of the step of having, by the second user, two secret encryption keys S1₂ and S2₂.

24. The method of claim 23, wherein the step of having, by the second user, n public encryption keys is comprised of the step of having, by the second user, two public encryption keys P1₂ =gS1₂ mod p and P2₂ =gS2₂ mod p.

25. The method of claim 24, wherein the step of receiving, by the first user, n public encryption keys of the second user is comprised of the step of receiving, by the first user, P1₂ and P2₂.

26. The method of claim 25, wherein the step of generating, by the first user, n values a_i =F₁ (Si₁, Pi₂, ID₁, ID₂, r₁) is comprised of the step of generating, by the first user, a₁ =h(P1₂ S1₁ mod p, ID₁, ID₂, r₁) and a₂ =h(P2₂ S2₁ mod p, ID₁, ID₂, r₁).

27. The method of claim 26, wherein the step of generating, by the first user, n values b_i =h_m-1 ( . . . h₂ (h₁ (a₁,r₂),r₃), . . . ,r_m) is comprised of the step of generating, by the first user, b₁, =h(a₁,r₂) and b₂ =h(a₂,r₂).

28. The method of claim 27, wherein the step of generating key=h(F₂ (b₁,b₂, . . . ,b_n),x) is comprised of the step of generating, by the first user, key=h((b₁, XOR b₂),x).

29. The method of claim 28, wherein the step of encrypting, by the first user, a message using key is comprised of the step of encrypting, by the first user, a message using key, where the message is digitally signed by the first user.

30. The method of claim 29, wherein the step of appending to the encrypted message r₁,r₂, . . . ,r_m, x, ID₁, and ID₂ is comprised of the step of appending to the encrypted message r₁, r₂, x, ID₁, and ID₂.

31. The method of claim 30, wherein the step of generating, by the first user, n values a_i =F₁ (Si₁, Pi₂, ID₁, ID₂, r₁) is comprised of the step of generating, by the first user, a₁ =h(P1₂ S1₁ mod p, ID₁, ID₂, r₁) and a₂ =h(P2₂ S2₁ mod p, ID₁, ID₂, r₁), where r₁, is an access restriction selected from the group consisting of time, group affiliation, corporate affiliation, and cell hierarchy.

32. The method of claim 31, wherein the step of generating, by the first user, n values b_i =h_m-1 ( . . . h₂ (h₁ (a₁,r₂),r₃), . . . ,r_m) is comprised of the step of generating, by the first user, b₁, =h(a₁,r₂) and b₂ =h(a₂,r₂), where r₂ is an access restriction selected from the group consisting of time, group affiliation, corporate affiliation, and cell hierarchy.

33. The method of claim 32, further comprising the steps of:

a) sending securely, by the first user, S1₁ to a first escrow agent of the first user;

b) sending securely, by the first user, S2₁ to a second escrow agent of the first user;

c) sending securely, by the second user, S1₂ to a first escrow agent of the second user; and

d) sending securely, by the second user, S2₂ to a second escrow agent of the second user.

34. The method of claim 33, wherein the step of sending securely, by the first user, S1₁, to a first escrow agent of the first user is comprised of the steps of:

a) generating, by the first user, a secret key t1₁ ;

b) generating, by the first user, tp1₁ =gt1₁ mod p;

c) having, by the first user'"'"'s first escrow agent, a secret key S_EA11 ;

d) receiving, by the first user, p_EA11 =gS_EA11 mod p from the first user'"'"'s first escrow agent;

e) generating, by the first user, k1₁ =p_EA11 t1₁ mod p;

f) encrypting, by the first user, S1₁ using k1₁ as a key to an encryption function E, where the result is denoted as E_k11 (S1₁);

g) receiving, by the first user, a unique identifier ID_CA1 of a certifying authority of the first user;

h) signing digitally, by the first user, tp1₁, E_k11 (S1₁), and ID_CA1 ; and

i) sending the result of step (h) to the first escrow agent of the first user.

35. The method of claim 34, wherein the step of sending securely, by the first user, S2₁ to a second escrow agent of the first user is comprised of the steps of:

a) generating, by the first user, a secret key t2₁ ;

b) generating, by the first user, tp2₁ =gt2₁, mod p;

c) having, by the first user'"'"'s second escrow agent, a secret key S_EA21 ;

d) receiving, by the first user, p_EA21 =gS_EA21 mod p from the first user'"'"'s second escrow agent;

e) generating, by the first user, k2₁ =p_EA21 t2₁ mod p;

f) encrypting, by the first user, S2₁ using k2₁ as a key to an encryption function E, where the result is denoted as E_k21 (S2₁);

g) signing digitally, by the first user, tp2₁, E_k21 (S2₁), and ID_CA1 ; and

h) sending the result of step (g) to the second escrow agent of the first user.

36. The method of claim 35, wherein the step of sending securely, by the second user, S1₂ to a first escrow agent of the second user is comprised of the steps of:

a) generating, by the second user, a secret key t1₂ ;

b) generating, by the second user, tp1₂ =gt1₂ mod p;

c) having, by the second user'"'"'s first escrow agent, a secret key S_EA12 ;

d) receiving, by the second user, p_EA12 =gS_EA12 mod p from the second user'"'"'s first escrow agent;

e) generating, by the second user, k1₂ =p_EA12 t1₂ mod p;

f) encrypting, by the second user, S1₂ using k1₂ as a key to an encryption function E, where the result is denoted as E_k12 (S1₂);

g) receiving, by the second user, a unique identifier ID_CA2 of a certifying authority of the second user;

h) signing digitally, by the second user, tp1₂, E_k12 (S1₂), and ID_CA2 ; and

i) sending the result of step (h) to the first escrow agent of the second user.

37. The method of claim 36, wherein the step of sending securely, by the second user, S2₂ to a second escrow agent of the second user is comprised of the steps of:

a) generating, by the second user, a secret key t2₂ ;

b) generating, by the second user, tp2₂ =gt2₂ mod p;

c) having, by the second user'"'"'s second escrow agent, a secret key S_EA22 ;

d) receiving, by the second user, p_EA22 =gS_EA22 mod p from the second user'"'"'s second escrow agent;

e) generating, by the second user, k2₂ =p_EA22 t2₂ mod p;

f) encrypting, by the second user, S2₂ using k2₂ as a key to an encryption function E, where the result is denoted as E_k22 (S2₂);

g) signing digitally, by the second user, tp2₂, E_k22 (S2₂), and ID_CA2 ; and

h) sending the result of step (g) to the second escrow agent of the second user.

38. The method of claim 37, further comprising the steps of:

a) authenticating, by the first escrow agent of the first user, the first user'"'"'s digital signature;

b) reconstructing, by the first escrow agent of the first user, k1₁ =tp1₁ S_EA11 mod p;

c) decrypting, by the first escrow agent of the first user, E_k11 (S1₁) using the result of step (b) to recover S1₁ ;

d) generating, by the first escrow agent of the first user, p1₁ =gS1₁ mod p;

e) signing digitally, by the first escrow agent of the first user, p1₁ and ID₁ ;

f) sending the result of step (e) to the certifying authority of the first user;

g) authenticating, by the second escrow agent of the first user, the first user'"'"'s digital signature;

h) reconstructing, by the second escrow agent of the first user, k2₁ =tp2₁ S_EA21 mod p;

i) decrypting, by the second escrow agent of the first user, E_k21 (S2₁) using the result of step (h) to recover S2₁ ;

j) generating, by the second escrow agent of the first user, p2₁ =gS2₁ mod p;

k) signing digitally, by the second escrow agent of the first user, p2₁ and ID₁ ;

l) sending the result of step (k) to the certifying authority of the first user;

m) authenticating, by the first escrow agent of the second user, the second user'"'"'s digital signature;

n) reconstructing, by the first escrow agent of the second user, k1₂ =tp1₂ S_EA12 mod p;

o) decrypting, by the first escrow agent of the second user, E_k12 (S1₂) using the result of step (n) to recover S1₂ ;

p) generating, by the first escrow agent of the second user, p1₂ =gS1₂ mod p;

q) signing digitally, by the first escrow agent of the second user, p1₂ and ID₂ ;

r) sending the result of step (q) to the certifying authority of the second user;

s) authenticating, by the second escrow agent of the second user, the second user'"'"'s digital signature;

t) reconstructing, by the second escrow agent of the second user, k2₂ =tp2₂ S_EA22 mod p;

u) decrypting, by the second escrow agent of the second user, E_k22 (S2₂) using the result of step (t) to recover S2₂ ;

v) generating, by the second escrow agent of the second user, p2₂ =gS2₂ mod p;

w) signing digitally, by the second escrow agent of the second user, p2₂ and ID₂ ; and

ID₂ ; and

x) sending the result of step (w) to the certifying authority of the second user.

39. The method of claim 38, further comprising the steps of:

a) verifying, by the certifying authority of the first user, the digital signature of the first escrow agent of the first user;

b) verifying, by the certifying authority of the first user, the digital signature of the second escrow agent of the first user;

c) signing digitally, by the certifying authority of the first user, the digitally signed message received from the first escrow agent of the first user, the digitally signed message of the second escrow agent of the first user, and ID₁ ;

d) sending the result of step (c) to a public directory;

e) verifying, by the certifying authority of the second user, the digital signature of the first escrow agent of the second user;

f) verifying, by the certifying authority of the second user, the digital signature of the second escrow agent of the second user;

g) signing digitally, by the certifying authority of the second user, the digitally signed message received from the first escrow agent of the second user, the digitally signed message of the second escrow agent of the second user, and ID₂ ; and

h) sending the result of step (g) to a public directory.

40. The method of claim 39, wherein the step of transmitting the result of step (k) to a storage medium is comprised of the step of transmitting the result of step (k) to a storage medium of the second user.

41. The method of claim 39, wherein the step of transmitting the result of step (k) to a storage medium is comprised of the step of transmitting the result of step (k) to a storage medium of the first user.

42. The method of claim 41, further comprising the steps of:

a) transmitting, by the first user, r₁, r₂, x, ID₁, and ID₂ to the second user;

b) requesting, by the first user, that the second user reconstruct key;

c) reconstructing key by the second user;

d) transmitting, by the second user, key to the first user;

e) retrieving, by the first user, the encrypted message from the storage medium of the first user; and

f) decrypting, by the first user, the encrypted message using key.

43. The method of claim 40, further comprising the steps of:

a) retrieving, by the second user, the result of step (k) stored in the storage medium of the second user;

b) receiving, by the second user, P1₁ and P1₂ ;

c) reconstructing, by the second user, a₁ =h(P1₁ S1₂ mod p, ID₁, ID₂, r₁) and a₂ =h(P2₁ S2₂ mod p, ID₁, ID₂, r₁);

d) reconstructing, by the second user, b₁ =h(a₁,r₂) and b₂ =h(a₂,r₂);

e) reconstructing, by the second user, key=h((b₁ XOR b₂)x);

f) decrypting, by the second user, using key the encrypted message which was digitally signed by the first user; and

g) verifying, by the second user, the first user'"'"'s digital signature.

44. The method of claim 43, further comprising the steps of:

a) obtaining authorization, by a third party, from an appropriate authority to gain access to secure communications from the first user to the second user restricted by r₁ ;

b) signing digitally, by the appropriate authority, ID₁, ID₂, and r₁ ;

c) sending the result of step (b) to the first and second escrow agents of the first user;

d) generating, by the first escrow agent of the first user, a₁ =h(P1₂ S1₁ mod p, ID₁, ID₂, r₁);

e) signing digitally, by the first escrow agent of the first user, a₁, ID₁, and ID₂ ;

f) sending the results of step (e) to the third party;

g) generating, by the second escrow agent of the first user, a₂ =h(P2₂ S2₁ mod p, ID₁, ID₂, r₁);

h) signing digitally, by the second escrow agent of the first user, a₂, ID₁, and ID₂ ;

i) sending the results of step (h) to the third party;

j) obtaining, by the third party, the transmission by the first user of the result of step (k) of claim 1 to the storage medium of the second user;

k) generating, by the third party, b₁ =h(a₁,r₂) and b₂ =h(a₂,r₂), where the third party knows r₂ from step (j);

l) reconstructing, by the third party, key=h((b₁ XOR b₂),x), where the third party knows x from step (j);

m) decrypting the digitally signed message sent from the first user to the second user that was encrypted with key; and

n) verifying the digital signature of the first user.

45. The method of claim 43, further comprising the steps of:

a) obtaining authorization, by a third party, from an appropriate authority to gain access to secure communications from the first user to the second user restricted by r₁ ;

b) signing digitally, by the appropriate authority, ID₁, ID₂, and r₁ ;

c) sending, by the appropriate authority, the result of step (b) to the first and second escrow agents of the second user;

d) reconstructing, by the first escrow agent of the second user, a₁ =h(P1₁ S1₂ mod p, ID₁, ID₂, r₁);

e) signing digitally, by the first escrow agent of the second user, a₁, ID₁, and ID₂ ;

f) sending, by the first escrow agent of the second user, the result of step (e) to the third party;

g) reconstructing, by the second escrow agent of the second user, a₂ =h(P2₁ S2₂ mod p, ID₁, ID₂, r₁);

h) signing digitally, by the second escrow agent of the second user, a₂, ID₁, and ID₂ ;

i) sending, by the second escrow agent of the second user, the result of step (h) to the third party;

j) obtaining, by the third party, the transmission by the first user of the result of step (k) of claim 1 to the storage medium of the second user;

k) generating, by the third party, b₁ =h(a₁,r₂) and b₂ =h(a₂,r₂), where the third party knows r₂ from step (j);

l) reconstructing, by the third party, key=h((b₁ XOR b₂),x), where the third party knows x from step (j);

m) decrypting the digitally signed message sent from the first user to the second user that was encrypted with key; and

n) verifying the digital signature of the first user.

46. The method of claim 43, further comprising the steps of:

a) obtaining authorization, by a third party, from an appropriate authority to gain access to secure communications from the first user to the second user restricted by r₁ and r₂ ;

b) signing digitally, by the appropriate authority, ID₁, ID₂, r₁ and r₂ ;

c) sending, by the appropriate authority, the result of step (b) to the first and second escrow agents of the first user;

d) generating, by the first escrow agent of the first user, b₁ =h(h(P1₂ S1₁ mod p, ID₁, ID₂, r₁),r₂);

e) signing digitally, by the first escrow agent of the first user, b₁, ID₁, and ID₂ ;

f) sending, by the first escrow agent of the first user, the result of step (e) to the third party;

g) generating, by the second escrow agent of the first user, b₂ =h(h(P2₂ S2₁ mod p, ID₁, ID₂, r₁),r₂);

h) signing digitally, by the second escrow agent of the first user, b₂, ID₁, and ID₂ ;

i) sending, by the second escrow agent of the first user, the result of step (h) to the third party;

j) obtaining, by the third party, the transmission by the first user of the result of step (k) of claim 1 to the storage medium of the second user;

k) reconstructing, by the third party, key=h((b₁ XOR b₂),x), where the third party knows x from step (j);

l) decrypting, by the third party, the digitally signed message sent from the first user to the second user that was encrypted with key; and

m) verifying the digital signature of the first user.

47. The method of claim 43, further comprising the steps of:

a) obtaining authorization, by a third party, from an appropriate authority to gain access to secure communications from the first user to the second user restricted by r₁ and r₂ ;

b) signing digitally, by the appropriate authority, ID₁, ID₂, r₁ and r₂ ;

c) sending, by the appropriate authority, the result of step (b) to the first and second escrow agents of the second user;

d) generating, by the first escrow agent of the second user, b₁ =h(h(P1₁ S1₂ mod p, ID₁, ID₂, r₁),r₂);

e) signing digitally, by the first escrow agent of the second user, b₁, ID₁, and ID₂ ;

f) sending, by the first escrow agent of the second user, the result of step (e) to the third party;

g) generating, by the second escrow agent of the second user, b₂ =h(h(P2₁ S2₂ mod p, ID₁, ID₂, r₁),r₂);

h) signing digitally, by the second escrow agent of the second user, b₂, ID₁, and ID₂ ;

i) sending, by the second escrow agent of the second user, the result of step (h) to the third party;

j) obtaining, by the third party, the transmission by the first user of the result of step (k) of claim 1 to the storage medium of the second user;

k) reconstructing, by the third party, key=h((b₁ XOR b₂),x), where the third party knows x from step (j);

l) decrypting, by the third party, the digitally signed message sent from the first user to the second user that was encrypted with key; and

m) verifying the digital signature of the first user.

48. The method of claim 1, wherein the step of generating key=h(F₂ (b₁, b₂, . . . ,b_n),x) is comprised of the step of key=h((b₁ XOR b₂ XOR b₃ . . . XOR b_n),x), where XOR is an exclusive-or function.

49. The method of claim 1, wherein the step of encrypting, by the first user, a message using key is comprised of the step of encrypting, by the first user, a message digitally signed by the first user.

50. The method of claim 1, wherein the step of encrypting, by the first user, a message using key is comprised of encrypting, by the first user, a message using key, where the message is a second key key₂.

51. The method of claim 50, further comprising the steps of:

a) encrypting, by the first user, a second message using key₂ ; and

b) storing, by the first user, the result of step (a) in the storage medium.

52. The method of claim 51, wherein the step of transmitting the result of step (k) to a storage medium is comprised of the step of transmitting the result of step (k) to a storage medium of the second user.

53. The method of claim 52, further comprising the steps of:

a) receiving, by the second user, the n public encryption keys of the first user, where Pi₁ denotes the i^th public encryption key of the first user;

b) receiving, by the second user, a unique identifier ID₁ of the first user;

c) reconstructing, by the second user, n values a_i =F₁ (Si₂, Pi₁, ID₁, ID₂, r₁);

d) reconstructing, by the second user, n values b_i =h_m-1 ( . . . h₂ (h₁ (a₁, r₂),r₃), . . . ,r_m);

e) reconstructing, by the second user, key=h(F₂ (b₁, b₂, . . . ,b_n),x);

f) retrieving, by the second user, the encrypted key₂ from the storage medium of the second user;

g) decrypting, by the second user, the encrypted key₂ using key;

h) retrieving, by the second user, the encrypted second message from the storage medium of the second user; and

i) decrypting, by the second user, the encrypted second message using key₂.