Secure probabilistic analytics using an encrypted analytics matrix
Provided are methods and systems for performing a secure probabilistic analytic using an encrypted analytics matrix. An example method includes acquiring, by a client, an analytic, analytic parameters associated with the analytic, and a homomorphic encryption scheme including a public key for encryption and a private key for decryption. The method further includes generating, using the encryption scheme, an analytic matrix based on the analytic and analytic parameters, and sending the analytic matrix and the encryption scheme to at least one server. The method includes generating, by the server and based on the encryption scheme, set of terms from a data set, evaluating the analytic matrix over the set of terms to obtain an encrypted result, and estimating a probabilistic error of the encrypted result. The method further includes sending, by the server, the encrypted result and the probabilistic error to the client where the encrypted result is decrypted.
1. A method for performing a secure probabilistic analysis, the method comprising:
receiving, by at least one server from a client, at least one analytic matrix, a term generation function, and a keyed hash function, the at least one analytic matrix being generated from an analytic and an analytic parameter set and encoded using a homomorphic encryption scheme, the at least one analytic matrix having dimensions comprising a number of rows that are equal to or greater than a number of distinct elements in a set of term components, wherein the homomorphic encryption scheme includes a public key for encryption and a private key for decryption;
extracting, by the at least one server, the set of term components from a data set using the term generation function, the keyed hashed function, and the analytic;
evaluating, by the at least one server, the at least one analytic matrix over the encrypted data set to obtain at least one encrypted result;
estimating, by the at least one server, a probabilistic error bound of the at least one encrypted result; and
sending, by the at least one server, the at least one encrypted result and the probabilistic error bound to the client, wherein the client is configured to decrypt the at least one encrypted result using the homomorphic encryption scheme.
2. The method of claim 1 , wherein the homomorphic encryption scheme includes a partially homomorphic encryption scheme.
3. The method of claim 2 , wherein the partially homomorphic encryption scheme includes at least one of a Rivest, Shamir and Adleman cryptosystem, an Elgamal cryptosystem, a Benaloh cryptosystem, a Goldwasser-Micali cryptosystem, and a Pallier cryptosystem.
4. The method of claim 1 , wherein the homomorphic encryption scheme includes a fully homomorphic encryption scheme.
5. The method of claim 1 , wherein the at least one analytic matrix is generated based on an analytic and at least one parameter associated with the analytic.
6. The method of claim 5 , wherein the generation of the at least one analytic matrix includes:
extracting, using the term generation function, a set of term elements from the analytic and at least one analytic parameter;
generating, using the keyed hash function, a set of hashes from the set of term elements;
partitioning elements of the set of hashes to generate a set of vectors, wherein each of the vectors is of a pre-defined dimension;
determining whether for at least one matrix element associated with row j and column m of the at least one analytic matrix, there is a vector C from the set of vectors, wherein C[j]=m;
if the result of the determination is positive, assigning the at least one matrix element a non-zero value; and
if the result of the determination is negative, assigning the at least one matrix element a zero value.
7. The method of claim 6 , wherein the number of rows of the at least one analytic matrix is equal or greater than the number of distinct elements in the set of term elements and length of the elements in the set of hashes is divisible by a number of columns of the at least one analytical matrix.
8. The method of claim 6 , wherein the non-zero value is an encrypted value of a non-zero bitmask of a term element of the set of term elements, wherein a hash of the term element is used to generate the vector C, the encrypted value being obtained using the homomorphic encryption scheme.
9. The method of claim 1 , wherein estimating the probabilistic error is based on a hash collision rate of the keyed hash function over the data set.
10. The method of claim 1 , wherein the data set is one of a plaintext form, deterministically encrypted or semantically encrypted.
11. A system for performing a secure probabilistic analysis using homomorphic encryption, the system comprising:
at least one processor; and
a memory communicatively coupled with the at least one processor, the memory storing instructions, which when executed by the at least one processor causes the system to:
receive, from a client, at least one analytic matrix, a term generation function, and a keyed hash function, the at least one analytic matrix being generated from an analytic and an analytic parameter set and encoded using a homomorphic encryption scheme, the at least one analytic matrix having dimensions comprising a number of rows that are equal to or greater than a number of distinct elements in a set of term components, wherein the homomorphic encryption scheme includes a public key for encryption and a private key for decryption;
extract, by the at least one server, the set of term components from a data set using the term generation function, the keyed hashed function, and the analytic;
evaluate the at least one analytic matrix over the set of term components to obtain at least one encrypted result;
estimate a probabilistic error bound of the at least one encrypted result; and
send the at least one encrypted result and the probabilistic error bound to the client, wherein the client is configured to decrypt the at least one encrypted result using the homomorphic encryption scheme.
12. The system of claim 11 , wherein the homomorphic encryption scheme includes a partially homomorphic encryption scheme.
13. The system of claim 12 , wherein the partially homomorphic encryption scheme includes at least one of a Rivest, Shamir and Adleman cryptosystem, an Elgamal cryptosystem, a Benaloh cryptosystem, a Goldwasser-Micali cryptosystem, and a Pallier cryptosystem.
14. The system of claim 11 , wherein the homomorphic encryption scheme includes a fully homomorphic encryption scheme.
15. The system of claim 11 , wherein the at least one analytic matrix is generated based on an analytic and at least one parameter associated with the analytic.
16. The system of claim 15 , wherein the generation of the at least one analytic matrix includes:
extracting, using the term generation function, a set of term elements from the analytic and at least one analytic parameter;
generating, using the keyed hash function, a set of hashes from the set of term elements;
partitioning elements of the set of hashes to generate a set of vectors, wherein each of the vectors is of a pre-defined dimension;
determining whether for at least one matrix element associated with row j and column m of the at least one analytic matrix, there is a vector C from the set of vectors, wherein C[j]=m;
if the result of the determination is positive, assigning the at least one matrix element a non-zero value; and
if the result of determination is negative, assigning the at least one matrix element a zero.
17. The system of claim 16 , wherein the number of rows of the at least one analytic matrix is equal or greater than the number of distinct elements in the set of term elements and length of the elements in the set of hashes is divisible by a number of columns of the at least one analytical matrix.
18. The system of claim 16 , wherein the non-zero value is an encrypted value of a non-zero bitmask of a term element of the set of term elements, wherein a hash of the term element is used to generate the vector C, the encrypted value being obtained using the homomorphic encryption scheme.
19. The system of claim 13 , wherein estimating the probabilistic error is based on a hash collision rate of the keyed hash function over the data set.
20. A non-transitory computer-readable storage medium having embodied thereon instructions, which when executed by at least one processor, perform steps of a method, the method comprising:
receiving, by at least one server from a client, at least one analytic matrix, a term generation function, and a keyed hash function, the at least one analytic matrix being generated from an analytic and an analytic parameter set and encoded using a homomorphic encryption scheme, the at least one analytic matrix having dimensions comprising a number of rows that are equal to or greater than a number of distinct elements in a set of term components, wherein the homomorphic encryption scheme includes a public key for encryption and a private key for decryption;
extracting, by the at least one server, a set of term components from a data set using the term generation function and the keyed hashed function;
evaluating, by the at least one server, the at least one analytic matrix over the set of term components to obtain at least one encrypted result;
estimating, by the at least one server, a probabilistic error bound of the at least one encrypted result; and
sending, by the at least one server, the at least one encrypted result and the probabilistic error bound to the client, wherein the client is configured to decrypt the at least one encrypted result using the homomorphic encryption scheme.