System and method for generating a server-assisted strong password from a weak secret

1. A method for generating a high entropy password using a low entropy password and low-entropy login data comprising:

supplying the low entropy password to a system comprising:

a generating computer client and/or a recovery computer client, and

at least n computer servers;

submitting request data derived, at least in part, from the user's low entropy password, where the request data includes authentication data; where a user enters the low entropy password into the generating computer client and/or recovery computer client;

engaging in a distributed protocol with at least t computer servers to generate high-entropy values based on stored cryptographic information and a set of authentication information stored on the at least n computer servers which is checked against the authentication data provided by the user and/or the generating computer client and/or a recovery computer client; and

generating the high entropy password where at least a threshold t≦n of the at least n computer servers contribute to generation of the high-entropy password, where a corrupted computer server cannot generate any passwords after a single setup as long as the threshold t≦n is not reached.

2. The method of claim 1 , further comprising permitting the user to provide a plurality of auxiliary low entropy passwords that permit deriving a plurality of high entropy passwords for a plurality of different services and where the at least t computer servers do not learn the plurality of auxiliary passwords.

3. The method of claim 2 , where none of the at least n computer servers learn which high entropy password was generated in a given password generating session.

4. The method of claim 3 , further comprising permitting the at least n computer servers to stop contributing to high entropy password generation.

5. The method of claim 4 , where the system further comprises a recovery computer client that contributes to password generation, and where the recovery computer client authenticates itself towards the at least n computer servers to avoid flooding the at least n computer servers with false login attempts.

6. The method of claim 1 , where the generating computer client and/or recovery computer client communicates with the at least n computer servers to generate a RSA-key pair (d, (N, e)), where d, N and e represent integers and where the relationship between d, N and e is given by equation (1):

( d ) e≡ 1 mod φ( N )  (1),

splitting up the integer d into a plurality of key-shares;

assigning a portion of each key-share d i to the one or more computer servers as seen in the Equation (2); where n is an integer that represents a number of computer servers;

( d 1 d 2 d 3 . . . d n ) e≡ 1 mod φ( N )  (2),

where d i is a share of the i th computer server;

sending initial data that comprises derived data from the low entropy password PW, the RSA-key pair, a salt k, and an optional “id” from the generating computer client and/or recovery computer client to the one or more computer servers; where initial data is represented by Equation (3)

id,h 1 =H ( k,PW,S 1 ) d 1 ,N   (3), and

computing a bit string (N, e, d i , id) which constitutes the computer server secrets; where the bit string is computed by the at least n computer servers, or a combination of the none or more of the at least n computer servers and the generating computer client.

7. The method of claim 6 , where n>2 or where n=t−1, and where the user takes a RSA-key share.

8. The method of claim 6 , where n=t is greater than or equal to 2 when a user does not take a RSA-key pair share.

9. The method of claim 6 , where n≧1 or where n=t−1, and where the user takes a RSA-key share.

10. The method of claim 9 , where a first computer server sends to the generating computer client and/or recovery computer client a first signature s 1 ←s o d 1 mod N, where d 1 is a share of the first computer server; where s o =H(m)r e mod N is a blinded signature or a value obtained from an oblivious pseudorandom function.

11. The method of claim 10 , where the n th computer server sends to the generating computer client and/or recovery computer client an n th signature s n , where s n =s n-1 r −1 mod N is a blinded signature or a signature obtained from an oblivious pseudorandom function and where r is coprime with N.

12. A system comprising:

a generating computer client and/or recovery computer client in operative communication with a user; where the user provides a password to the generating computer client and/or recovery computer client; and

a computer server; where the computer server is in operative communication with the generating computer client and/or recovery computer client; and

where the generating computer client and/or recovery computer client:

generates a RSA-key pair (d, (N, e)), where d, N and e represent integers and where the relationship between d, N and e is given by equation (1):

( d ) e≡ 1 mod φ( N )  (1),

splits up the integer d into a plurality of key-shares;

assigns a portion of each key-pair share d i to the one or more computer servers as seen in the Equation (2); where n is an integer that represents a number of computer servers;

( d 1 d 2 d 3 . . . d n ) e≡ 1 mod φ( N )  (2),

where d i is a share of the i th computer server; where n is an integer that represents the number of computer servers;

sends initial data that is derived from the low entropy password PW, the RSA-key pair, a salt k, and an optional “id” from the generating computer client and/or recovery computer client to the one or more computer servers; where initial data is represented by Equation (3)

id,h 1 =H ( k,PW,S 1 ) d 1 ,N   (3), and

computes a bit string (N, e, d i , id) which provides the high entropy password; where the bit string is computed by the at least n computer servers, or a combination of the one or more of the at least n computer servers and the generating computer client.

13. The system of claim 12 , where n≧1 if a user takes a RSA-key pair share d i for himself.

14. The system of claim 13 , where a first computer server sends to the generating computer client and/or the recovery computer client a first signature s 1 ←s o d 1 mod N, where d 1 is a share of the first computer server; where s o is a blinded signature or a signature obtained from an oblivious pseudorandom function.

15. The system of claim 14 , where the n th computer server sends to the generating computer client and/or recovery computer client an n th signature s n r −1 mod N, where s n is a blinded signature or a signature obtained from an oblivious pseudorandom function and where r is coprime with N and where s n r −1 mod N is the high entropy password that can be verified on inspection.

16. The system of claim 12 , where n is greater than or equal to 2 when a user does not take a RSA-key pair share.