Privacy-preserving distributed computing

1 . A client device, comprising:

an interface configured to communicate with a plurality of servers; and

at least one hardware processor, individually or in combination, configured to:

encode a first dataset using an encoding function to generate a first set of encoded data portions;

encode a second dataset using the encoding function or a different encoding function to generate a second set of encoded data portions;

encrypt the first and second sets of encoded data portions using a first key according to an approximate Fully Homomorphic Encryption (FHE) scheme to generate first and second sets of encrypted encoded data portions;

send, via the interface, the first and second sets of encrypted encoded data portions to the plurality of servers;

receive, via the interface, a plurality of encrypted encoded results from at least a subset of servers of the plurality of servers, wherein each encrypted encoded result of the plurality of encrypted encoded results, received from a respective server, is based on at least one encrypted encoded data portion from each of the first set of encrypted encoded data portions and the second set of encrypted encoded data portions;

decrypt the received plurality of encrypted encoded results using a secret key according to the approximate FHE scheme to derive a plurality of decrypted encoded results; and

decode the plurality of decrypted encoded results using an approximate decoding function.

2 . The client device of claim 1 , wherein the first dataset and the second dataset represent respective first and second matrices, and wherein the at least one hardware processor, individually or in combination, is further configured to:

divide the first dataset into a first set of smaller datasets representing smaller matrices within the first matrix; and

divide the second dataset into a second set of smaller datasets representing smaller matrices within the second matrix.

3 . The client device of claim 1 , wherein the at least one hardware processor, individually or in combination, is further configured to:

divide the first dataset into a first number of smaller datasets; and

divide the second dataset into a second number of smaller datasets, wherein the first number of smaller datasets does not equal the second number of smaller datasets.

4 . The client device of claim 1 , wherein the at least one hardware processor, individually or in combination, is further configured to send, to each server of the plurality of servers, a first encrypted encoded data portion from the first set of encrypted encoded data portions and a second encrypted encoded data portion from the second set of encrypted encoded data portions to multiply the first and second encrypted encoded data portions with each other.

5 . The client device of claim 1 , wherein the at least one hardware processor, individually or in combination, is further configured to determine a total number of encoded data portions to be derived from encoding one of the first dataset or the second dataset based at least in part on a degree of a function to be evaluated by each server of the plurality of servers to calculate the encrypted encoded result.

6 . The client device of claim 1 , wherein the at least one hardware processor, individually or in combination, is further configured to:

divide the first dataset into a first set of smaller datasets;

divide the second dataset into a second set of smaller datasets;

encode the first set of smaller datasets to generate the first set of encoded data portions; and

encode the second set of smaller datasets to generate the second set of encoded data portions.

7 . A method for distributed computation, the method comprising:

encoding at least two datasets using one or more encoding functions to generate encoded data portions;

encrypting the encoded data portions using a first key according to an approximate Fully Homomorphic Encryption (FHE) scheme to generate encrypted encoded data portions;

sending the encrypted encoded data portions to a plurality of servers;

receiving a plurality of encrypted encoded results from at least a subset of servers from the plurality of servers, wherein each server of the at least a subset of servers calculates a respective encrypted encoded result by evaluating a multivariate function using at least two encrypted encoded data portions received by the server;

decrypting the received plurality of encrypted encoded results using a secret key according to the approximate FHE scheme to derive a plurality of decrypted encoded results; and

decoding the plurality of decrypted encoded results using an approximate decoding function.

8 . The method of claim 7 , wherein the at least two datasets represent respective matrices, and wherein the method further comprises dividing each of the at least two datasets into a plurality of smaller datasets that each represent a smaller matrix within one of the respective matrices.

9 . The method of claim 7 , further comprising:

dividing a first dataset into a first set of smaller datasets; and

dividing a second dataset into a second set of smaller datasets, wherein the number of smaller datasets in the first set of smaller datasets does not equal the number of smaller datasets in the second set of smaller datasets.

