Failsafe key escrow system

• US 5,647,000 A
• Filed: 09/03/1996
• Issued: 07/08/1997
• Est. Priority Date: 08/12/1994
• Status: Expired due to Fees

• Current Assignee: Frank Thomsen Leighton
• Original Assignee: Frank Thomsen Leighton
• Inventors: Leighton, Frank Thomsen
• Primary Examiner(s): Barron, Jr., Gilberto
• Application Number:
  US08/706,975
• Time in Patent Office: 308 Days
• Field of Search: 380/44, 380/28, 380/30
• US Class Current: 380/30
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

A method of generating cryptographic keys to implement a Failsafe Key Escrow system. A prime modulus Q and a generator G for Z_Q are publicly known. The public key P_X that is escrowed for user X is G^SX mod Q, where Sx is the secret key for user X. The user picks a random secret value A from [0, Q-2] and announces the value of G^A mod Q to a set of trustees or a central authority. Next the user "shares" A with the trustees using a verifiable secret sharing scheme. The trustees and/or the central authority selects a random value B from the interval [0, Q-2] and they set the user'"'"'s public key to be P_X =(G^A)G^B mod Q. The value of B is returned to the user and is escrowed with the public key for X. The value of B is not released to the public. The user'"'"'s then sets his secret key to be S_X =A+B mod (Q-1).

Claims

1. A method of generating cryptographic keys for use in securing communications among users in a cryptosystem having an authority and a plurality of trustees, where trustees must cooperate in a predetermined manner to reveal a secret key, comprising the steps of:

for each user, verifiably secret sharing a first seed value with the plurality of trustees, the first seed value alone being insufficient to reveal a secret key even if the trustees cooperate; and

for each user, generating a secret key by computing a given function of the first seed value associated with that user and a second seed value generated by the authority, wherein neither the user nor the authority can derive the given function from just their respective seed values.

2. The method as described in claim 1 further including the step of:

for each user, computing a public key from information derived from the first seed value associated with the user.

3. The method as described in claim 2 further including the step of:

escrowing the public key for each user.

4. The method as described in claim 1 wherein the first seed value is selected at random by each user.

5. The method as described in claim 4 wherein the first seed value is selected at random by each user prior to generation of the second seed value by the authority.

6. In a cryptosystem having a plurality of users, one or more trustees and a central authority, where the one or more trustees and the authority cooperate under predetermined circumstances to reveal a secret key, an improved method for generating and using cryptographic keys, comprising the unordered steps of:

for each user, generating a first seed value, shares of which are provided to the trustees so that the first seed value can be reconstructed if the trustees reveal their shares;

having the authority generate a second seed value; and

for each user, generating a secret key by computing a given function of the first seed value and the second seed value generated by the authority, wherein the given function cannot be derived from just the first seed value or from just the second seed value;

for each user, generating a public key for the secret key;

encrypting at least one message using a key derived according to a publicly-known process from the public key; and

having the authority and the trustees cooperate under a predetermined circumstance to reconstruct the secret key to thereby decrypt the message.

7. A method of securing communications among users in a cryptosystem having a plurality of trustees, comprising the unordered steps of:

for each user, verifiably secret sharing a first seed value with the plurality of trustees;

for each user, generating a secret key by computing a given function of the first seed value associated with that user and a second seed value, wherein the user cannot derive the given function from just the first seed value;

for each user, escrowing a public key associated with that user;

upon a predetermined occurrence, having a sufficient number of trustees cooperate to reveal the first seed value associated with a suspect user to enable reconstruction of that user'"'"'s secret key; and

having the authority use the reconstructed secret key and the public key of the suspect user to monitor communications.

8. The method as described in claim 7 wherein the first seed value is alone insufficient to enable the plurality of trustees to construct a secret key useful in monitoring communications.

9. The method as described in claim 7 wherein the public key for each user is computed from information derived from that user'"'"'s first seed value.

10. The method as described in claim 9 wherein the information is an encoded version of the user'"'"'s first seed value.