A method for performing a secure evaluation of a decision tree, including: receiving, by a processor of a server, an encrypted feature vector x=(x1, . . . , xn) from a client; choosing a random mask μ0; calculating m0 and sending m0 to the client, wherein m0=xi0(0)−t0(0)+μ0 and t0(0) is a threshold value in the first node in the first level of a decision tree ′; performing a comparison protocol on m0 and μ0, wherein the server produces a comparison bit b0 and the client produces a comparison bit b′0; choosing a random bit s0∈{0,1} and when s0=1 switching a left and right subtrees of ′; sending b0⊕s0 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 yk where k=0, 1, . . . , −1; performing a comparison protocol on and , wherein is a random mask and is based upon, x, , yk, 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.