Privacy-preserving evaluation of decision trees

摘要

A method for performing a secure evaluation of a decision tree, including: receiving, by a processor of a server, an encrypted feature vector x=(x₁, . . . , x_n) from a client; choosing a random mask μ₀; calculating m₀ and sending m₀ to the client, wherein m₀=x_i0⁽⁰⁾−t₀⁽⁰⁾+μ₀ and t₀⁽⁰⁾ is a threshold value in the first node in the first level of a decision tree ′; performing a comparison protocol on m₀ and μ₀, wherein the server produces a comparison bit b₀ and the client produces a comparison bit b′₀; choosing a random bit s₀∈{0,1} and when s₀=1 switching a left and right subtrees of ′; sending b₀⊕s₀ to the client; and for each level =1, 2, . . . , d−1 of the decision tree ′, where d is the number of levels in the decision tree ′, perform the following steps: receiving from the client y_k where k=0, 1, . . . , −1; performing a comparison protocol on and , wherein is a random mask and is based upon, x, , y_k, and and the server produces a comparison bit and the client produces a comparison bit ; choosing a random bit ∈{0,1} and when =1 switching all left and right subtrees at level of ′; and sending ⊕ to the client.