Server-assisted regeneration of a strong secret from a weak secret

• US 6,829,356 B1
• Filed: 05/17/2000
• Issued: 12/07/2004
• Est. Priority Date: 06/29/1999
• Status: Expired due to Term

• Current Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Original Assignee: VeriSign, Inc.
• Inventors: Ford, Warwick S
• Primary Examiner(s): Morse, Gregory
• Assistant Examiner(s): Lipman, Jacob
• Application Number:
  US09/574,687
• Time in Patent Office: 1,665 Days
• Field of Search: 713/171, 380/46, 380/286, 380/44, 380/277
• US Class Current: 380/44
• CPC Class Codes: A01K 2217/05 Animals comprising random inserted nucleic acids (transgenic)
• CPC Class Codes: A61K 38/00 Medicinal preparations containing peptides peptides containing beta-lactam rings A61K31/00; cyclic dipeptides not having in their molecule any other peptide link than those which form their ring, e.g. piperazine-2,5-diones, A61K31/00; ergot alkaloids of the cyclic peptide type A61K31/48; containing macromolecular compounds having statistically distributed amino acid units A61K31/74; medicinal preparations containing antigens or antibodies A61K39/00; medicinal preparations characterised by the non-active ingredients, e.g. peptides as drug carriers, A61K47/00
• CPC Class Codes: C07K 14/47 from mammals
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

Methods for regenerating a strong secret for a user, based on input of a weak secret, such as a password, are assisted by communications exchanges with a set of independent servers. Each server holds a distinct secret value (i.e., server secret data). The strong secret is a function of the user'"'"'s weak secret and of the server secret data, and a would-be attacker cannot feasibly compute the strong secret without access to both the user'"'"'s weak secret and the server secret data. Any attacker has only a limited opportunity to guess the weak secret, even if he has access to all messages transmitted in the generation and regeneration processes plus a subset (but not all) of the server secret data.

Claims

1. A method for enabling devices to securely regenerate a user'"'"'s strong secret data from weak secret data for the user, the method comprising:

determining the user'"'"'s weak secret data;

computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server, said computing secret components includes, for at least one secret holding server;

computing server request data for the secret holding server, wherein the server request data is a function of the weak secret data and of an ephemeral client secret, and the server request data does not reveal information about the weak secret data without knowledge of the ephemeral client secret,

receiving server response data from the secret holding server, wherein the server response data is a function of the server secret data for the secret holding server and of the server request data, and the server response data does not reveal information about the server secret data without knowledge of the weak secret data and the ephemeral client secret, and

computing the secret component for the secret holding server as a function of the server response data received from the secret holding server and of the ephemeral client secret, wherein the secret component is a function of the weak secret data and of the server secret data but is independent of the ephemeral client secret;

computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers; and

determining verifier data for each of at least two verification servers, wherein the verifier data for each verification server enables the verification server to verify that a device has successfully recovered the strong secret data but it is computationally infeasible for the verification server to determine the weak secret data based only on access to its verifier data.

2. The method of claim 1 wherein:

the server secret data for at least one secret holding server i includes a random integer b(i), where i is an index for the secret holding servers;

the step of computing the server request data for the secret holding server i comprises computing the value M=w^a wherein

w=f(weak secret data), wherein f is a function which generates an element of a finite group G in which exponentiation is efficient but the discrete logarithm problem is computationally infeasible; and

the ephemeral client secret includes the random integer a for which there exists a corresponding integer a′

such that x^aa′

=x for all x in the group G;

the step of receiving the server response data comprises receiving the value c(i)=M^b(i) wherein the exponentiation is computed in the group G; and

the step of computing the secret component comprises computing the value K(i)=h(c(i)^a′

) wherein h is a function and the exponentiation is computed in the group G.

3. The method of claim 2 wherein the group G is selected from:

a multiplicative group of the set of integers modulo p, where p is a large prime suitable as a Diffie-Hellman modulus; and

a group of points on an elliptic curve over a finite field.

4. A method for enabling devices to securely regenerate a user'"'"'s strong secret data from weak secret data for the user, the method comprising:

determining the user'"'"'s weak secret data;

computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server;

computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers;

encrypting private data for the user using the strong secret data as a cryptographic key in a symmetric cryptosystem; and

determining verifier data for each of at least two verification servers, wherein the verifier data for each verification server enables the verification server to verify that a device has successfully recovered the strong secret data but it is computationally infeasible for the verification server to determine the weak secret data based only on access to its verifier data, said determining verifier data includes, for at least one verification server, determining public data which corresponds to the user'"'"'s private data, wherein a first entity with access to the private data can prove said access to a second entity with access to the public data without disclosing the private data to the second entity.

5. A method for securely regenerating a user'"'"'s strong secret data from weak secret data for the user, the method comprising:

receiving the user'"'"'s weak secret data;

computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server, said computing secret components includes, for at least one secret holding server;

computing server request data for the secret holding server, wherein the server request data is a function of the weak secret data and of an ephemeral client secret, and the server request data does not reveal information about the weak secret data without knowledge of the ephemeral client secret,

receiving server response data from the secret holding server, wherein the server response data is a function of the server secret data for the secret holding server and of the server request data, and the server response data does not reveal information about the server secret data without knowledge of the weak secret data and the ephemeral client secret, and

computing the secret component for the secret holding server as a function of the server response data received from the secret holding server and of the ephemeral client secret, wherein the secret component is a function of the weak secret data and of the server secret data but is independent of the ephemeral client secret;

computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers;

determining proof data for proving to at least two verification servers that the strong secret data was successfully computed; and

transmitting the proof data to the verification servers.

6. The method of claim 5 wherein:

the server secret data for at least one secret holding server i includes a random integer b(i), where i is an index for the secret holding servers;

the step of computing the server request data for the secret holding server i comprises computing the value M=w^a wherein

w=f(weak secret data), wherein f is a function which generates an element of a finite group G in which exponentiation is efficient but the discrete logarithm problem is computationally infeasible; and

the ephemeral client secret includes the random integer a for which there exists a corresponding integer a′

such that x^aa′

=x for all x in the group G;

the step of receiving the server response data comprises receiving the value c(i)=M^b(i) wherein the exponentiation is computed in the group G; and

the step of computing the secret component comprises computing the value K(i)=h(c(i)^a′

) wherein h is a function and the exponentiation is computed in the group G.

7. The method of claim 6 wherein the group G is selected from:

a multiplicative group of the set of integers modulo p, where p is a large prime suitable as a Diffie-Hellman modulus; and

a group of points on an elliptic curve over a finite field.

8. A method for securely regenerating a user'"'"'s strong secret data from weak secret data for the user, the method comprising:

receiving the user'"'"'s weak secret data;

computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server, said computing secret components;

computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers;

obtaining encrypted private data for the user, wherein a first entity with access to the private data can prove said access to a second entity with access to corresponding public data without disclosing the private data to the second entity, and

