Homomorphic encrypted one-hot maps using intermediate chinese remainder theorem (CRT) maps
A method, apparatus and computer program product for privacy-preserving homomorphic inferencing using one-hot data representations. In this approach, a client interacting with a cloud-based server submits one-hot maps of a Chinese Remainder Theorem (CRT)-based representation of an data element, and the server expands these maps in an online phase to obtain a full one-hot map for the element. After the server obtains the full one-hot map, it performs an operation, e.g., a comparison operation associated with inferencing on a decision tree, on the one-hot map under homomorphic encryption, and in response generates a result. The result is provided back to the client.
1. A method implemented in part on at least one processor for secure computations under Homomorphic Encryption (HE), comprising:
receiving an encrypted data point that encrypts one or more elements, wherein at least one element is associated with a plaintext number, the plaintext number being represented in the encrypted data point as a set of one-hot maps, each of the set of one-hot maps corresponding to a coprime factor computed for the plaintext number using a Chinese Remainder Theorem (CRT) encoding;
under homomorphic encryption, generating a one-hot map representation of the plaintext number using the set of one-hot maps;
under homomorphic encryption, performing an operation on the one-hot representation and generating a result; and
providing the result as a response to the encrypted data point.
2. The method as described in claim 1 wherein generating the one-hot map representation comprises:
for a given one-hot map of the set of one-hot maps, duplicating the given one-hot map a number of times to generate a vector, the number of times derived by dividing a result of multiplying the coprime factors by the coprime factor for the given one-hot map; and
multiplying the vectors.
3. The method as described in claim 1 wherein the plaintext number is a number without coprime factors and that has been padded with one or more zeros.
4. The method as described in claim 1 wherein the operation is a comparison operation associated with evaluation of a decision tree.
5. The method as described in claim 1 wherein the homomorphic encryption is based on a Cheon-Kim-Kim-Song (CKKS) scheme.
6. The method as described in claim 1 wherein the one or more elements are arranged according to a tile tensor-based packing scheme.
7. The method as described in claim 1 wherein the CRT encoding is hierarchical, and wherein generating the one-hot map representation is recursively repeated at each hierarchy.
8. An apparatus, comprising:
a processor;
computer memory holding computer program instructions executed by the processor to provide secure computations under Homomorphic Encryption (HE), the computer program instructions comprising program code configured to:
receive an encrypted data point that encrypts one or more elements, wherein at least one element is associated with a plaintext number, the plaintext number being represented in the encrypted data point as a set of one-hot maps, each of the set of one-hot maps corresponding to a coprime factor computed for the plaintext number using a Chinese Remainder Theorem (CRT) encoding;
under homomorphic encryption, generate a one-hot map representation of the plaintext number using the set of one-hot maps;
under homomorphic encryption, perform an operation on the one-hot representation and generating a result; and
provide the result as a response to the encrypted data point.
9. The apparatus as described in claim 8 wherein the program code configured to generate the one-hot map representation comprises program code configured to:
for a given one-hot map of the set of one-hot maps, duplicate the given one-hot map a number of times to generate a vector, the number of times derived by dividing a result of multiplying the coprime factors by the coprime factor for the given one-hot map; and
multiply the vectors.
10. The apparatus as described in claim 8 wherein the plaintext number is a number without coprime factors and that has been padded with one or more zeros.
11. The apparatus as described in claim 8 wherein the operation is a comparison operation associated with evaluation of a decision tree.
12. The apparatus as described in claim 8 wherein the homomorphic encryption is based on a Cheon-Kim-Kim-Song (CKKS) scheme.
13. The apparatus as described in claim 8 wherein the one or more elements are arranged according to a tile tensor-based packing scheme.
14. The apparatus as described in claim 8 wherein the CRT encoding is hierarchical, and the computer program code configured to generate the one-hot map representation is recursively repeated at each hierarchy.
15. A computer program product in a non-transitory computer readable medium, the computer program product holding computer program instructions that, when executed by a first processor in a first processing system and a second processor in a second processing system, provide secure computations under Homomorphic Encryption (HE), the computer program instructions comprising program code configured to:
generate an encrypted data point that encrypts one or more elements, wherein at least one element is associated with a plaintext number, the plaintext number being represented in the encrypted data point as a set of one-hot maps, each of the set of one-hot maps corresponding to a coprime factor computed for the plaintext number using a Chinese Remainder Theorem (CRT) encoding;
output the encrypted data point from the first processing system;
receive the encrypted data point at the second processing system;
under homomorphic encryption, generate a one-hot map representation of the plaintext number using the set of one-hot maps;
under homomorphic encryption, perform an operation on the one-hot representation and generate a result; and
provide the result as a response to the encrypted data point from the second processing system.
16. The computer program product as described in claim 15 wherein the program code configured to generate the one-hot map representation comprises program code configured to:
for a given one-hot map of the set of one-bot maps, duplicate the given one-hot map a number of times to generate a vector, the number of times derived by dividing a result of multiplying the coprime factors by the coprime factor for the given one-hot map; and
multiply the vectors.
17. The computer program product as described in claim 15 wherein the plaintext number is a number without coprime factors and that has been padded with one or more zeros.
18. The computer program product as described in claim 15 wherein the operation is a comparison operation associated with evaluation of a decision tree.
19. The computer program product as described in claim 15 wherein the one or more elements are arranged according to a tile tensor-based packing scheme.
20. The computer program product as described in claim 15 wherein the CRT encoding is hierarchical, and the computer program code configured to generate the one-hot map representation is recursively repeated at each hierarchy.