Privacy-enhanced decision tree-based inference on homomorphically-encrypted data
A technique for computationally-efficient privacy-preserving homomorphic inferencing against a decision tree. Inferencing is carried out by a server against encrypted data points provided by a client. Fully homomorphic computation is enabled with respect to the decision tree by intelligently configuring the tree and the real number-valued features that are applied to the tree. To that end, and to the extent the decision tree is unbalanced, the server first balances the tree. A cryptographic packing scheme is then applied to the balanced decision tree and, in particular, to one or more entries in at least one of: an encrypted feature set, and a threshold data set, that are to be used during the decision tree evaluation process. Upon receipt of an encrypted data point, homomorphic inferencing on the configured decision tree is performed using a highly-accurate approximation comparator, which implements a “soft” membership recursive computation on real numbers, all in an oblivious manner.
1. A method for privacy-preserving homomorphic inferencing, comprising:
configuring a decision tree;
receiving an encrypted data point;
performing homomorphic inferencing on the decision tree with respect to the encrypted data point using a homomorphic comparison operation, wherein, for a given decision node, the comparison operation comprises a plurality of sub-operations directed to conditional branches of the decision tree, wherein a sub-operation comprises a recursive computation using an evaluation function EVAL(a≥b)=a n /(a n +b n ), where n is a parameter and a and b are positive real numbers in the range [0,1], wherein the sub-operations and a decision resulting from the comparison operation occur on real number-valued features of the encrypted data point; and
returning an encrypted result.
2. The method as described in claim 1 wherein the comparison operation is a fuzzy comparison, and at least one sub-operation performs a pairwise comparison on floating point values.
3. The method as described in claim 1 wherein pairwise comparisons implemented by the plurality of the sub-operations are carried out using a single instruction, multiple data (SIMD) operation for all decision nodes of the decision tree.
4. The method as described in claim 3 wherein the decision resulting from the comparison operation is computed as a single ArgMax function for an aggregated set of confidence class values.
5. The method as described in claim 1 wherein configuring the decision tree converts an unbalanced decision tree into the decision tree.
6. The method as described in claim 5 further including applying a packing function to one or more entries in at least one of: an encrypted feature set, and a threshold data set, to generate a packed ciphertext.
7. The method as described in claim 6 further including rearranging one or more entries in the packed ciphertext prior to executing the comparison operation.
8. An apparatus, comprising:
a processor;
computer memory holding computer program instructions executed by the processor, the computer program instructions configured to provide privacy-preserving homomorphic inferencing, the computer program instructions configured to:
configure a decision tree;
receive an encrypted data point;
perform homomorphic inferencing on the decision tree with respect to the encrypted data point using a homomorphic comparison operation, wherein, for a given decision node, the comparison operation comprises a plurality of sub-operations directed to conditional branches of the decision tree, wherein a sub-operation comprises a recursive computation using an evaluation function EVAL(a≥b)=a n /(a n +b n ), where n is a parameter and a and b are positive real numbers in the range [0,1], and wherein the sub-operations and a decision resulting from the comparison operation occur on real number-valued features of the encrypted data point; and
return an encrypted result.
9. The apparatus as described in claim 8 wherein the comparison operation is a fuzzy comparison, and at least one sub-operation performs a pairwise comparison on floating point values.
10. The apparatus as described in claim 8 wherein pairwise comparisons implemented by the plurality of the sub-operations are carried out in the processor using a single instruction, multiple data (SIMD) operation for all decision nodes of the decision tree.
11. The apparatus as described in claim 10 wherein the decision resulting from the comparison operation is computed as a single ArgMax function for an aggregated set of confidence class values.
12. The apparatus as described in claim 8 wherein the computer program instructions are further configured to convert an unbalanced decision tree into the decision tree.
13. The apparatus as described in claim 12 wherein the computer program instructions are further configured to apply a ciphertext packing function to one or more entries in at least one of: an encrypted feature set, and a threshold data set, to generate a packed ciphertext.
14. The apparatus as described in claim 13 wherein the computer program instructions are further configured to rearrange one or more entries in the packed ciphertext prior to executing the comparison operation.
15. A computer program product comprising a non-transitory computer readable medium for use in a data processing system to provide privacy-preserving homomorphic inferencing, the computer program product holding computer program instructions that, when executed by the data processing system:
configure a decision tree;
receive an encrypted data point;
perform homomorphic inferencing on the decision tree with respect to the encrypted data point using a homomorphic comparison operation, wherein, for a given decision node, the comparison operation comprises a plurality of sub-operations directed to conditional branches of the decision tree, wherein a sub-operation comprises a recursive computation using an evaluation function EVAL(a≥b)=a n /(a n +b n ), where n is a parameter and a and b are positive real numbers in the range [0,1], and wherein the sub-operations and a decision resulting from the comparison operation occur on real number-valued features of the encrypted data point; and
return an encrypted result.
16. The computer program product as described in claim 15 wherein the comparison operation is a fuzzy comparison, and at least one sub-operation performs a pairwise comparison on floating point values.
17. The computer program product as described in claim 15 wherein pairwise comparisons implemented by the plurality of the sub-operations are carried out using a single instruction, multiple data (SIMD) operation for all decision nodes of the decision tree.
18. The computer program product as described in claim 17 wherein the decision resulting from the comparison operation is computed as a single ArgMax function for an aggregated set of confidence class values.
19. The computer program product as described in claim 15 wherein the computer program instructions convert an unbalanced decision tree into the decision tree.
20. The computer program product as described in claim 19 wherein the computer program instructions configure the decision tree by applying a packing function to one or more entries in at least one of: an encrypted feature set, and a threshold data set, to generate a packed ciphertext.
21. The computer program product as described in claim 20 wherein the computer program instructions rearrange one or more entries in the packed ciphertext prior to executing the comparison operation.