decrypting the encrypted private data using the strong secret data as a cryptographic key in a symmetric cryptosystem;

determining proof data for proving to at least two verification servers that the strong secret data was successfully computed, said determining proof data includes, for at least one verification server, determining proof data based on the decrypted private data; and

transmitting the proof data to the verification servers.

9. The method of claim 8 wherein the step of determining proof data comprises:

determining proof data as a function of a nonce which distinguishes the proof data from other instances of proof data provided for the user.

10. The method of claim 9 wherein:

the user'"'"'s private data includes a private key for use in a digital signature system; and

the step of determining proof data comprises digitally signing a message containing the nonce using the private key.

11. A method for securely regenerating a user'"'"'s strong secret data from weak secret data for the user, the method comprising:

receiving the user'"'"'s weak secret data;

computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server;

computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers;

determining proof data for proving to at least two verification servers that the strong secret data was successfully computed, said determining proof data includes;

computing the proof data as a one-way function of the strong secret data, and

determining the proof data as a function of a nonce which distinguishes the proof data from other instances of proof data provided for the user; and

transmitting the proof data to the verification servers.

12. The method of claim 11 wherein the step of determining proof data comprises:

computing verifier data for the verification server as a one-way function of the strong secret data; and

computing the proof data as a one-way function of the verifier data and the nonce.

13. A method for securely regenerating a user'"'"'s strong secret data from weak secret data for the user, the method comprising:

receiving the user'"'"'s weak secret data;

computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server;

computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers;

determining proof data for proving to at least two verification servers that the strong secret data was successfully computed;

transmitting the proof data to the verification servers;

determining token possession proof data for proving presence of a user'"'"'s hardware token; and

transmitting the token possession proof data to at least one server selected from a group of consisting of the secret holding servers and the verification servers.

14. A method for securely regenerating a user'"'"'s strong secret data from weak secret data for the user, the method comprising:

receiving the user'"'"'s weak secret data;

computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server;

computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers;

determining proof data for proving to at least two verification servers that the strong secret data was successfully computed, said determining proof data includes determining the proof data as a function of user data which the verification server can authenticate as originating from the user; and

transmitting the proof data to the verification servers.

15. The method of claim 14 further comprising:

receiving digital signature components from at least two verification servers, wherein the user data comprises a user-originated message, and

computing a digital signature of the user-originated message as a function of digital signature components.

16. A method for facilitating secure regeneration of a user'"'"'s strong secret data from weak secret data for the user, the method comprising:

receiving server request data from a device attempting to recover a user'"'"'s strong secret data, wherein;

the strong secret data is a function of the user'"'"'s weak secret data and of the server secret data for at least one secret holding server, and

the server request data is a function of the weak secret data and of an ephemeral client secret, and the server request data does not reveal information about the weak secret data without knowledge of the ephemeral client secret;

computing server response data as a function of server secret data for the user and the server request data, and the server response data does not reveal information about the server secret data without knowledge of the weak secret data and the ephemeral client secret; and

transmitting the server response data to the device responsive to a determination that it is unlikely that a party without access to the weak secret data is attempting to regenerate the strong secret data.

17. The method of claim 16 wherein:

the server secret data includes a random integer b;

the server request data includes a value M=w^a, where

w=f(user secret data), wherein f is a function which generates an element of a finite group G in which exponentiation is efficient but the discrete logarithm problem is computationally infeasible;

a is an ephemeral client secret; and

the exponentiation w^a is computed in the group G; and

the step of computing the server response data includes computing a value M^b wherein the exponentiation is computed in the group G.

18. The method of claim 17 wherein the group G is selected from:

a multiplicative group of the set of integers modulo p, where p is a large prime suitable as a Diffie-Hellman modulus; and

a group of points on an elliptic curve over a finite field.

19. The method of claim 16 wherein the server response data includes a nonce which distinguishes the server response data from other instances of server response data provided by the secret holding server for the user.

20. The method of claim 16 further comprising:

accessing verifier data, wherein the verifier data enables a verification server to verify that a device has successfully recovered the strong secret data;

receiving proof data from the device;

responsive to the verifier data and the proof data received from the device, determining whether the device has successfully regenerated the strong secret data; and

responsive to a determination that the device has not successfully recovered the strong secret data, updating a record of unsuccessful attempts to recover the strong secret data.

21. The method of claim 20 wherein:

the verifier data includes public data which corresponds to a user'"'"'s private data, wherein a first entity with access to the private data can prove said access to a second entity with access to the public data without disclosing the private data to the second entity; and

the step of determining whether the device has successfully recovered the strong secret data comprises determining whether the proof data proves that the device has access to the private data.

22. The method of claim 21 wherein:

the step of determining whether the device has successfully recovered the strong secret data further comprises determining whether the proof data proves that the device has access to a nonce which confirms freshness of the proof data.

23. The method of claim 22 wherein:

the user'"'"'s private data includes a private key for use in a digital signature system;

the proof data includes digitally signed data which allegedly contains the nonce and allegedly has been digitally signed using the private key;

the step of determining whether the proof data proves that the device has access to the private data includes verifying that the digitally signed data has been digitally signed using the private key; and

the step of determining whether the proof data proves that the device has access to the nonce includes verifying that the digitally signed data contains the nonce or a value derived from the nonce.

24. The method of claim 20 wherein:

the verifier data is a one-way function of the strong secret data; and

the step of determining whether the device has successfully recovered the strong secret data comprises determining whether the proof data proves that the device can compute the verifier data.

25. The method of claim 24 wherein:

the step of determining whether the device has successfully recovered the strong secret data further comprises determining whether the proof data proves that the device has access to a nonce which confirms freshness of the proof data.

26. The method of claim 25 wherein the step of determining whether the device has successfully recovered the strong secret data comprises:

computing an expected proof data as a one-way function of the verifier data and the nonce; and

comparing the expected proof data with the proof data received from the device.

27. The method of claim 16 further comprising:

accessing verifier data, wherein the verifier data enables a verification server to verify that a device has successfully recovered the strong secret data;

receiving proof data from the device, the proof data including a user-originated message to be digitally signed;

responsive to the verifier data and the proof data received from the device, determining whether the device has successfully regenerated the strong secret data; and

responsive to a determination that the device has successfully recovered the strong secret data, generating a digital signature component based on the user-originated message, wherein a digital signature of the user-originated message is a function of the digital signature components for at least two verification servers; and

transmitting the digital signature component to the device.

28. The method of claim 16 further comprising:

receiving token possession proof data for proving presence of a user'"'"'s hardware token;

wherein the step of transmitting server response data to the device is responsive to a determination that the user'"'"'s hardware token is present.

29. A method for enabling devices to securely regenerate a user'"'"'s strong secret data from weak secret data for the user, the method comprising:

determining the user'"'"'s weak secret data;

