Computer-implemented system and method for multi-party data function computing using discriminative dimensionality-reducing mappings

1. A computer-implemented system for multi-party data function computing using discriminative dimensionality-reducing mappings, comprising:

a server comprising a processor configured to execute computer code, comprising:

a maintenance module configured to maintain one or more vectors, each of the vectors comprising one or more elements drawn from a finite ordered set;

a function module configured to obtain by the server one or more parameters for a discriminative dimensionality-reducing mapping function and for an embedded vector processing function;

a mapping module configured to create by the server embedded server vectors by applying the mapping function to the server vectors, wherein each of the embedded server vectors has a lower dimensionality than the server vector on which that embedded server vector is based;

a receipt module configured to receive from a client a homomorphically encrypted embedded query vector comprising a homomorphically encrypted result of an application of the mapping function to a query vector comprising one or more elements drawn from the finite ordered set, the embedded query vector having a lower dimensionality than the query vector;

a computation module configured to, for each of the embedded server vectors, compute by the server a homomorphic encryption of a result of an application of the processing function to the homomorphically encrypted embedded query vector and that embedded server vector;

a result module configured to provide by the server the encrypted results to the client, wherein each of the server vectors is associated with an index and the server provides to the client with each of the encrypted results the index of the server vector on which the embedded server vector used to obtain that result is based; and

a transfer module configured to provide to the client by the server through a performance of an oblivious transfer protocol one or more of the server vectors identified of interest to the client based on the client's processing of the encrypted results; and

the client comprising another processor configured to execute code, comprising:

a processing module configured to process the encrypted results received from the server by the client, comprising:

a decryption module configured to decrypt the encrypted results;

an identification module configured to identify those of the results informative of a relationship between the query vector and one of the server vectors; and

a construction module configured to, based on the informative results, construct a set of the indices associated with the server vectors of interest to the client; and

a retrieval module configured to retrieve the server vectors corresponding to the set of indices using the oblivious transfer protocol, wherein the retrieved server vectors are the server vectors of interest.

2. A system according to claim 1 , wherein the server vectors of interest are nearest neighbors of the query vector.

3. A system according to claim 1 , wherein the server vectors of interest comprise at least as many unique elements as the query vector.

4. A system according to claim 1 , wherein one of the results is informative if the application of the processing function to the embedded query vector and the embedded server vector used to obtain the result obeys a predefined rule, wherein the predefined rule relates an aggregate function of a pair comprising the embedded query vector and the embedded server vector to a function of another pair comprising the query vector and the server vector on which that embedded server vector in the pair is based.

5. A system according to claim 4 , wherein the processing function and the aggregate function are distance functions and the rule specifies a distance between nearest neighbors query vector and one of the server vectors.

6. A system according to claim 1 , further comprising:

a histogram module comprised in the server and configured to, for each of the server vectors, create a histogram representing that server vector and create one of the embedded server vectors based on the histogram, wherein each element of the embedded server vector is associated with one of the bins of the histogram, wherein the elements of the embedded server vector have a value of 0 if the associated bins are populated and the elements have a random value in an interval [a, b] if the corresponding bins are unpopulated, wherein a and b are chosen so that a mean value 0.5 (a+b) is away from 0.

7. A system according to claim 1 , further comprising:

a histogram module comprised in the client and configured to create a histogram representing the query vector and create the embedded query vector based on the histogram, wherein each element of the embedded query vector associated with one of the bins of the histogram, wherein the elements of the embedded query vector have a value of 1 if the associated bins are populated and the elements have a value of 0 if the bins are unpopulated.

8. A system according to claim 1 , further comprising:

an additional vector module comprised in the client and configured to maintaining by the client additional vectors and creating additional embedded vectors by applying the mapping function to the additional vectors;

an additional mapping module comprised in the client and configured to, for each of the embedded vectors, apply by the client the processing function to the embedded query vector and that additional embedded vector;

a combining module comprised in the client and configured to combine the result of the processing function application with the result of decrypting the computations performed by the server; and

an identification module comprised in the client and configured to identify any of the additional vectors that are nearest neighbors of the query vector based on the combined results.

