Method for enabling users of a cryptosystem to generate and use a private pair key for enciphering communications between the users

• US 5,519,778 A
• Filed: 09/26/1994
• Issued: 05/21/1996
• Est. Priority Date: 08/13/1993
• Status: Expired due to Term

• Current Assignee: Silvio Micali
• Original Assignee: Silvio Micali
• Inventors: Leighton, Frank T., Micali, Silvio
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US08/312,567
• Time in Patent Office: 603 Days
• Field of Search: 380/30, 380/21
• US Class Current: 380/30
• CPC Class Codes: H04L 9/0841 involving Diffie-Hellman or related key agreement protocols

Abstract

The present invention describes a method for enabling users of a cryptosystem to agree on secret keys. In one embodiment, a trusted agent chooses at least one individual key for each user, with at least a portion of such individual key being secret. At least some of the individual keys are then stored in physically secure devices, and the pair of users i and j use their individual keys to compute a common secret key. In another embodiment, each trustee of a group of trustees choose at least one individual key for each user, with at least some portion of such individual key being secret. The keys chosen by a sufficiently small number of such trustees, however, are insufficient for computing the common secret key of the users. Other hardware and software key exchange protocols based on these two techniques are also disclosed.

Claims

1. A method for enabling users of a cryptosystem to generate and use a private pair key for enciphering communications between the users, comprising the steps of:

for each user and each trustee of a group of at least two trustees, having at least one user individual key;

for each user, storing at least some of the user'"'"'s individual user keys in a physically-secure device;

having each of the users compute the private pair key in a physically-secure device from information that includes information stored in the user'"'"'s physically-secure device and identifying information of the other user, wherein the private pair key cannot be computed by a subset of of trustees containing less than a given number of trustees;

having one of the users generate a ciphertext using the private pair key; and

transmitting the ciphertext from the user to another user of the cryptosystem.

2. The method as described in claim 1 wherein some of the users belong to different security levels.

3. The method as described in claim 2 wherein the individual user keys of a group of users of a first security level contain no useful information for computing the private pair key of a pair of users of a second security level.

4. A method for enabling users of a cryptosystem to generate and use a private pair key for enciphering communications between the users, comprising the steps of:

generating at least one public key for each user by iterating at least a conventional one-way function on at least one private value stored in a physically-secure device;

using the physically-secure device of each of a pair of users to compute the private pair key for the pair of users, wherein the private pair key is computed based on information that includes one user'"'"'s private information and the other user'"'"'s public key;

having one of the users generate a ciphertext using the private pair key; and

transmitting the ciphertext from the user to other user of the cryptosystem.

5. The method as described in claim 4 wherein some of the users belong to different security levels.

7. A method for enabling users of a cryptosystem to generate and use a private pair key enciphering communications between the users, comprising the steps of:

for each user and each trustee of a group of trustee of a group of trustees, generating at least one public key by iterating at least a conventional one-way function on at least one private value stored in a physically-secure device;

having at least one of the two users use a physically-secure device to compute the private pair key from information that includes private information of the user and the other user'"'"'s public key, wherein a subset of trustees containing less than a given number of trustees does not possess any useful information for reconstructing the private pair key;

having one of the users generate a ciphertext using the private pair key; and

transmitting the ciphertext from the user to other user of the cryptosystem.

8. The method as described in claim 7 wherein some of the users belong to different security levels.

9. A method for enabling two users of a cryptosystem to generate and use a private pair key to encipher communications between the two users, comprising the steps of:

for each user and each trustee of a group of trustees, having at least one individual user key;

having at least one of the two users receive and store in a physical device at least a public pair key for the two users;

having at least one of two users use the physical device to compute the private pair key from information that includes the user'"'"'s individual user key and the public pair key stored by one of the users, wherein a subset of trustees containing less than a given number of trustees does not possess any useful information for reconstructing the private pair key;

having one of the users generate a ciphertext using the private pair key; and