computing server request data for a secret holding server, wherein the server request data is a function of the weak secret data and of an ephemeral client secret, and the server request data does not reveal information about the weak secret data without knowledge of the ephemeral client secret;

receiving server response data from the secret holding server, wherein the server response data is a function of the server secret data for the secret holding server and of the server request data, and the server response data does not reveal information about the server secret data without knowledge of the weak secret data and the ephemeral client secret;

computing a secret component for the secret holding server as a function of the server response data received from the secret holding server and of the ephemeral client secret, wherein the secret component is a function of the weak secret data and of the server secret data but is independent of the ephemeral client secret;

computing the user'"'"'s strong secret data as a function of the secret component; and

determining verifier data for at least one verification server, wherein the verifier data enables the verification server to verify that a device has successfully recovered the strong secret data but it is computationally infeasible for the verification server to determine the weak secret data based only on access to its verifier data.

30. The method of claim 29 wherein:

the server secret data includes a random integer b;

the secret component is a value K=h(w^b), wherein

h is a function;

w=f(weak secret data), wherein f is a function which generates an element of a finite group G in which exponentiation is efficient but the discrete logarithm problem is computationally infeasible; and

the exponentiation w^b is computed in the group G;

the ephemeral client secret is a random integer a for which there exists a corresponding integer a′

such that x^aa′

=x for all x in group G;

the server request data is computed as the value M=w^a wherein the exponentiation is computed in the group G;

the server response data is computed as the value c=M^b wherein the exponentiation is computed in the group G; and

the secret component is computed as the value K=h(c^a′

) wherein the exponentiation is computed in the group G.

31. The method of claim 30 wherein the group G is selected from:

a multiplicative group of the set of integers modulo p, where p is a large prime suitable as a Diffie-Hellman modulus; and

a group of points on an elliptic curve over a finite field.

32. The method of claim 29 further comprising:

encrypting private data for the user using the strong secret data as a cryptographic key in a symmetric cryptosystem;

wherein

the step of determining verifier data includes determining public data which corresponds to the user'"'"'s private data, wherein a first entity with access to the private data can prove said access to a second entity with access to the public data without disclosing the private data to the second entity.

33. The method of claim 29 wherein the step of determining verifier data comprises computing verifier data as a one-way function of the strong secret data.

34. A method for securely regenerating a user'"'"'s strong secret data from weak secret data for the user, the method comprising:

receiving the user'"'"'s weak secret data;

computing server request data for a secret holding server, wherein the server request data is a function of the weak secret data and of an ephemeral client secret, and the server request data does not reveal information about the weak secret data without knowledge of the ephemeral client secret;

receiving server response data from the secret holding server, wherein the server response data is a function of the server secret data for the secret holding server and of the server request data, and the server response data does not reveal information about the server secret data without knowledge of the weak secret data and the ephemeral client secret;

computing a secret component for the secret holding server as a function of the server response data received from the secret holding server and of the ephemeral client secret, wherein the secret component is a function of the weak secret data and of the server secret data but is independent of the ephemeral client secret;

computing the user'"'"'s strong secret data as a function of the secret component;

determining proof data for proving to at least one verification server that the strong secret data was successfully computed; and

transmitting the proof data to the verification servers.

35. The method of claim 34 wherein:

the server secret data includes a random integer b; and

the secret component is a value K=h(w^b), wherein

h is a function;

w=f(weak secret data), wherein f is a function which generates an element of a finite group G in which exponentiation is efficient but the discrete logarithm problem is computationally infeasible; and

the exponentiation w^b is computed in the group G;

the ephemeral client secret is a random integer a for which there exists a corresponding integer a′

such that x^aa′

=x for all x in group G;

the server request data is computed as the value M=w^a wherein the exponentiation is computed in the group G;

the server response data is computed as the value c=M^b wherein the exponentiation is computed in the group G; and

the secret component is computed as the value K=h(c^a′

) wherein the exponentiation is computed in the group G.

36. The method of claim 35 wherein the group G is selected from:

a multiplicative group of the set of integers modulo p, where p is a large prime suitable as a Diffie-Hellman modulus; and

a group of points on an elliptic curve over a finite field.

37. The method of claim 34 further comprising:

obtaining encrypted private data for the user, wherein a first entity with access to the private data can prove said access to a second entity with access to corresponding public data without disclosing the private data to the second entity; and

decrypting the encrypted private data using the strong secret data as a cryptographic key in a symmetric cryptosystern;

wherein

the step of determining proof data comprises computing proof data based on the decrypted private data.

38. The method of claim 37 wherein the step of determining proof data comprises determining proof data as a function of a nonce which distinguishes the proof data from other instances of proof data provided for the user.

39. The method of claim 38 wherein:

the user'"'"'s private data includes a private key for use in a digital signature system; and

the step of determining proof data comprises digitally signing a message containing the nonce using the private key.

40. The method of claim 34 wherein the step of determining proof data comprises computing proof data as a one-way function of the strong secret data.

41. The method of claim 40 wherein:

the step of determining proof data comprises determining the proof data as a function of a nonce which distinguishes the proof data from other instances of proof data provided for the user.

42. The method of claim 41 wherein the step of determining proof data comprises:

computing verifier data as a one-way function of the strong secret data; and

computing the proof data as a one-way function of the verifier data and of the nonce.

43. The method of claim 34 further comprising:

determining token possession proof data for proving presence of a user'"'"'s hardware token; and

transmitting the token possession proof data to at least one server selected from a group consisting of the secret holding servers and the verification servers.

44. A computer program product having instructions executable by a generating client for instructing the generating client to perform method steps for enabling devices to securely regenerate a user'"'"'s strong secret data from weak secret data for the user, the method steps comprising:

determining the user'"'"'s weak secret data;

computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of the server secret data for the secret holding server, said computing secret components includes, for at least one secret holding server;

computing server request data for the secret holding server, wherein the server request data is a function of the weak secret data and of an ephemeral client secret, and the server request data does not reveal information about the weak secret data without knowledge of the ephemeral client secret,

receiving server response data from the secret holding server, wherein the server response data is a function of the server secret data for the secret holding server and of the server request data, and the server response data does not reveal information about the server secret data without knowledge of the weak secret data and the ephemeral client secret, and

computing the secret component for the secret holding server as a function of the server response data received from the secret holding server and of the ephemeral client secret, wherein the secret component is a function of the weak secret data and of the server secret data but is independent of the ephemeral client secret;

computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers; and

determining verifier data for each of at least two verification servers, wherein the verifier data for each verification server enables the verification server to verify that a device has successfully recovered the strong secret data but it is computationally infeasible for the verification server to determine the weak secret data based only on access to its verifier data.

45. The computer program product of claim 44 wherein:

the server secret data for at least one secret holding server i includes a random integer b(i), where i is an index for the secret holding servers;

the step of computing the server request data for the secret holding server i comprises computing the value M=w^a wherein