10 . The method of claim 7 , wherein each server of the plurality of servers evaluates the multivariate function as a bilinear function using a first encrypted encoded data portion from a first set of encrypted encoded data portions as a first input to the bilinear function and using a second encrypted encoded data portion from a second set of encrypted encoded data portions as a second input to the bilinear function.

11 . The method of claim 7 , wherein each server of the plurality of servers performs at least one matrix or vector arithmetic operation using the at least two encrypted encoded data portions received from the client device.

12 . The method of claim 7 , further comprising sending, to each server of the plurality of servers, a first encrypted encoded data portion from a first set of encrypted encoded data portions and a second encrypted encoded data portion from a second set of encrypted encoded data portions to multiply the first and second encrypted encoded data portions with each other.

13 . The method of claim 7 , further comprising determining a total number of encoded data portions to be derived from encoding one dataset of the at least two datasets based at least in part on a degree of the multivariate function to be evaluated by each server of the plurality of servers to calculate an encrypted encoded result of the plurality of encrypted encoded results.

14 . The method of claim 7 , further comprising:

dividing a dataset of the at least two datasets into a number of smaller datasets; and

setting a number of servers to use for the plurality of servers based at least in part on the number of smaller datasets.

15 . A server, comprising:

an interface configured to communicate with a client device; and

at least one hardware processor, individually or in combination, configured to:

receive a first encrypted data portion and a second encrypted data portion from the client device, wherein the first encrypted data portion is from a first set of encrypted data portions and the second encrypted data portion is from a second set of encrypted data portions, the first and second sets of encrypted data portions having been encrypted using an approximate Fully Homomorphic Encryption (FHE) scheme;

calculate an encrypted result by at least in part evaluating a multivariate function using the first encrypted data portion as a first input to the multivariate function and using the second encrypted data portion as a second input to the multivariate function; and

send the encrypted result to the client device.

16 . The server of claim 15 , wherein the at least one hardware processor, individually or in combination, is further configured to evaluate the multivariate function by performing at least one matrix or vector arithmetic operation using the first encrypted data portion and the second encrypted data portion.

17 . A system, comprising:

a plurality of servers; and

a client device including means for:

encoding a first dataset using an encoding function to generate a first set of encoded data portions;

encoding a second dataset using the encoding function or a different encoding function to generate a second set of encoded data portions;

encrypting the first and second sets of encoded data portions using a first key according to an approximate Fully Homomorphic Encryption (FHE) scheme to generate first and second sets of encrypted encoded data portions; and

sending the first and second sets of encrypted encoded data portions to the plurality of servers; and

wherein each server of the plurality of servers is configured to:

receive at least one encrypted encoded data portion from the client device;

evaluate a function using the received at least one encrypted encoded data portion to calculate an encrypted encoded result, wherein the at least one encrypted encoded data portion received by the server is from at least one of the first and second sets of encrypted encoded data portions; and

send the encrypted encoded result to the client device; and

wherein the client device further includes means for:

receiving a plurality of encrypted encoded results from at least a subset of servers of the plurality of servers;

decrypting the received plurality of encrypted encoded results using a secret key according to the approximate FHE scheme to derive a plurality of decrypted encoded results; and

decoding the plurality of decrypted encoded results using an approximate decoding function.

18 . The system of claim 17 , wherein each server of the plurality of servers is further configured to perform at least one matrix or vector arithmetic operation using the received at least one encrypted encoded data portion.

19 . The system of claim 17 , wherein the client device further includes means for determining a total number of encoded data portions to be derived from encoding at least one of the first dataset and the second dataset based at least in part on a degree of the function to be evaluated by each server of the plurality of servers to calculate the encrypted encoded result.

20 . The system of claim 17 , wherein the client device further includes means for:

dividing the first dataset into a first set of smaller datasets;

dividing the second dataset into a second set of smaller datasets;

encoding the first set of smaller datasets to generate the first set of encoded data portions; and

encoding the second set of smaller datasets to generate the second set of encoded data portions.