9. A system according to claim 1 , wherein the encryption is an additively homomorphic encryption, further comprising:

a sum module comprised in the server and configured to receive by the server an encrypted sum of squares of all elements of the embedded query vector and using the sum in an encrypted-domain computation of polynomial functions used to compute the results of the processing function application.

10. A computer-implemented method for multi-party data function computing using discriminative dimensionality-reducing mappings, comprising:

maintaining by a server one or more vectors, each of the vectors comprising one or more elements drawn from a finite ordered set;

obtaining by the server one or more parameters for a discriminative dimensionality-reducing mapping function and for an embedded vector processing function;

creating by the server embedded server vectors by applying the mapping function to the server vectors, wherein each of the embedded server vectors has a lower dimensionality than the server vector on which that embedded server vector is based;

receiving from a client a homomorphically encrypted embedded query vector comprising a homomorphically encrypted result of an application of the mapping function to a query vector comprising one or more elements drawn from the finite ordered set, the embedded query vector having a lower dimensionality than the query vector;

for each of the embedded server vectors, computing by the server a homomorphic encryption of a result of an application of the processing function to the homomorphically encrypted embedded query vector and that embedded server vector;

providing by the server the encrypted results to the client, wherein each of the server vectors is associated with an index and the server provides to the client with each of the encrypted results the index of the server vector on which the embedded server vector used to obtain that result is based;

providing to the client by the server through a performance of an oblivious transfer protocol one or more of the server vectors identified of interest to the client based on the client's processing of the encrypted results; and

processing the encrypted results received from the server by the client, comprising:

decrypting the encrypted results;

identifying those of the results informative of a relationship between the query vector and one of the server vectors; and

based on the informative results, constructing a set of the indices associated with the server vectors of interest to the client; and

retrieving the server vectors corresponding to the set of indices using the oblivious transfer protocol, wherein the retrieved server vectors are the server vectors of interest.

11. A method according to claim 10 , wherein the server vectors of interest are nearest neighbors of the query vector.

12. A method according to claim 10 , wherein the server vectors of interest comprise at least as many unique elements as the query vector.

13. A method according to claim 10 , wherein one of the results is informative if the application of the processing function to the embedded query vector and the embedded server vector used to obtain the result obeys a predefined rule, wherein the predefined rule relates an aggregate function of a pair comprising the embedded query vector and the embedded server vector to a function of another pair comprising the query vector and the server vector on which that embedded server vector in the pair is based.

14. A method according to claim 13 , wherein the processing function and the aggregate function are distance functions and the rule specifies a distance between nearest neighbors query vector and one of the server vectors.

15. A method according to claim 10 , further comprising:

for each of the server vectors, creating by the server a histogram representing that server vector and creating one of the embedded server vectors based on the histogram, wherein each element of the embedded server vector is associated with one of the bins of the histogram, wherein the elements of the embedded server vector have a value of 0 if the associated bins are populated and the elements have a random value in an interval [a, b] if the corresponding bins are unpopulated, wherein a and b are chosen so that a mean value 0.5 (a+b) is away from 0.

16. A method according to claim 10 , further comprising:

creating by the client a histogram representing the query vector and creating the embedded query vector based on the histogram, wherein each element of the embedded query vector associated with one of the bins of the histogram, wherein the elements of the embedded query vector have a value of 1 if the associated bins are populated and the elements have a value of 0 if the bins are unpopulated.

17. A method according to claim 10 , further comprising:

maintaining by the client additional vectors and creating additional embedded vectors by applying the mapping function to the additional vectors;

for each of the embedded vectors, applying by the client the processing function to the embedded query vector and that additional embedded vector;

combining the result of the processing function application with the result of decrypting the computations performed by the server; and

identifying any of the additional vectors that are nearest neighbors of the query vector based on the combined results.

18. A method according to claim 10 , wherein the encryption is an additively homomorphic encryption, further comprising:

receiving by the server an encrypted sum of squares of all elements of the embedded query vector and using the sum in an encrypted-domain computation of polynomial functions used to compute the results of the processing function application.