w=f(weak secret data), wherein f is a function which generates an element of a finite group G in which exponentiation is efficient but the discrete logarithm problem is computationally infeasible; and

the ephemeral client secret includes the random integer a for which there exists a corresponding integer a′

such that x^aa′

=x for all x in the group G;

the step of receiving the server response data comprises receiving the value c(i)=M^b(i) wherein the exponentiation is computed in the group G; and

the step of computing the secret component comprises computing the value K(i)=h(c(i)^a′

) wherein h is a function and the exponentiation is computed in the group G.

46. The computer program product of claim 45 wherein the group G is selected from:

a multiplicative group of the set of integers modulo p, where p is a large prime suitable as a Diffie-Hellman modulus; and

a group of points on an elliptic curve over a finite field.

47. A computer program product having instructions executable by a generating client for instructing the generating client to perform method steps for enabling devices to securely regenerate a user'"'"'s strong secret data from weak secret data for the user, the method steps comprising:

determining the user'"'"'s weak secret data;

computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server;

computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers;

encrypting private data for the user using the strong secret data as a cryptographic key in a symmetric cryptosystem; and

determining verifier data for each of at least two verification servers, wherein the verifier data for each verification server enables the verification server to verify that a device has successfully recovered the strong secret data but it is computationally infeasible for the verification server to determine the weak secret data based only on access to its verifier data, said determining verifier data includes, for at least one verification server, determining public data which corresponds to the user'"'"'s private data, wherein a first entity with access to the private data can prove said access to a second entity with access to the public data without disclosing the private data to the second entity.

48. A computer program product having instructions executable by a generating client for instructing the generating client to perform method steps for enabling devices to securely regenerate a user'"'"'s strong secret data from weak secret data for the user, the method steps comprising:

receiving the user'"'"'s weak secret data;

computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server, said computing secret components includes, for at least one secret holding server;

computing server request data for the secret holding server, wherein the server request data is a function of the weak secret data and of an ephemeral client secret, and the server request data does not reveal information about the weak secret data without knowledge of the ephemeral client secret,

receiving server response data from the secret holding server, wherein the server response data is a function of the server secret data for the secret holding server and of the server request data, and the server response data does not reveal information about the server secret data without knowledge of the weak secret data and the ephemeral client secret, and

computing the secret component for the secret holding server as a function of the server response data received from the secret holding server and of the ephemeral client secret, wherein the secret component is a function of the weak secret data and of the server secret data but is independent of the ephemeral client secret;

computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers;

determining proof data for proving to at least two verification servers that the strong secret data was successfully computed; and

transmitting the proof data to the verification servers.

49. The computer program product of claim 48 wherein:

the server secret data for at least one secret holding server i includes a random integer b(i), where i is an index for the secret holding servers;

the step of computing the server request data for the secret holding server i comprises computing the value M=w^a wherein

w=f(weak secret data), wherein f is a function which generates an element of a finite group G in which exponentiation is efficient but the discrete logarithm problem is computationally infeasible; and

the ephemeral client secret includes the random integer a for which there exists a corresponding integer a′

such that x^aa′

=x for all x in the group G;

the step of receiving the server response data comprises receiving the value c(i)=M^b(i) wherein

the exponentiation is computed in the group G; and

the step of computing the secret component comprises computing the value K(i)=h(c(i)^a′

) wherein h is a function and the exponentiation is computed in the group G.

50. The computer program product of claim 49 wherein the group G is selected from:

a multiplicative group of the set of integers modulo p, where p is a large prime suitable as a Diffie-Hellman modulus; and

a group of points on an elliptic curve over a finite field.

51. A computer program product having instructions executable by a generating client for instructing the generating client to perform method steps for enabling devices to securely regenerate a user'"'"'s strong secret data from weak secret data for the user, the method steps comprising:

receiving the user'"'"'s weak secret data;

computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server, said computing secret components;

computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers;

obtaining encrypted private data for the user, wherein a first entity with access to the private data can prove said access to a second entity with access to corresponding public data without disclosing the private data to the second entity, and

decrypting the encrypted private data using the strong secret data as a cryptographic key in a symmetric cryptosystem;

determining proof data for proving to at least two verification servers that the strong secret data was successfully computed, said determining proof data includes, for at least one verification server, determining proof data based on the decrypted private data; and

transmitting the proof data to the verification servers.

52. The computer program product of claim 51 wherein the step of determining proof data comprises:

determining proof data as a function of a nonce which distinguishes the proof data from other instances of proof data provided for the user.

53. The computer program product of claim 52 wherein:

the user'"'"'s private data includes a private key for use in a digital signature system; and

the step of determining proof data comprises digitally signing a message containing the nonce using the private key.

54. A computer program product having instructions executable by a generating client for instructing the generating client to perform method steps for enabling devices to securely regenerate a user'"'"'s strong secret data from weak secret data for the user, the method steps comprising:

receiving the user'"'"'s weak secret data;

computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server;

computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers;

determining proof data for proving to at least two verification servers that the strong secret data was successfully computed, said determining proof data includes;

computing the proof data as a one-way function of the strong secret data, and

determining the proof data as a function of a nonce which distinguishes the proof data from other instances of proof data provided for the user; and

transmitting the proof data to the verification servers.

55. The computer program product of claim 54 wherein the step of determining proof data comprises:

computing verifier data for the verification server as a one-way function of the strong secret data; and

computing the proof data as a one-way function of the verifier data and the nonce.

56. A computer program product having instructions executable by a generating client for instructing the generating client to perform method steps for enabling devices to securely regenerate a user'"'"'s strong secret data from weak secret data for the user, the method steps comprising:

receiving the user'"'"'s weak secret data;

computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server;

computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers;

determining proof data for proving to at least two verification servers that the strong secret data was successfully computed;

transmitting the proof data to the verification servers;

determining token possession proof data for proving presence of a user'"'"'s hardware token; and

transmitting the token possession proof data to at least one server selected from a group of consisting of the secret holding servers and the verification servers.

57. A computer program product having instructions executable by a generating client for instructing the generating client to perform method steps for enabling devices to securely regenerate a user'"'"'s strong secret data from weak secret data for the user, the method steps comprising:

receiving the user'"'"'s weak secret data;

computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server;

computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers;

determining proof data for proving to at least two verification servers that the strong secret data was successfully computed, said determining proof data includes determining the proof data as a function of user data which the verification server can authenticate as originating from the user; and

transmitting the proof data to the verification servers.

58. The computer program product of claim 57 wherein the method steps further comprise:

receiving digital signature components from at least two verification servers, wherein the user data comprises a user-originated message, and

computing a digital signature of the user-originated message as a function of digital signature components.

59. A computer program product having instructions executable by a server for instructing the server to perform method steps for facilitating secure regeneration of a user'"'"'s strong secret data from weak secret data for the user, the method steps comprising:

receiving server request data from a device attempting to recover a user'"'"'s strong secret data, wherein;

the strong secret data is a function of the user'"'"'s weak secret data and of the server secret data for at least one secret holding server, and

the server request data is a function of the weak secret data and of an ephemeral client secret, and the server request data does not reveal information about the weak secret data without knowledge of the ephemeral client secret;

computing server response data as a function of server secret data for the user and the server request data, and the server response data does not reveal information about the server secret data without knowledge of the weak secret data and the ephemeral client secret; and

transmitting the server response data to the device responsive to a determination that it is unlikely that a party without access to the weak secret data is attempting to regenerate the strong secret data.

60. The computer program product of claim 59 wherein:

the server secret data includes a random integer b;

the server request data includes a value M=w^a, where

w=f(user secret data), wherein f is a function which generates an element of a finite group G in which exponentiation is efficient but the discrete logarithm problem is computationally infeasible;

a is an ephemeral client secret; and

the exponentiation w^a is computed in the group G; and

the step of computing the server response data includes computing a value M^b wherein the exponentiation is computed in the group G.

61. The computer program product of claim 60 wherein the group G is selected from:

a multiplicative group of the set of integers modulo p, where p is a large prime suitable as a Diffie-Hellman modulus; and

a group of points on an elliptic curve over a finite field.

62. The computer program product of claim 59 wherein the server response data includes a nonce which distinguishes the server response data from other instances of server response data provided by the secret holding server for the user.

63. The computer program product of claim 59 wherein the method steps further comprise:

accessing verifier data, wherein the verifier data enables a verification server to verify that a device has successfully recovered the strong secret data;

receiving proof data from the device;

responsive to the verifier data and the proof data received from the device, determining whether the device has successfully regenerated the strong secret data; and

responsive to a determination that the device has not successfully recovered the strong secret data, updating a record of unsuccessful attempts to recover the strong secret data.

64. The computer program product of claim 63 wherein:

the verifier data includes public data which corresponds to a user'"'"'s private data, wherein a first entity with access to the private data can prove said access to a second entity with access to the public data without disclosing the private data to the second entity; and

the step of determining whether the device has successfully recovered the strong secret data comprises determining whether the proof data proves that the device has access to the private data.

65. The computer program product of claim 64 wherein:

the step of determining whether the device has successfully recovered the strong secret data further comprises determining whether the proof data proves that the device has access to a nonce which confirms freshness of the proof data.

66. The computer program product of claim 65 wherein:

the user'"'"'s private data includes a private key for use in a digital signature system;

the proof data includes digitally signed data which allegedly contains the nonce and allegedly has been digitally signed using the private key;

the step of determining whether the proof data proves that the device has access to the private data includes verifying that the digitally signed data has been digitally signed using the private key; and

the step of determining whether the proof data proves that the device has access to the nonce includes verifying that the digitally signed data contains the nonce or a value derived from the nonce.

67. The computer program product of claim 63 wherein:

the verifier data is a one-way function of the strong secret data; and

the step of determining whether the device has successfully recovered the strong secret data comprises determining whether the proof data proves that the device can compute the verifier data.

68. The computer program product of claim 67 wherein:

the step of determining whether the device has successfully recovered the strong secret data further comprises determining whether the proof data proves that the device has access to a nonce which confirms freshness of the proof data.

69. The computer program product of claim 68 wherein the step of determining whether the device has successfully recovered the strong secret data comprises:

computing an expected proof data as a one-way function of the verifier data and the nonce; and

comparing the expected proof data with the proof data received from the device.

70. The computer program product of claim 59 wherein the method steps further comprise:

accessing verifier data, wherein the verifier data enables a verification server to verify that a device has successfully recovered the strong secret data;

receiving proof data from the device, the proof data including a user-originated message to be digitally signed;

responsive to the verifier data and the proof data received from the device, determining whether the device has successfully regenerated the strong secret data; and

responsive to a determination that the device has successfully recovered the strong secret data, generating a digital signature component based on the user-originated message, wherein a digital signature of the user-originated message is a function of the digital signature components for at least two verification servers; and

transmitting the digital signature component to the device.

71. The computer program product of claim 59 wherein the method steps further comprise:

receiving token possession proof data for proving presence of a user'"'"'s hardware token;

wherein the step of transmitting server response data to the device is responsive to a determination that the user'"'"'s hardware token is present.

72. A computer program product having instructions executable by a generating client for instructing the generating client to perform method steps for enabling devices to securely regenerate a user'"'"'s strong secret data from weak secret data for the user, the method steps comprising:

determining the user'"'"'s weak secret data;

computing server request data for a secret holding server, wherein the server request data is a function of the weak secret data and, of an ephemeral client secret, and the server request data does not reveal information about the weak secret data without knowledge of the ephemeral client secret;

receiving server response data from the secret holding server, wherein the server response data is a function of the server secret data for the secret holding server and of the server request data, and the server response data does not reveal information about the server secret data without knowledge of the weak secret data and the ephemeral client secret;

computing a secret component for the secret holding server as a function of the server response data received from the secret holding server and of the ephemeral client secret, wherein the secret component is a function of the weak secret data and of the server secret data but is independent of the ephemeral client secret;

computing the user'"'"'s strong secret data as a function of the secret component; and

determining verifier data for at least one verification server, wherein the verifier data enables the verification server to verify that a device has successfully recovered the strong secret data but it is computationally infeasible for the verification server to determine the weak secret data based only on access to its verifier data.

73. The computer program product of claim 72 wherein:

the server secret data includes a random integer b;

the secret component is a value K=h(w^b), wherein

h is a function;

w=f(weak secret data), wherein f is a function which generates an element of a finite group G in which exponentiation is efficient but the discrete logarithm problem is computationally infeasible; and

the exponentiation w^b is computed in the group G;

the ephemeral client secret is a random integer a for which there exists a corresponding integer a′

such that x^aa′

=x for all x in group G;

the server request data is computed as the value M=w^a wherein the exponentiation is computed in the group G;

the server response data is computed as the value c=M^b wherein the exponentiation is computed in the group G; and

the secret component is computed as the value K=h(c^a′

) wherein the exponentiation is computed in the group G.

74. The computer program product of claim 73 wherein the group G is selected from:

a multiplicative group of the set of integers modulo p, where p is a large prime suitable as a Diffie-Hellman modulus; and

a group of points on an elliptic curve over a finite field.

75. The computer program product of claim 73 wherein the method steps further comprise:

encrypting private data for the user using the strong secret data as a cryptographic key in a symmetric cryptosystem;

wherein

the step of determining verifier data includes determining public data which corresponds to the user'"'"'s private data, wherein a first entity with access to the private data can prove said access to a second entity with access to the public data without disclosing the private data to the second entity.

76. The computer program product of claim 72 wherein the step of determining verifier data comprises computing verifier data as a one-way function of the strong secret data.

