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

A system for decrypting encrypted secrets using a first secret, comprising:

• a client and a group of one or more servers, each server of the group comprising a respective server secret and a blind function evaluator for participating in a blind function evaluation protocol with the client, the blind function evaluation protocol resulting in the generation of a strong secret component revealed to the client but not to any of the other servers of the group, the blind function evaluator evaluating a function taking as input the respective server secret and client information derived from the first secret, and generating as output the respective strong secret component, the client generating the strong secret from the strong secret components generated for the group of servers and using the strong secret to decrypt an encrypted secret, wherein the blind function evaluation protocol is characterized in that the client cannot determine any of the respective server secrets and in that each server cannot determine any other respective strong secret component or the strong secret, wherein the blind function evaluation protocol is selected from a set of blind function evaluation protocols that excludes any protocol involving:
• the client computing server request data by exponentiating the client information to a random first integer a, wherein the client information is an element w of a finite group G in which exponentiation is efficient but the discrete logarithm problem is computationally infeasible;
• the server computing server response data from the server request data and the server secret, wherein the server response data comprises a value c in the group G;
• and
• the client computing a strong secret component by exponentiating the value c to a second integer a′, wherein the first and second integers a and a′ are such that zaa′=x for all x in the group G.

A system for decrypting encrypted secrets using a first secret, comprising:

• a client in communication with a group of one or more servers, each server of the group comprising a respective server secret and a blind function evaluator for participating in a blind function evaluation protocol with the client, the blind function evaluation protocol resulting in the generation of a strong secret component revealed to the client but not the servers, the evaluator evaluating a function taking as input the respective server secret and client information derived from the first secret, and generating as output a respective strong secret component, the client generating the strong secret from the strong secret components generated for the group of servers, wherein the blind function evaluation protocol is characterized in that the client cannot determine any of the respective server secrets and in that each server cannot determine either another respective strong secret component or the strong secret, wherein the blind function evaluation protocol is selected from a set of blind function evaluation protocols that excludes any protocol involving:
• the client computing server request data by exponentiating the client information to a random first integer a, wherein the client information is an element w of a finite group G in which exponentiation is efficient but the discrete logarithm problem is computationally infeasible;
• the server computing server response data from the server request data and the server secret, wherein the server response data comprises a value c in the group G;
• and
• the client computing a strong secret component by exponentiating the value c to a second integer a′, wherein the first and second integers a and a′ are such that xaa′=x for all x in the group C,
• the client comprising:
• a receiver for receiving encrypted secrets;
• a decryption function for decrypting the encrypted secrets with a key derived from the strong secret.