Efficient, remote, private tree-based classification using cryptographic techniques

摘要

A method and apparatus are disclosed herein for classification. In one embodiment, the method comprises performing tree-based classification of a user input by a classifier with a classification tree at a first location, including exchanging data with a second location, different from the first location, to obtain the user input and provide results of classification to a user using singly homomorphic encryption so that the user input is not revealed to the classifier, the classification tree is not revealed to the user and the classifier's output is not revealed to the classifier.

主权项

1. A method comprising:
receiving first encrypted input data, wherein the first encrypted input data comprises input data that has been bit-wise encrypted using an additive homomorphic cryptosystem; computing, with a processor, a function with a classifier, using the first encrypted data, for each node of a classification tree, the classification tree comprising a decision tree that is a multivariate tree having one or more multiple-feature splits; sending second encrypted data that comprises an encrypted version of results of computing the function for said each node; receiving first and second encrypted vectors, each encrypted using the additive homomorphic cryptosystem, the first encrypted vector containing an encrypted version of a vector containing a classification decision at each node in the classification tree and the second encrypted vector containing a complementary of the vector containing a classification decision at each node in the classification tree, wherein each of the first and second encrypted vectors are P-dimensional encrypted binary vectors, and the order of encrypted data in the second vector is not indicative of node location in the classification tree; for each node in a path in the classification tree,
selecting a value from either the first and second encrypted vectors based on the classification decision at said each node, andcomputing a vector of values using the additive homomorphic cryptosystem based on the value using values selected from the first and second encrypted vectors; and sending the vector of values from which decryption of each value in the vector results in a single element in a domain of class values and a corresponding class in the classification tree can be obtained for the input data.