77. A computer program product having instructions executable by a recovery client for instructing the recovery client to perform method steps for enabling devices to securely regenerate a user'"'"'s strong secret data from weak secret data for the user, the method steps comprising:

receiving the user'"'"'s weak secret data;

computing server request data for a secret holding server, wherein the server request data is a function of the weak secret data and of an ephemeral client secret, and the server request data does not reveal information about the weak secret data without knowledge of the ephemeral client secret;

receiving server response data from the secret holding server, wherein the server response data is a function of the server secret data for the secret holding server and of the server request data, and the server response data does not reveal information about the server secret data without knowledge of the weak secret data and the ephemeral client secret;

computing a secret component for the secret holding server as a function of the server response data received from the secret holding server and of the ephemeral client secret, wherein the secret component is a function of the weak secret data and of the server secret data but is independent of the ephemeral client secret;

computing the user'"'"'s strong secret data as a function of the secret component;

determining proof data for proving to at least one verification server that the strong secret data was successfully computed; and

transmitting the proof data to the verification servers.

78. The computer program product of claim 77 wherein:

the server secret data includes a random integer b; and

the secret component is a value K=h(w^b), wherein

h is a function;

w=f(weak secret data), wherein f is a function which generates an element of a finite group G in which exponentiation is efficient but the discrete logarithm problem is computationally infeasible; and

the exponentiation w^b is computed in the group G;

the ephemeral client secret is a random integer a for which there exists a corresponding integer a′

such that x^aa′

=x for all x in group G;

the server request data is computed as the value M=w^a wherein the exponentiation is computed in the group G;

the server response data is computed as the value c=M^b wherein the exponentiation is computed in the group G; and

the secret component is computed as the value K=h(c^a′

) wherein the exponentiation is computed in the group G.

79. The computer program product of claim 78 wherein the group G is selected from:

a multiplicative group of the set of integers modulo p, where p is a large prime suitable as a Diffie-Hellman modulus; and

a group of points on an elliptic curve over a finite field.

80. The computer program product of claim 77 wherein the method steps further comprise:

obtaining encrypted private data for the user, wherein a first entity with access to the private data can prove said access to a second entity with access to corresponding public data without disclosing the private data to the second entity; and

decrypting the encrypted private data using the strong secret data as a cryptographic key in a symmetric cryptosystern;

wherein

the step of determining proof data comprises computing proof data based on the decrypted private data.

81. The computer program product of claim 80 wherein the step of determining proof data comprises determining proof data as a function of a nonce which distinguishes the proof data from other instances of proof data provided for the user.

82. The computer program product of claim 81 wherein:

the user'"'"'s private data includes a private key for use in a digital signature system; and

the step of determining proof data comprises digitally signing a message containing the nonce using the private key.

83. The computer program product of claim 77 wherein the step of determining proof data comprises computing proof data as a one-way function of the strong secret data.

84. The computer program product of claim 83 wherein:

the step of determining proof data comprises determining the proof data as a function of a nonce which distinguishes the proof data from other instances of proof data provided for the user.

85. The computer program product of claim 84 wherein the step of determining proof data comprises:

computing verifier data as a one-way function of the strong secret data; and

computing the proof data as a one-way function of the verifier data and of the nonce.

86. The computer program product of claim 77 wherein the method steps further comprise:

determining token possession proof data for proving presence of a user'"'"'s hardware token; and

transmitting the token possession proof data to at least one server selected from a group consisting of the secret holding servers and the verification servers.

87. A system for enabling devices to securely regenerate a user'"'"'s strong secret data from weak secret data for the user, the system comprising:

a generating client and at least two secret holding servers coupled to the generating client, for executing the following method steps;

the generating client determining the user'"'"'s weak secret data;

each secret holding server and the generating client computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server, said computing secret components includes, for at least one secret holding server;

the generating client computing and transmitting server request data to the secret holding server, wherein the server request data is a function of the weak secret data and of an ephemeral client secret, and the server request data does not reveal information about the weak secret data without knowledge of the ephemeral client secret,

the secret holding server computing and transmitting server response data to the generating client, wherein the server response data is a function of the server secret data for the secret holding server and of the server request data, and the server response data does not reveal information about the server secret data without knowledge of the weak secret data and the ephemeral client secret, and

the generating client computing the secret component for the secret holding server as a function of the server response data received from the secret holding server and of the ephemeral client secret, wherein the secret component is a function of the weak secret data and of the server secret data but is independent of the ephemeral client secret;

the generating client computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers; and

the generating client determining verifier data for each of at least two verification servers, wherein the verifier data for each verification server enables the verification server to verify that a device has successfully recovered the strong secret data but it is computationally infeasible for the verification server to determine the weak secret data based only on access to its verifier data.

88. The system of claim 87 wherein:

the server secret data for at least one secret holding server i includes a random integer b(i), where i is an index for the secret holding servers;

the step of computing the server request data for the secret holding server i comprises computing the value M=w^a wherein

w=f(weak secret data), wherein f is a function which generates an element of a finite group G in which exponentiation is efficient but the discrete logarithm problem is computationally infeasible; and

the ephemeral client secret includes the random integer a for which there exists a corresponding integer a′

such that x^aa′

=x for all x in the group G;

the step of receiving the server response data comprises receiving the value c(i)=M^b(i) wherein the exponentiation is computed in the group G; and

the step of computing the secret component comprises computing the value K(i)=h(c(i)^a′

) wherein h is a function and the exponentiation is computed in the group G.

89. The system of claim 88 wherein the group G is selected from:

a multiplicative group of the set of integers modulo p, where p is a large prime suitable as a Diffie-Hellman modulus; and

a group of points on an elliptic curve over a finite field.

90. A system for enabling devices to securely regenerate a user'"'"'s strong secret data from weak secret data for the user, the system comprising:

a generating client and at least two secret holding servers coupled to the generating client, for executing the following method steps;

the generating client determining the user'"'"'s weak secret data;

each secret holding server and the generating client computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server, said computing secret components includes, for at least one secret holding server;

the generating client encrypting private data for the user using the strong secret data as a cryptographic key in a symmetric cryptosystem; and

the generating client determining verifier data for each of at least two verification servers, wherein the verifier data for each verification server enables the verification server to verify that a device has successfully recovered the strong secret data but it is computationally infeasible for the verification server to determine the weak secret data based only on access to its verifier data, said determining verifier data includes, for at least one verification server, determining public data which corresponds to the user'"'"'s private data, wherein a first entity with access to the private data can prove said access to a second entity with access to the public data without disclosing the private data to the second entity.

91. A system for securely regenerating a user'"'"'s strong secret data from weak secret data for the user, the system comprising:

a recovery client and at least two secret holding servers coupled to the recovery client, for executing the following method steps;

the recovery client receiving the user'"'"'s weak secret data;

each secret holding server and the recovery client computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server, said computing secret components includes, for at least one secret holding server;