transmitting the ciphertext from the user to other user of the cryptosystem.

6. The method as described in claim 9 wherein private information relative to users of a first security level is substantially useless for computing the private pair key of a pair of users of a second security level.

10. The method as described in claim 9 wherein the individual user key of each user is stored in a physically-secure device.

11. The method as described in claim 9 wherein a plurality of individual user keys of a user are combined into a single individual user key.

12. The method as described in claim 9 wherein at least some public pair keys are computed by an entity that cannot compute individual user keys.

13. The method as described in claim 12 wherein the entity is prevented from computing individual user keys because such keys are stored in physically-secure devices.

14. The method as described in claim 9 wherein trustees reveal individual user keys of a given user for the purpose of enabling monitoring of communications relative to that user while preserving privacy of the communications of other users.

15. A method for enabling two users of a cryptosystem to generate and use a private pair key to encipher communications between the two users, comprising the steps of:

for each user and each trustee of a group of trustees, having at least one individual user key;

having at least one of the two users receive at least a public pair key for the two users, wherein at least one public pair key is computed by an entity that cannot compute all individual user keys;

having at least one of the two users use a physical device to compute the private pair key from information that includes the user'"'"'s individual user key and at least one public pair key, wherein a subset of trustees containing less than a given number of trustees does not possess any useful information for reconstructing the private pair key;

having one of the users generate a ciphertext using the private pair key; and

transmitting the ciphertext from the user to other user of the cryptosystem.

16. The method as described in claim 15 wherein the entity is prevented from computing individual user keys because such keys are stored in physically-secure devices.

17. The method as described in claim 15 wherein trustees reveal individual user keys of a given user for the purpose of enabling monitoring of communications relative to that user while preserving privacy of the communications of other users.

18. A method for enabling two users of a cryptosystem to generate and use a private pair key to encipher communications between the two users, comprising the steps of:

for each user and each trustee of a group of trustees, having at least one individual user key;

having at least one of the two users receive at least a public pair key for the two users;

having at least one of two users use a physical device to compute the private pair key from information that includes the user'"'"'s individual user key and the public pair key received by one of the users, wherein a subset of trustees containing less than a given number of trustees does not possess any useful information for reconstructing the private pair key, and wherein a subset of trustees containing more than a given number of trustees can reconstruct individual user keys of a given user for the purpose of enabling monitoring of communications relative to that user while preserving privacy of the communications of other users;

having one of the users generate a ciphertext using the private pair key; and

transmitting the ciphertext from the user to other user of the cryptosystem.

19. The method as described in claim 18 wherein at least some public pair keys are computed by an entity that cannot compute individual user keys.

20. The method as described in claim 19 wherein the entity is prevented from computing individual user keys because such keys are stored in physically-secure devices.

21. A method for enabling two users of a cryptosystem to generate and use a private pair key to encipher communications between the two users, comprising the steps of:

for each user and each trustee of a group of trustees, having at least one individual key;

having at least one of the two users receive from a trustee information for the two users from which the user derives and stores, in a physical device, key information;

having at least one of two users use the physical device to compute the private pair key from information that includes the user'"'"'s individual user key and the stored key information, wherein a subset of trustees containing less that a given number of trustees does not possess any useful information for reconstructing the private key;

a subset of trustees containing less than a given number of trustees does not possess any useful information for reconstructing the private pair key;

having one of the users generate a ciphertext using the private pair key; and

transmitting the ciphertext from the user to other user of the cryptosystem.

22. The method as described in claim 21 wherein the individual user key of each user is stored in a physically-secure device.

23. The method as described in claim 21 wherein a plurality of individual keys of a user are combined into a single individual key.

24. The method as described in claim 21 wherein at least some key information is computed by an entity that cannot compute individual keys.

25. The method as described in claim 29 wherein the entity is prevented from computing individual keys because such individual keys are stored in physically-secure devices.