System and method for generating a server-assisted strong password from a weak secret
Disclosed herein is 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 client and/or a recovery client; and at least n servers; submitting request data derived, at least in part, from the user's low entropy password, where the request data includes authentication data; engaging in a distributed protocol with at least t servers to generate high-entropy values based on stored cryptographic information and a set of authentication information stored on the at least n servers which is checked against the authentication data provided by the user and/or the generating client and/or a recovery client; and generating the high entropy password.
1. A system for retrieving a high entropy password comprising:
a generating and/or a recovery computer client; and one or more computer servers; where the generating and/or recovery computer client:
chooses a threshold t≤n, where t and n represent a number of computer servers;
transmits (pk t ; {(pk i ,sk i )} 0<i≤n )←TKeyGen(1 λ ,t,n) to the one or more computer servers; where pk t is a public key, pk i is a private key and sk i is a secret key;
distributes pk t , pk i , and sk i arbitrarily among the one or more computer servers; where each server receives a share of pk t , pk i , and sk i ,
sets c=G(m), where c is a ciphertext, G is a hash function and m is a message;
blinds ciphertext c where by setting c′=TEnc(pk t , 1);
randomizes c″←c⊕c′ in a homomorphic form;
decrypts c″ by applying a decryption share (d i ,π i )←PDec(sk i , c″); where c′ is the blinding ciphertext and c″ is the blinded ciphertext;
sends (d i ,π i ) from the one or more computer servers to the generating and/or recovery computer client;
where TKeyGen is an algorithm that outputs the public (pk t ) and the private (pk i ) key for each participant and the secret key (sk i ) of a scheme, where λ is a security parameter, n∈N a number of participants, t≤n∈N is a threshold given by:
( pk t ,{( pk i ,sk i )} 0<i≤n )← T KeyGen(1 λ ,t,n );
where algorithm TEnc gets as input the public key pk t , a message m∈M to encrypt, where m and M are both messages; and outputs a cipher-text c:
c←T Enc( pk t ,m ),
where algorithm PDec outputs a decryption share d i , or a special symbol
⊥∉ M if
decryption failed, a proof π i that decryption was performed correctly with respect to a partial secret key sk i and the cipher-text c,
( d i ,π i )← P Dec( sk i ,c );
where algorithm TDec outputs a high-entropy value m on input of t correctly calculated decryption shares, m←TDec({d i } 0<i≤t ), wherein the high entropy password is based on the high entropy value.
2. The system of claim 1 , where any one of the choosing, transmitting, setting, blinding, randomizing and/or decrypting may be performed by any one of the one or more computer servers in conjunction with the generating and/or the recovery computer client.
3. The system of claim 1 , where the generating computer client and/or the recovery computer client and/or the one or more computer servers further sets m=(Uid i , X) where X is a uniform resource locator for a website that uses the high entropy password and Uid i is a login password and where m is transmitted from the generating and/or recovery computer client to the one or more computer servers.