the recovery client computing and transmitting server request data to the secret holding server, wherein the server request data is a function of the weak secret data and of an ephemeral client secret, and the server request data does not reveal information about the weak secret data without knowledge of the ephemeral client secret,

the secret holding server computing and transmitting server response data to the recovery client responsive to a determination that it is unlikely that a party without access to the weak secret data is attempting to regenerate the strong secret data, wherein the server response data is a function of the server secret data for the secret holding server and of the server request data, and the server response data does not reveal information about the server secret data without knowledge of the weak secret data and the ephemeral client secret, and

the recovery client computing the secret component for the secret holding server as a function of the server response data received from the secret holding server and of the ephemeral client secret, wherein the secret component is a function of the weak secret data and of the server secret data but is independent of the ephemeral client secret;

the recovery client computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers;

the recovery client determining proof data for proving to at least two verification servers that the strong secret data was successfully computed.

92. The system of claim 91 wherein:

the server secret data for at least one secret holding server i includes a random integer b(i), where i is an index for the secret holding servers;

the step of computing the server request data for the secret holding server i comprises computing the value M=w^a wherein

w=f(weak secret data), wherein f is a function which generates an element of a finite group G in which exponentiation is efficient but the discrete logarithm problem is computationally infeasible; and

the ephemeral client secret includes the random integer a for which there exists a corresponding integer a′

such that x^aa′

=x for all x in the group G;

the step of computing the server response data comprises receiving the value c(i)=M^b(i)wherein the exponentiation is computed in the group G; and

the step of computing the secret component comprises computing the value K(i)=h(c(i)^a′

) wherein h is a function and the exponentiation is computed in the group G.

93. The system of claim 92 wherein the group G is selected from:

a multiplicative group of the set of integers modulo p, where p is a large prime suitable as a Diffie-Hellman modulus; and

a group of points on an elliptic curve over a finite field.

94. The system of claim 91 wherein the server response data includes a nonce which distinguishes the server response data from other instances of server response data provided by the secret holding server for the user.

95. A system for securely regenerating a user'"'"'s strong secret data from weak secret data for the user, the system comprising:

a recovery client and at least two secret holding servers coupled to the recovery client, for executing the following method steps;

the recovery client receiving the user'"'"'s weak secret data;

each secret holding server and the recovery client computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server;

the recovery client computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers;

the recovery client determining proof data for proving to at least two verification servers that the strong secret data was successfully computed;

the recovery client obtaining encrypted private data for the user, wherein a first entity with access to the private data can prove said access to a second entity with access to corresponding public data without disclosing the private data to the second entity; and

the recovery client decrypting the encrypted private data using the strong secret data as a cryptographic key in a symmetric cryptosystem;

wherein

the step of determining proof data for the verification servers comprises, for at least one verification server, determining proof data based on the decrypted private data.

96. A system for securely regenerating a user'"'"'s strong secret data from weak secret data for the user, the system comprising:

a recovery client, at least two secret holding servers coupled to the recovery client and at least two verification servers coupled to the recovery client, for executing the following method steps;

the recovery client receiving the user'"'"'s weak secret data;

each secret holding server and the recovery client computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server;

the recovery client computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers;

the recovery client determining proof data for proving to the verification servers that the strong secret data was successfully computed;

the recovery client transmitting the proof data to the verification servers;

each verification server accessing verifier data, wherein the verifier data enables the verification server to verify that the recovery client has successfully recovered the strong secret data;

responsive to the verifier data and the proof data received from the recovery client, each verification server determining whether the recovery client has successfully recovered the strong secret data; and

responsive to a determination that the recovery client has not successfully recovered the strong secret data, each verification server updating a record of unsuccessful attempts to recover the strong secret data.

97. The system of claim 96 wherein:

the verifier data includes public data which corresponds to a user'"'"'s private data, wherein a first entity with access to the private data can prove said access to a second entity with access to the public data without disclosing the private data to the second entity; and

the step of determining whether the recovery client has successfully recovered the strong secret data comprises determining whether the proof data proves that the recovery client has access to the private data.

98. The system of claim 97 wherein:

the step of determining whether the recovery client has successfully recovered the strong secret data further comprises determining whether the proof data proves that the recovery client has access to a nonce which confirms freshness of the proof data.

99. The system of claim 98 wherein:

the user'"'"'s private data includes a private key for use in a digital signature system;

the proof data includes digitally signed data which allegedly contains the nonce and allegedly has been digitally signed using the private key;

the step of determining whether the proof data proves that the recovery client has access to the private data includes verifying that the digitally signed data has been digitally signed using the private key; and

the step of determining whether the proof data proves that the recovery client has access to the nonce includes verifying that the digitally signed data contains the nonce or a value derived from the nonce.

100. The system of claim 96 wherein:

the verifier data is a one-way function of the strong secret data; and

the step of determining whether the recovery client has successfully recovered the strong secret data comprises determining whether the proof data proves that the recovery client can compute the verifier data.

101. The system of claim 100 wherein:

the step of determining whether the recovery client has successfully recovered the strong secret data further comprises determining whether the proof data proves that the, recovery client has access to a nonce which confirms freshness of the proof data.

102. The system of claim 101 wherein the step of determining whether the recovery client has successfully recovered the strong secret data comprises:

computing an expected proof data as a one-way function of the verifier data and the nonce; and

comparing the expected proof data with the proof data received from the recovery client.

103. A system for securely regenerating a user'"'"'s strong secret data from weak secret data for the user, the system comprising:

a recovery client, at least two secret holding servers coupled to the recovery client and at least two verification servers coupled to the recovery client, for executing the following method steps;

the recovery client receiving the user'"'"'s weak secret data;

each secret holding server and the recovery client computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server;

the recovery client computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers;

the recovery client determining proof data for proving to the verification servers that the strong secret data was successfully computed;

the recovery client transmitting the proof data to the verification servers, the proof data including a user-originated message to be digitally signed;

each verification server accessing verifier data, wherein the verifier data enables the verification server to verify that a device has successfully recovered the strong secret data;

responsive to the verifier data and the proof data received from the recovery client, each verification server determining whether the recovery client has successfully regenerated the strong secret data; and

responsive to a determination that the recovery client has successfully recovered the strong secret data, each verification server generating and transmitting to the recovery client a digital signature component based on the user-originated message; and

the recovery client computing a digital signature of the user-originated message as a function of the digital signature components.

104. A system for securely regenerating a user'"'"'s strong secret data from weak secret data for the user, the system comprising:

a recovery client and at least two secret holding servers coupled to the recovery client, for executing the following method steps;

the recovery client receiving the user'"'"'s weak secret data;

each secret holding server and the recovery client computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server;

the recovery client computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers;

the recovery client determining proof data for proving to at least two verification servers that the strong secret data was successfully computed;

the recovery client determining token possession proof data for proving presence of a user'"'"'s hardware token; and

the recovery client transmitting the token possession proof data to at least one server selected from a group consisting of the secret holding servers and the verification servers.

105. A system for securely regenerating a user'"'"'s strong secret data from weak secret data for the user, the system comprising:

a recovery client and at least two secret holding servers coupled to the recovery client, for executing the following method steps;

the recovery client receiving the user'"'"'s weak secret data;

each secret holding server and the recovery client computing secret components for each of at least two secret holding servers, wherein the secret component for each secret holding server is a function of the user'"'"'s weak secret data and of server secret data for the secret holding server;

the recovery client computing the user'"'"'s strong secret data, wherein the strong secret data is a function of the secret components for the secret holding servers;

the recovery client determining proof data for proving to at least two verification servers that the strong secret data was successfully computed, said determining proof data includes determining the proof data as a function of user data which the verification server can authenticate as originating from the user.

106. A system for enabling devices to securely regenerate a user'"'"'s strong secret data from weak secret data for the user, the system comprising:

a generating client and at least one secret holding server coupled to the generating client, for executing the following method steps;

the generating client determining the user'"'"'s weak secret data;

the generating client computing and transmitting server request data to the secret holding server, wherein the server request data is a function of the weak secret data and of an ephemeral client secret, and the server request data does not reveal information about the weak secret data without knowledge of the ephemeral client secret;

the secret holding server computing and transmitting server response data to the generating client, wherein the server response data is a function of the server secret data for the secret holding server and of the server request data, and the server response data does not reveal information about the server secret data without knowledge of the weak secret data and the ephemeral client secret;

the generating client computing a secret component for the secret holding server as a function of the server response data received from the secret holding server and of the ephemeral client secret, wherein the secret component is a function of the weak secret data and of the server secret data but is independent of the ephemeral client secret;

the generating client computing the user'"'"'s strong secret data as a function of the secret component; and

the generating client determining verifier data for at least one verification server, wherein the verifier data enables the verification server to verify that a device has successfully recovered the strong secret data but it is computationally infeasible for the verification server to determine the weak secret data based only on access, to its verifier data.

107. The system of claim 106 wherein:

the server secret data includes a random integer b;

the secret component is a value K=h(w^b), wherein

h is a function;

w=f(weak secret data), wherein f is a function which generates an element of a finite group G in which exponentiation is efficient but the discrete logarithm problem is computationally infeasible; and

the exponentiation w^b is computed in the group G;

the ephemeral client secret is a random integer a for which there exists a corresponding integer a′

such that x^aa′

=x for all x in group G;

the server request data is computed as the value M=w^a wherein the exponentiation is computed in the group G;

the server response data is computed as the value c=M^b wherein the exponentiation is computed in the group G; and

the secret component is computed as the value K=h(c^a′

) wherein the exponentiation is computed in the group G.

108. The system of claim 107 wherein the group G is selected from:

a multiplicative group of the set of integers modulo p, where p is a large prime suitable as a Diffie-Hellman modulus; and

a group of points on an elliptic curve over a finite field.

109. The system of claim 106 wherein the method steps further comprise:

the generating client encrypting private data for the user using the strong secret data as a cryptographic key in a symmetric cryptosystem;

wherein

the step of determining verifier data includes determining public data which corresponds to the user'"'"'s private data, wherein a first entity with access to the private data can prove said access to a second entity with access to the public data without disclosing the private data to the second entity.

110. The system of claim 106 wherein the step of determining verifier data comprises computing verifier data as a one-way function of the strong secret data.

111. A system for securely regenerating a user'"'"'s strong secret data from weak secret data for the user, the system comprising:

a recovery client and at least one secret holding server coupled to the recovery client, for executing the following method steps;

the recovery client receiving the user'"'"'s weak secret data;

the recovery client computing and transmitting server request data to the secret holding server, wherein the server request data is a function of the weak secret data and of an ephemeral client secret, and the server request data does not reveal information about the weak secret data without knowledge of the ephemeral client secret;

the secret holding server computing and transmitting server response data to the recovery client, wherein the server response data is a function of the server secret data for the secret holding server and of the server request data, and the server response data does not reveal information about the server secret data without knowledge of the weak secret data and the ephemeral client secret;

the recovery client computing a secret component for the secret holding server as a function of the server response data received from the secret holding server and of the ephemeral client secret, wherein the secret component is a function of the weak secret data and of the server secret data but is independent of the ephemeral client secret;

the recovery client computing the user'"'"'s strong secret data as a function of the secret component; and

the recovery client determining proof data for proving to at least one verification server that the strong secret data was successfully computed.

112. The system of claim 111 wherein:

the server secret data includes a random integer b;

the secret component is a value K=h(w^b), wherein

h is a function;

w=f(weak secret data), wherein f is a function which generates an element of a finite group G in which exponentiation is efficient but the discrete logarithm problem is computationally infeasible; and

the exponentiation w^b is computed in the group G;

the ephemeral client secret is a random integer a for which there exists a corresponding integer a′

such that x^aa′

=x for all x in group G;

the server request data is computed as the value M=w^a wherein the exponentiation is computed in the group G;

the server response data is computed as the value c=M^b wherein the exponentiation is computed in the group G; and

the secret component is computed as the value K=h(c^a′

) wherein the exponentiation is computed in the group G.

113. The system of claim 112 wherein the group G is selected from:

a multiplicative group of the set of integers modulo p, where p is a large prime suitable as a Diffie-Hellman modulus; and

a group of points on an elliptic curve over a finite field.

114. The system of claim 111 wherein the method steps further comprise:

the recovery client obtaining encrypted private data for the user, wherein a first entity with access to the private data can prove said access to a second entity with access to corresponding public data without disclosing the private data to the second entity; and

the recovery client decrypting the encrypted private data using the strong secret data as a cryptographic key in a symmetric cryptosystern;

wherein

the step of determining proof data comprises computing proof data based on the decrypted private data.

115. The system of claim 114 wherein the step of determining proof data comprises determining proof data as a function of a nonce which distinguishes the proof data from other instances of proof data provided for the user.

116. The system of claim 115 wherein:

the user'"'"'s private data includes a private key for use in a digital signature system; and

the step of determining proof data comprises digitally signing a message containing the nonce using the private key.

117. The system of claim 111 wherein the step of determining proof data comprises computing proof data as a one-way function of the strong secret data.

118. The system of claim 117 wherein:

the step of determining proof data comprises determining the proof data as a function of a nonce which distinguishes the proof data from other instances of proof data provided for the user.

119. The system of claim 118 wherein the step of determining proof data comprises:

computing verifier data as a one-way function of the strong secret data; and

computing the proof data as a one-way function of the verifier data and of the nonce.

120. The system of claim 111 wherein the method steps further comprise:

the recovery client determining token possession proof data for proving presence of a user'"'"'s hardware token; and

the recovery client transmitting the token possession proof data to at least one server selected from a group consisting of the secret holding servers and the verification servers.