Private decision tree evaluation using an arithmetic circuit

Abstract

A non-interactive protocol is provided for evaluating machine learning models such as decision trees. A client can delegate the evaluation of a machine learning model such as a decision tree to a server by sending an encrypted input and receiving only the encryption of the result. The inputs can be encoded as vector of integers using their binary representation. The server can then evaluate the machine learning model using a homomorphic arithmetic circuit. The homomorphic arithmetic circuit provides an implementation that requires fewer multiplications than a Boolean comparison circuit. Efficient data representations are then combined with different algorithmic optimizations to keep the computational overhead and the communication cost low. Related apparatus, systems, techniques and articles are also described.

Claims

1. A computerized method comprising: receiving, by a server from a client, an encrypted input, the encrypted input including a combination of a data set and a plurality of random integers; receiving the plurality of random integers from a randomizer; identifying the data set in the encrypted input using the plurality of random integers from the randomizer; generating, by the server using a homomorphic arithmetic circuit, a classification of the data set using a decision tree; and providing, by the server to the client, the generated classification to enable the client to decrypt the classification.

2. The method of claim 1, wherein the decision tree is a machine learning model that maps an n-dimensional attribute vector to a finite set of classification labels.

3. The method of claim 2, wherein the decision tree comprises a plurality of internal nodes that each comprise a test condition, and a plurality of leaf nodes that each comprise a classification label.

4. The method of claim 3, wherein the arithmetic circuit evaluates the decision tree using an efficient integer comparison algorithm requiring fewer multiplications than a Boolean comparison circuit.

5. The method of claim 3 further comprising: computing a decision result for each internal node; and aggregating, for each leaf node, the computed decision results along a corresponding path to such leaf node to determine whether one such leaf node has been reached by a classification algorithm.

6. The method of claim 4, wherein the provided generated classification comprises the classification labels.

7. The method of claim 1 further comprising: receiving, by the server from the client, a public key and an evaluation key.

8. The method of claim 1 further comprising: homomorphically encrypting the data set by the client to result in the encrypted input.

9. The method of claim 7, wherein the data set is plaintext and is encoded as vector of integers and encrypted component-wise.

10. The method of claim 1 further comprising: homomorphically evaluating the decision tree.

11. The method of claim 10, wherein an output of the homomorphic evaluation of the decision tree consists of a ciphertext of a corresponding computation result.

12. The method of claim 3 further comprising: encoding a plurality of attribute vectors by the client such that the server can evaluate them together in a single protocol run.

13. The method of claim 3 further comprising: encoding a plurality of threshold values by the server and evaluating them together in a single operation.

14. The method of claim 1, wherein the providing comprises transmitting the generated classification to the client over a network; wherein the method further comprises: decrypting the generated classification by the client.

15. A system comprising: at least one data processor; and memory storing instructions which, when executed by the at least one data processor, result in operations comprising: receiving an encrypted input, the encrypted input including a combination of a data set and a plurality of random integers; receiving the plurality of random integers from a randomizer; identifying the data set in the encrypted input using the plurality of random integers from the randomizer; generating, using a homomorphic arithmetic circuit, a classification of the data set using a decision tree; and transmitting the generated classification over a computer network to a remote computing device to enable decryption the classification.

16. The system of claim 15, wherein: the decision tree is a machine learning model that maps an n-dimensional attribute vector to a finite set of classification labels; and the decision tree comprises a plurality of internal nodes that each comprise a test condition, and a plurality of leaf nodes that each comprise a classification label.

17. The system of claim 16, wherein the arithmetic circuit evaluates the decision tree using an efficient integer comparison algorithm requiring fewer multiplications than a Boolean comparison circuit.

18. The system of claim 17, wherein the operations further comprise: computing a decision result for each internal node; and aggregating, for each leaf node, the computed decision results along a corresponding path to such leaf node to determine whether one such leaf node has been reached by a classification algorithm.

Description

DESCRIPTION OF DRAWINGS

(1) FIG. 1 is a process flow diagram illustrating private decision tree evaluation using an arithmetic circuit; and

(2) FIG. 2 is a diagram illustrating a computing device for implementing aspects of the current subject matter.

DETAILED DESCRIPTION

(3) The current subject matter addresses the problem of privately evaluating a machine learning model such as a decision tree on private data. As will be described in more detail below, a server executes a private decision tree model and a client seeks to classify a private attribute vector using the server's private model. The goal of the computation is to obtain the classification while preserving the privacy of both—the decision tree and the client input. After the computation, the classification result is revealed only to the client, and beyond that, nothing further is revealed to neither party.

(4) The following describes a client-server protocol that delegates the complete tree evaluation to the server while preserving privacy and keeping the performance acceptable. The current subject matter can use fully (somewhat) homomorphic encryption and evaluate decision trees on ciphertexts encrypted under the client's public key. As a result, no intermediate or final computational result is revealed to the evaluating server. The core operation in a decision tree evaluation is the comparison of integer. This comparison can be done using a binary circuit with the advantage of having a decision tree protocol with sublinear (in the size of the tree) to constant communication. However, comparing two μ-bit integers using a binary circuit requires a circuit with a depth of log(μ−1)+1 and (μ log(μ)) homomorphic multiplications. As such, a modified version of the integer comparison is provided herein such that it can be evaluated using an arithmetic homomorphic circuit. The resulting circuit has depth of log(μ−1) and requires exactly log(μ) multiplications. Moreover, when used for decision trees, the arithmetic comparison circuit does not increase the circuit multiplicative depth of the decision tree evaluation as the binary comparison circuit.

(5) A homomorphic encryption (HE) allows computations on ciphertexts by generating an encrypted result whose decryption matches the result of a function on the plaintexts. Homomorphic encryption schemes (particularly lattice-based) can be used that allow many chained additions and multiplications to be computed on plaintext homomorphically. A HE scheme consists of the following algorithms: pk, sk, ek←KGen (λ): This probabilistic algorithm takes a security parameter k and outputs public, private and evaluation key pk, sk and ek. c←Enc(pk,m): This probabilistic algorithm takes pk and a message m and outputs a ciphertext c. m is used herein as a shorthand notation for Enc(pk,m). c←Eval(ek, c.sub.1, . . . , c.sub.n): This probabilistic algorithm takes ek, an n-ary function ƒ and n ciphertexts c.sub.1, . . . , c.sub.n and outputs a ciphertext c. m′←Dec(sk, c): This deterministic algorithm takes sk and a ciphertext c and outputs a message m′.

(6) With the current subject matter, the homomorphic encryption should have the property of indistinguishability under Chosen Plaintext Attack techniques (IND-CPA) and the following correctness conditions for all m.sub.1, . . . , m.sub.n: Dec(sk, Enc(pk, m.sub.i))=Dec(sk, mi)=m.sub.i, Dec(sk, Eval(ek, ƒ, m.sub.1, . . . , m.sub.i))=Dec(sk, ƒ(m.sub.1, . . . , m.sub.n)).

(7) The encryption algorithm Enc adds “noise” to the ciphertext which increases during homomorphic evaluation. While addition of ciphertexts increases the noise linearly, the multiplication increases it exponentially. If the noise becomes too large, then correct decryption is no longer possible. To prevent this from happening, one can either keep the circuit's depth of the function ƒ low enough or use a refresh algorithm. This algorithm consists of the bootstrapping procedure, which takes a ciphertext with large noise and outputs a ciphertext (of the same message) with a smaller amount of noise. With the current subject matter, the circuit's depth is kept low to ensure that the noise does not overwhelm the ciphertext and prevent correct decryption. This allows the usage of somewhat homomorphic encryption (SHE) and avoid bootstrapping. Therefore, in the current subject matter, the homomorphic operations will be prefixed with “SHE” for somewhat homomorphic encryption.

(8) A Brakerski-Gentry-Vaikuntanathan (BGV) type homomorphic encryption scheme can be used. Plaintexts can be encrypted using an integer representation (an integer x.sub.i is encrypted as x.sub.i) or a binary representation (each bit of the bit representation x.sub.i.sup.b: =x.sub.iμ. . . x.sub.i1 is encrypted). The encryption scheme as required herein can support Smart and Vercauteren's ciphertext packing (SVCP) technique to pack many plaintexts in one ciphertext. Using SVCP, a ciphertext consists of a fixed number s of slots, each capable of holding one plaintext, i.e. .Math.|.Math.| . . . |.Math.. The encryption of a bit b replicates b to all slots, i.e., b=b|b| . . . |b. However, the bits of x.sub.i.sup.b:can be packed in one ciphertext and denoted by {right arrow over (x)}.sub.i=x.sub.iμ|0| . . . |0. The computation relies on some built-in routines, that allow homomorphic operations on encrypted data. The relevant routines required to the homomorphic encryption scheme are: addition (SHEADD), multiplication (SHEMULT) and comparison (SHECMP). These routines are compatible with the ciphertext packing technique (i.e., operations are replicated on all slots in a SIMD manner).

(9) The routine SHEADD takes two or more ciphertexts and performs a component-wise addition modulo two, i.e., we have:
SHEADD(b.sub.i1| . . . |b.sub.is,b.sub.j1| . . . |b.sub.js)=b.sub.i1⊕b.sub.j1| . . . |b.sub.is⊕b.sub.js| . . . |b.sub.is⊕b.sub.js.

(10) Similarly, SHEMULT performs component-wise multiplication modulo two, i.e., there is:
SHEMULT(b.sub.i1| . . . |b.sub.is,b.sub.j1| . . . |b.sub.js)=b.sub.i1.Math.b.sub.j1| . . . |b.sub.is.Math.b.sub.js.

(11) Let x.sub.i, x.sub.1 be two integers, b.sub.ij=[x.sub.i>x.sub.j] and b.sub.ji=[x.sub.j>x.sub.i], the routine SHECMP takes x.sub.i.sup.b, x.sub.j.sup.b compares x.sub.i and x.sub.j and returns b.sub.ij, b.sub.ji:
b.sub.ij,b.sub.ji←SHECMP(x.sub.i.sup.b , x.sub.j.sup.b).

(12) Note that if the inputs to SHECMP encrypt the same value, then the routine outputs two ciphertexts of 0. This routine implements the comparison circuit described in.

(13) Beyond arithmetic and comparison operation, it is assumed that the encryption support shift operations. Given a packed ciphertext b.sub.1| . . . |b.sub.s, the shift left operation SHESHIFTL shifts all slots to the left by a given offset, using zero-fill, i.e., we have:
SheShiftL(b.sub.1| . . . |b.sub.s,i)=b.sub.i| . . . |b.sub.s|0| . . . |0.

(14) The shift right operation is defined similarly for shifting to the right.

(15) With the current subject matter, a decision tree (DT) is a function
:.sup.n.fwdarw.{c.sub.0, . . . ,c.sub.k−1}
that maps an n-dimensional attribute vector (x.sub.0, x.sub.n−1) to a finite set of classification labels. The tree consists of: internal nodes (decision nodes) containing a test condition leave nodes containing a classification label.

(16) A decision tree model consists of a decision tree and the following functions:

(17) a function thr that assigns to each decision node a threshold value, thr: [0, m−1]>, a function att that assigns to each decision node an attribute index, att: [0, m−1].fwdarw.[0, n−1], and a labeling function lab that assigns to each leaf node a label, lab: [m, M−1]>{c.sub.0, . . . , c.sub.k−1}.

(18) The decision at each decision node is a “greater-than” comparison between the assigned threshold and attribute values, i.e., the decision at node v is [x.sub.att(v)≥thr(v)].

(19) Given a decision tree, the index of a node is its order as computed by breadth-first search (BFS) traversal, starting at the root with index 0. If the tree is complete, then a node with index ν has left child 2v+1 and right child 2v+2.

(20) The node with index ν as the node ν. W.l.o.g, [0, k−1] will be used as classification labels (i.e., c.sub.j=j for 0≤j≤k−1) and the first (second, third, . . . ) leaf in BFS traversal will be labeled with classification label 0 (1, 2, . . . ). For a complete decision tree with depth d the leaves have indices ranging from 2.sup.d, 2.sup.d+1, . . . , 2.sup.d+1−2 and classification labels ranging from 0, . . . , 2.sup.d−1 respectively. Since the classification labeling is now independent of the tree, =(, thr, att) can be used to denote a decision tree model consisting of a tree T and the labeling functions thr, att as defined above. It can be assumed that the tree parameters d, m, can be derived from .

(21) Given x=(x.sub.0, . . . , x.sub.n−1) and =(, thr, att), then starting at the root, the Decision Tree Evaluation (DTE) evaluates at each reached node v the decision b∂[x.sub.att(v)≥thr(v)] and moves either to the left (if b=0) or right (if b=1) subsequent node. The evaluation returns the label of the reached leaf as result of the computation. This result can be denoted by (x).

(22) Let x=(x.sub.0, . . . , x.sub.n−1) be a client's private attribute vector and =(, thr, att) be a server's private decision tree model. A private DTE (PDTE) functionality evaluates the model on input x, then reveals to the client the classification label (x) and nothing else, while the server learns nothing, i.e.,
.fwdarw.(ϵ,(x)).

(23) Let x=(x.sub.0, . . . , x.sub.n−1) be a client's private attribute vector and =(thr, att) be a server's private decision tree model. A protocol II correctly implements a PDTE functionality if after the computation it holds for the result c obtained by the client that c=(x).

(24) Besides correctness, parties must learn only what they are allowed to. To formalize this, the following two definitions are needed. A function μ: .fwdarw. is negligible if for every positive polynomial p(.) there exists an c such that for all n>ϵ: μ(n)<1/p(n). Two distributions .sub.1 and .sub.2 are computationally indistinguishable (denoted .sub.1.sub.2) if no probabilistic polynomial time (PPT) algorithm can distinguish them except with negligible probability.

(25) In SMC protocols, the view of a party consists of its input and the sequence of messages that it has received during the protocol execution. The protocol is said to be secure, if for each party, one can construct a simulator that, given only the input of that party and the output, can generate a distribution that is computationally indistinguishable to the party's view.

(26) With regard to PDTE Security, let x=(x.sub.0, . . . , x.sub.n−1) be a client's private attribute vector and =(, thr, att) be a server's private decision tree model. A protocol Π.sub.DTE securely implements the PDTE functionality in the semi-honest model if the following conditions hold: there exists a PPT algorithm Sim.sub.S.sup.pdte that simulates the server's view View.sub.S.sup.Π.sup.PDTE given only the private decision tree model (, thr, att) such that:
Sim.sub.S.sup.pdte(,ε)View.sub.S.sup.Π.sup.PDTE(,x),  (1) there exists a PPT algorithm Sim.sub.C.sup.pdte that simulates the client's view View.sub.C.sup.Π.sup.PDTE given only the depth d of the tree, x=(x.sub.0, . . . , x.sub.n−1) and a classification label (x)∈{0, . . . , k−1} such that:
Sim.sub.C.sup.pdte(d,x,(x))View.sub.C.sup.Π.sup.PDTE(,x).  (2)

(27) A protocol Π.sub.PDTE securely implements the PDTE functionality with one-sided simulation if the following conditions hold: for every pair x, x′ of different client's input vector it holds:
View.sub.s.sup.Π.sup.PDTE(,x)View.sub.S.sup.Π.sup.PDTE(,x′),  (3) Π.sub.PDTE is simulatable against every PPT adversary controlling C.

(28) Note that for the one-sided simulation, the requirement in Equation 3 is that the protocol should be indistinguishable against any PPT adversary that controls the server. This means, the server should not be able to distinguish between the case where the client uses x and the case where it uses x′. Moreover, the protocol should be simulatable in against any adversary controlling the client.

(29) The following describes a comparison protocol using an integer encoding which is based on Lin and Tzeng protocol. Let x.sub.i and x.sub.j be inputs of client and server, respectively, with the goal to compute [x.sub.i>x.sub.1]. With regard to input encoding, let INT(y.sub.η. . . y.sub.1)=y be a function that takes a bit string of length η and parses it into the η-bit integer y=Σ.sub.l=1.sup.ηy.sub.l.Math.2.sup.l−1. The 0-encoding V.sub.x.sub.i.sup.0 and 1-encoding V.sub.x.sub.i.sup.1 of an integer input x.sub.i are the following vectors: V.sub.x.sub.i.sup.0=(ν.sub.iμ, . . . , ν.sub.i1), V.sub.x.sub.i.sup.1=(u.sub.iμ, . . . , u.sub.i1), such that for each l, (1≤l≤μ)

(30) $v_{il}=\{\begin{array}{cc}INT\left(x_{i\mu }{x}_{i\mu -1}\mathrm{.Math.}{x}_{il},1\right)& \mathrm{if}{x}_{il}=0\\ r_{il}^{\left(0\right)}& \mathrm{if}{x}_{il}=1\end{array}{u}_{il}=\{\begin{array}{cc}I\mathrm{NT}\left(x_{i\mu }{x}_{i\mu -1}\mathrm{.Math.}{x}_{il}\right)& \mathrm{if}{x}_{il}=1\\ r_{il}^{\left(1\right)}& \mathrm{if}{x}_{il}=0,\end{array}$

(31) where l′=l+1, r.sub.il.sup.(0), r.sub.il.sup.(1) are random numbers of a fixed bitlength ν>μ (e.g. 2.sup.μ≤r.sub.il.sup.(0), r.sub.il.sup.(1)<2.sup.μ+1) with LSB(r.sub.il.sup.(0))=0 and LSB(r.sub.il.sup.(1))=1 (LSB is the least significant bit). If the INT function is used the compute the element at position 1, then we call it a proper encoded element otherwise we call it a random encoded element. Note that a random encoded element r.sub.il.sup.(1) at position l in the 1-encoding of x.sub.i is chosen such that it is guaranteed to be different to a proper or random encoded element at position 1 in the 0-encoding of x.sub.j, and vice versa. Hence, it enough if r.sub.il.sup.(1) and r.sub.il.sup.(0) are one or two bits longer than any possible proper encoding element at position l. Also note that the bit string x.sub.iμx.sub.iμ−1 . . . x.sub.il is interpreted by the function INT as the bit string y.sub.μ−l+1 . . . y.sub.1 with length μ−l+1 where y.sub.1=x.sub.i1, y.sub.2=x.sub.i(l+1), . . . , y.sub.μ−l+1=x.sub.iμ. If we see V.sub.x.sub.i.sup.0, V.sub.x.sub.j.sup.1 as sets, then x.sub.i>x.sub.1 iff they have exactly one common element.

(32) For example, if μ=3, x.sub.i=6=110.sub.2 and x.sub.1=2=010.sub.2 then
V.sub.x.sub.i.sup.0=(INT(1),r.sub.j2.sup.(0),INT(011)=(1,r.sub.j2.sup.(0),3)

(33) and V.sub.x.sub.i.sup.1−V.sub.x.sub.j.sup.0=(0, r.sub.2, r.sub.1), where r.sub.2=3−r.sub.j2.sup.(0) and r.sub.1=r.sub.i1.sup.(1)−3 are random numbers. On the other hand, if x.sub.i=2=010.sub.2 and x.sub.j=6=110.sub.2 then V.sub.x.sub.i.sup.1=(r.sub.i3.sup.(1),1, r.sub.i1.sup.(1)), V.sub.x.sub.j.sup.0=(r.sub.j3.sup.(0), r.sub.j2.sup.(0), 7) and V.sub.x.sub.i.sup.1−V.sub.x.sub.j.sup.0=(r.sub.3, r.sub.2, r.sub.1) where r.sub.3=r.sub.i3.sup.(1)−r.sub.j3.sup.(0), r.sub.2=1−r.sub.j2.sup.(0) and r.sub.1=r.sub.i1.sup.(1)−7 are all random numbers.

(34) Let x.sub.i and x.sub.j be two integers, then x.sub.i>x.sub.j iff V=V.sub.x.sub.i.sup.1−V.sub.x.sub.j.sup.0 has a unique position with 0.

(35) A proof: if V=V.sub.x.sub.i.sup.1−V.sub.x.sub.j.sup.0 has a unique 0 at a position l, (1≤l≤μ) then μ.sub.il and ν.sub.il have bit representation y.sub.μ−l+1 . . . y.sub.1, where for each h, μ−l+1≥h≥2, y.sub.h=x.sub.ig=x.sub.jg with g=l+h−1, and y.sub.1=x.sub.il=1 and x.sub.jl=0. It follows that x.sub.i>x.sub.j.

(36) If x.sub.i>x.sub.j then there exists a position l such that for each h, μ≥h≥l+1, x.sub.ih=x.sub.jh and x.sub.il=1 and x.sub.jl=0. This implies u.sub.il=ν.sub.il.

(37) For h, μ≥h>l+1, either u.sub.ih bit string is a prefix of x.sub.i while V.sub.jh is random, or u.sub.ih is random while ν.sub.jh bit string is a prefix of x.sub.j. From the choice of r.sub.ih.sup.(0), r.sub.ih.sup.(1), we have u.sub.ih≠ν.sub.ih.

(38) For h, l−1≥h≥1 there are three cases: u.sub.ih and ν.sub.ih (as bit string) are both prefixes of x.sub.i and x.sub.j, only one of them is prefix, both are random. For the first case the difference of the bits at position 1 and for the other cases the choice of r.sub.uh.sup.(0) imply that u.sub.ih≠ν.sub.ih. This concludes the proof

(39) Protocol: let V.sub.x.sub.i.sup.0 =ν.sub.iμ, . . . , ν.sub.i1 (respectively V.sub.x.sub.i.sup.1=u.sub.iμ, . . . , u.sub.i1) denote the componentwise encryption of V.sub.x.sub.i.sup.0 (resp. V.sub.x.sub.i.sup.1). The client sends V.sub.x.sub.i.sup.0 , V.sub.x.sub.i.sup.1 to the server. To determine the comparison bit for x.sub.i>x.sub.j, the server evaluates the function LIN COMPARE (V.sub.x.sub.i.sup.1, V.sub.x.sub.j.sup.0) (Algorithm 1) which returns μ ciphertexts among which exactly one encrypts zero if an only if x.sub.i>x.sub.j. For the decision tree evaluation, the server omits the randomization in Step 6 and the random permutation in Step 7, since this not the final result. Moreover, the server collects the difference ciphertexts c.sub.l in an array and uses the multiplication algorithm with logarithmic multiplicative depth.

(40) In contrast to the original protocol, there can be differences such as:

(41) Additively HE instead of multiplicative: As explained above multiplication increases the noise exponentially while addition increases it only linearly.

(42) The INT function: Instead of relying on a collision-free hash function as the original protocol, we use the INT function which is simpler to implement and more efficient as it produces smaller values.

(43) The choice of random encoded elements r.sub.il.sup.(0), r.sub.il.sup.(1): We choose the random encoded elements as explained above and encrypt them, while the original protocol uses ciphertexts chosen randomly in the ciphertext space.

(44) TABLE-US-00001 Algorithm 1: Modified Lin-Tzeng Comparison Protocol 1: function LINCOMPARE ( V.sub.xi.sup.1 , V.sub.xj.sup.0 ) 2:  parse V.sub.xi.sup.1  as u.sub.iμ , ... , u.sub.i1 3:  parse V.sub.xj.sup.0  as ν.sub.iμ , ... , ν.sub.i1 4:  for l := 1 to μ do 5:   choose a random r.sub.l from the plaintext space 6.   c.sub.l = (u.sub.il − ν.sub.jl) • r.sub.l 7:  choose a random permutation π 8:  return π(c.sub.μ, ... , c.sub.1)

(45) Encrypting the encodings on both side: In the original protocol, the evaluator has access to x.sub.j in plaintext and does not need to choose random encoded elements. By encoding as explained in our modified version, we can encrypt both encodings and delegate the evaluation to a third party which is not allowed to have access to the inputs in plaintext.

(46) Aggregation: The multiplication of the ciphertexts returned by Algorithm 1 returns a ciphertext encrypting either 0 or a random number.

(47) Edges of the tree can be marked with the corresponding comparison result. So if the comparison at node ν is the bit b then the right edge is marked outgoing from ν with b and the left edge is marked with 1-b. This information can be stored at the child nodes of ν and refer to it as cmp.

(48) For a decision tree model =(, thr, att), Node can be a data structure that for each node ν defines the following: ν.threshold stores the threshold thr(ν) of the node ν ν.aIndex stores the associated index att(ν) ν.parent stores the pointer to the parent node which is null for the root node ν.left stores the pointer to the left child node which is null for each leaf node

(49) TABLE-US-00002 Algorithm 2: Modified Lin-Tzeng Protocol for PDTE 1: function LINCOMPAREDT ( V.sub.xi.sup.1 , V.sub.xj.sup.0 ) 2:  parse V.sub.xi.sup.1  as u.sub.iμ , ... , u.sub.i1 3:  parse V.sub.xj.sup.0  as ν.sub.iμ , ... , ν.sub.i1 4:  let queue be an empty queue 5:  for l := 1 to μ do 6.   c.sub.l = u.sub.il − ν.sub.jl 7:   queue.enqueue(c.sub.l) 8:  return LOGCHAINEDMUL(queue) 1: function LOGCHAINEDMUL(queue) 2:  while queue.size( ) > 1 do 3:   c.sub.1 ← queue.dequeue() 4:   c.sub.2 ← queue.dequeue() 5:   c.sub.2 ← c.sub.2 • c.sub.1 6:   queue.enqueue(c2) 7:  return queue.dequeue( ) ν.right stores the pointer to the right child node which is null for each leaf node ν.cmp is computed during the tree evaluation and stores the comparison bit b←[x.sub.att(ν.parent)≥thr(ν.parent)] if ν is a right node. Otherwise it stores 1-b. ν.cLabel stores the classification label if ν is a leaf node and the empty string otherwise.

(50) is used to denote the set of all decision nodes and the set of all leave nodes of . As a result, the equivalent notation =(, thr, att)=(, ) can be used.

(51) With the data structure defined above, the classification function can be defined as follows. Let x=(x.sub.0, . . . , x.sub.n−1) be an attribute vector and =(, ) a decision tree model. The classification function can be defined as:
f.sub.c(x,)=tr(x,root),

(52) where root is the root node and tr is the traverse function defined as:

(53) $tr\left(x,v\right)=\{\begin{array}{cc}tr\left(x,v.\mathrm{left}\right)& \mathrm{if}v\in 𝒟\mathrm{and}{x}_{v.\mathrm{aInde}x}<v.\mathrm{threshold}\\ tr\left(x,v.\mathrm{right}\right)& \mathrm{if}v\in 𝒟\mathrm{and}{x}_{v.\mathrm{aInde}x}\ge v.\mathrm{threshold}\\ v& \mathrm{if}v\in ℒ\end{array}$

(54) Let x=(x.sub.0, . . . , x.sub.n−1) be an attribute vector and =(,thr,att)=(, ) a decision model such that:
(x)=b.Math.tr(x,root.right)+(1−b).Math.tr(x,root.left),

(55) where b=[x.sub.att(root)≥thr(root)] is the comparison at the root node.

(56) The proof follows by induction on the depth of the tree. In the base case, there is a tree of depth one (i.e., the root and two leaves). In the induction step, there are two trees of depth d which can be joined by adding a new root.

(57) Initialization includes a one-time key generation in which the client generates appropriate triple (pk, sk, ek) of public, private and evaluation keys for a homomorphic encryption scheme. Then the client sends (pk, ek) to the server. For each input classification, the client just encrypts its input and sends it to the server. To reduce the communication cost of sending client's input, one can use a trusted randomizer that does not take part in the real protocol and is not allowed to collaborate with the server. The trusted randomizer generates a list of random strings r and sends the encrypted strings r to server and the list of r's to the client. For an input x, the client then sends x+r to the server in the real protocol. This technique is similar to the commodity-based cryptography with the difference that the client can play the role of the randomizer itself and sends the list of r's (when the network is not too busy) before the protocol's start.

(58) With regard to encoding and encrypting input, the protocol starts with the client encoding, encrypting and sending its input to the server. For each attribute value x.sub.i the client sends the encryptions V.sub.x.sub.i.sup.0=(ν.sub.iμ, . . . , ν.sub.i1) and V.sub.x.sub.i.sup.1=(u.sub.iμ, . . . , u.sub.i1) of the 0-encoding V.sub.x.sub.i.sup.0 and 1-encoding V.sub.x.sub.i.sup.1 of x.sub.i. We let
V.sub.x=[(V.sub.x.sub.1.sup.0,V.sub.x.sub.1.sup.1), . . . (V.sub.x.sub.n.sup.0,V.sub.x.sub.n.sup.1)]

(59) denote the encoding and encryption of all attribute values in x.

(60) The server does the same with the threshold values. For each threshold value y.sub.j the server computes the encryptions V.sub.y.sub.j.sup.0=ν.sub.jμ, . . . , ν.sub.j1 and V.sub.yj.sup.1=u.sub.jμ, . . . , u.sub.j1) of the 0-encoding V.sub.y.sub.j.sup.0 and 1-encoding V.sub.y.sub.j.sup.1 of y.sub.j. We let
={(V.sub.y.sub.j.sup.0,V.sub.y.sub.j.sup.1)|ν∈Λν.threshold=y.sub.j}.
denote the encoding and encryption of all threshold values in . This computation is illustrated by Encode(x) and Encode() in Protocol 6. Note that, this is still compatible with the trusted randomizer technique, where we will use sequences of random integers.

(61) TABLE-US-00003 Algorithm 3: Computing Decision Bits 1: function EVALDNODE( ,   , V.sub.x ) 2:  for each ν ϵ  do 3:   let y.sub.j ← ν.threshold and i ← ν.aIndex 4:    ν.right.cmp  ← LINCOMPAREDT ( V.sub.xi.sup.1 , V.sub.yj.sup.0 ) 5:    ν.left.cmp  ← LINCOMPAREDT ( V.sub.yj.sup.1 , V.sub.xi.sup.0 )

(62) TABLE-US-00004 Algorithm 4: Aggregating Decision Bits 1: function EVALPATHS ( , ) 2:  for each ν ϵ  do 3:   let P.sub.ν be the array of nodes on the path (root .fwdarw. ν) 4:    cost.sub.ν   ← 0  5:   for each u ϵ P.sub.ν do 6:     cost.sub.ν   ← cost.sub.ν   + u.cmp 

(63) With regard to evaluating decision nodes, the server evaluates the comparison at each decision node. For each decision node ν∈, let ν.threshold=y.sub.j and i=ν.aIndex. It can be assumed that x.sub.i≠y.sub.j for all i, j. The parties can ensure this by having the client adding a bit 0 to the bit representation of each x.sub.i, and the server adding a bit 1 to the bit representation of each y.sub.j before encoding the values. Then from the definition of the tree evaluation, we move to the right if [x.sub.i≥y.sub.j] or the left otherwise. This is equivalent of testing [x.sub.i>y.sub.j] or [y.sub.j>x.sub.i], since we assume x.sub.i≠y.sub.j. Therefore, for each decision node y.sub.j with corresponding attribute x.sub.i, the server uses LINCOMPAREDT (V.sub.x.sub.i.sup.1, V.sub.y.sub.j.sup.0) to mark the edge right to y.sub.j (i.e., store it at the right child node of ν) and LINCOMPAREDT (V.sub.y.sub.j.sup.1, V.sub.x.sub.i.sup.0) to mark the edge left to y.sub.j (i.e., store it at the left child node of ν). It is illustrated in Algorithm 3.

(64) With regard to aggregating decision results, then for each node ν∈, the server aggregates the comparison results along the path from the root to ν. As a result of Algorithm 3, one edge of each decision node is marked with a ciphertext of 0, while the other will be marked with a ciphertext of a random plaintext. It follows that the sum of marks along each path of the tree, will result to an encryption of 0 for the classification path and an encryption of a random plaintext for other paths. This computation is illustrated in Algorithm 4.

(65) To reveal the final result to the client, the following can be performed. For each ciphertext cost.sub.ν of Algorithm 4, the server chooses a random number r.sub.ν, computes result.sub.ν←cost.sub.ν.Math.r.sub.ν+ν.cLabel and sends the resulting ciphertexts to the client in a random order. This is illustrated in Algorithm 5. Alternatively, the server can make a trade-off between communication and computation by using the shift operation to pack many result.sub.νin a single ciphertext.

(66) TABLE-US-00005 Algorithm 5: Finalizing 1: function FINALIZE( ) 2:  for each ν ϵ  do 3:   choose a random number r.sub.ν 4:    result.sub.ν  ← cost.sub.ν • r.sub.ν + ν.cLabel

(67) TABLE-US-00006 Protocol 6: The Basic Protocol Client Server Input: x Input:  = ( , ) Output:  (x) Output: ε V.sub.x   ← ENCODE(X)    ← ENCODE( ) EVALDNODE( ,   , V.sub.x  ) EVALPATHS ( , )  (x)  ←FINALIZE( ) DECODE(  (x))

(68) As illustrated in Algorithm 6, the whole computation is performed by the server. The server sequentially computes the algorithms described above and sends the resulting ciphertexts to the client. The client decrypts and outputs the resulting classification label. The correctness is straightforward and follows from above.

(69) With the current subject matter, ciphertext packing can be used to improve computation and communication. Ciphertext packing means that each ciphertext encrypts s bits, where s is the number of slots in the ciphertext. Then we can use this property in three different ways. First, one could pack each encoding (0 or 1) of each value (attribute or threshold) in a single ciphertext allowing the server to compute the difference in Step 6 LINCOMPAREDT( ) with one homomorphic operation (instead of μ). Second, one could encrypt several attributes together and classify them with a single protocol evaluation. Finally, one could encrypt multiple decision node thresholds that must be compared to the same attribute in the decision tree model.

(70) Packing 0-Encodings and 1-Encodings. A modified Lin-Tzeng comparison as provided herein requires only component-wise subtraction and a multiplication of all components. Therefore, the client can pack the 0-encoding of each x.sub.i in one ciphertext and sends ν.sub.iμ| . . . |ν.sub.i1|0| . . . |0 instead of V.sub.x.sub.i.sup.0 (and similar for the 1-encoding). Then, the server does the same for each threshold value and evaluates the decision node by computing the differences d.sub.ij←u.sub.iμ−ν.sub.jμ| . . . |u.sub.i1−ν.sub.j1|0| . . . |0 with one homomorphic subtraction. To multiply the μ relevant components in d.sub.ij, we use |μ| (bitlength of μ) left shifts and IA multiplications to shift Π.sub.l=1.sup.μ(u.sub.il−ν.sub.jl) to the first slot. The path evaluation and the computation of the result's ciphertext remain as explained above.

(71) Packing Attribute Values. Let x.sup.(1), . . . , x.sup.(s) be s possible attribute vectors with x.sup.(l)=[x.sub.1.sup.(1), . . . , x.sub.n.sup.(l)], 1≤l≤s. For each x.sub.i.sup.(l), let V.sub.x.sub.i.sup.0(l)=ν.sub.iμ.sup.(l), . . . , ν.sub.i1.sup.(l) be the 0-encoding. Then, the client generates for each attribute x.sub.i the ciphertexts cx.sub.iμ.sup.0, . . . , cx.sub.i1.sup.0, cx.sub.i1.sup.0 as illustrated in Equation 4. The client does similarly for the 1-encodings.

(72) $\begin{array}{cc}〚{\mathrm{cx}}_{i1}^0〛=〚v_{i1}^{\left(1\right)}\left|v_{i1}^{\left(2\right)}\right|\text{.Math.}|v_{i1}^{\left(s\right)}〛〚{\mathrm{cx}}_{i2}^0〛=〚v_{i2}^{\left(1\right)}\left|v_{i2}^{\left(2\right)}\right|\text{.Math.}|v_{i2}^{\left(s\right)}〛\mathrm{Packing}\mathrm{of}\mathrm{multiple}{V}_{x_i}^0\mathrm{.Math.}〚{\mathrm{cx}}_{i\mu }^0〛=〚v_{i\mu }^{\left(1\right)}\left|v_{i\mu }^{\left(2\right)}\right|\text{.Math.}|v_{i\mu }^{\left(s\right)}〛& \left(4\right)\end{array}$

(73) To shorten the notation, let y.sub.j denote the threshold of j-th decision node (i.e., y.sub.j=ν.sub.j.threshold) and let V.sub.yj.sup.0=ν.sub.jμ, . . . , ν.sub.j1 be the corresponding 0-encoding. The server encrypts V.sub.y.sub.j.sup.0 as illustrated in Equation 5. The 1-encoding is encrypted similarly.

(74) $\begin{array}{cc}〚{\mathrm{cy}}_{j1}^0〛=〚v_{j1}\left|v_{j1}\right|\mathrm{.Math.}|v_{j1}〛〚{\mathrm{cy}}_{j2}^0〛=〚v_{j2}\left|v_{j2}\right|\mathrm{.Math.}|v_{j2}〛\mathrm{Packing}\mathrm{of}a\mathrm{single}{V}_{y_j}^0\mathrm{.Math.}〚{\mathrm{cy}}_{j\mu }^0〛=〚v_{j\mu }\left|v_{j\mu }\right|\text{.Math.}|V_{j\mu }〛& \left(5\right)\end{array}$

(75) The above described encoding allows to compare s attribute values together with one threshold. This is possible because the routine LINCOMPAREDT( ) is compatible with SVCP such that we have:
LINCOMPAREDT((cx.sub.iμ.sup.1, . . . ,cx.sub.i1.sup.1),(cy.sub.jμ.sup.0, . . . ,cy.sub.j1.sup.0))=b.sub.ij.sup.(1)|b.sub.ij.sup.(2)| . . . |b.sub.ij.sup.(s),  (6)
where b.sub.iJ.sup.(l)=0 if x.sub.i.sup.(l)>y.sub.j and b.sub.ij.sup.(l) is a random number otherwise. This results in a single ciphertext such that the l-th slot contains the comparison result between x.sub.i.sup.(l) and y.sub.j.

(76) Aggregating decision bits remains unchanged as described in Algorithm 4. This results in a packed ciphertext b.sub.ν=b.sub.ν.sup.(1)| . . . |b.sub.ν.sup.(s) for each leaf ν∈, where b.sub.ν.sup.(l)=0 if x.sup.(l) classifies to leaf ν and b.sub.u.sup.(l) is a random number for any other leaf u∈−{ν}. Algorithm 5 remains unchanged as well.

(77) Packing Threshold Values. In this case, the client encrypts single attribute in one ciphertext, while the server encrypts multiple threshold values in a single ciphertext. Hence, for an attribute value x.sub.i, the client generates the ciphertexts as in Equation 7 for the 0-encoding and handles the 1-encoding similarly.

(78) $\begin{array}{cc}〚{\mathrm{cx}}_{i1}^0〛=〚v_{i1}\left|v_{i1}\right|\mathrm{.Math.}|v_{i1}〛〚{\mathrm{cx}}_{i2}^0〛=〚v_{i2}\left|v_{i2}\right|\mathrm{.Math.}|v_{i2}〛\mathrm{Packing}\mathrm{of}a\mathrm{single}{V}_{x_i}^0\mathrm{.Math.}〚{\mathrm{cx}}_{i\mu }^0〛=〚v_{i\mu }\left|v_{i\mu }\right|\mathrm{.Math.}|v_{i\mu }〛& \left(7\right)\end{array}$

(79) Let m.sub.i be the number of decision nodes that compare to the attribute x.sub.i (i.e., m.sub.i=|{ν.sub.j∈: ν.sub.j.aIndex=i}|). The server packs all corresponding threshold values in

(80) $.Math.\frac{m_i}{s}.Math.$
ciphertext(s) as illustrated in Equation 8 for the 0-encoding and handles the 1-encoding similarly.

(81) $\begin{array}{cc}〚{\mathrm{cy}}_{j1}^0〛=〚v_{j_{1}1}\left|\mathrm{.Math.}\right|v_{j_{m_i}1}|\mathrm{.Math.}〛〚{\mathrm{cy}}_{j2}^0〛=〚v_{j_{1}2}\left|\text{.Math.}\right|v_{j_{m_i}2}|\mathrm{.Math.}〛\mathrm{Packing}\mathrm{of}\mathrm{multiple}{V}_{y_j}^0\mathrm{.Math.}〚{\mathrm{cy}}_{j\mu }^0〛=[v_{j_1\mu }\left|\mathrm{.Math.}\right|v_{j_{m_i}\mu }|\mathrm{.Math.}〛& \left(8\right)\end{array}$

(82) The packing of threshold values allows to compare one attribute value against multiple threshold values together. Unfortunately, the slot cannot be accessed while performing homomorphic operation. Hence, to aggregate the decision bits, m.sub.i copies of the resulting packed decision results can be made, and each decision result can be shifted to the first slot. Then the aggregation of the decision result and the finalizing algorithm work as in the previous case with the only difference that only the result in the first slot matters and the remaining slots can be set to 0.

(83) FIG. 1 is a process flow diagram 100 in which, at 110, a server receives an encrypted input that encapsulates a data set. Thereafter, at 120, the server generates a classification based on the data set using a homomorphic arithmetic circuit. The generated classification is then provided by the server to the client, at 130, to enable the client to decrypt the classification.

(84) FIG. 2 is a diagram 200 illustrating a sample computing device architecture for implementing various aspects described herein. A bus 204 can serve as the information highway interconnecting the other illustrated components of the hardware. A processing system 208 labeled CPU (central processing unit) (e.g., one or more computer processors/data processors at a given computer or at multiple computers), can perform calculations and logic operations required to execute a program. A non-transitory processor-readable storage medium, such as read only memory (ROM) 212 and random access memory (RAM) 216, can be in communication with the processing system 208 and can include one or more programming instructions for the operations specified here. Optionally, program instructions can be stored on a non-transitory computer-readable storage medium such as a magnetic disk, optical disk, recordable memory device, flash memory, or other physical storage medium.

(85) In one example, a disk controller 248 can interface with one or more optional disk drives to the system bus 204. These disk drives can be external or internal floppy disk drives such as 260, external or internal CD-ROM, CD-R, CD-RW or DVD, or solid state drives such as 252, or external or internal hard drives 256. As indicated previously, these various disk drives 252, 256, 260 and disk controllers are optional devices. The system bus 204 can also include at least one communication port 220 to allow for communication with external devices either physically connected to the computing system or available externally through a wired or wireless network. In some cases, the at least one communication port 220 includes or otherwise comprises a network interface.

(86) To provide for interaction with a user, the subject matter described herein can be implemented on a computing device having a display device 240 (e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor) for displaying information obtained from the bus 204 via a display interface 214 to the user and an input device 232 such as keyboard and/or a pointing device (e.g., a mouse or a trackball) and/or a touchscreen by which the user can provide input to the computer. Other kinds of input devices 232 can be used to provide for interaction with a user as well; for example, feedback provided to the user can be any form of sensory feedback (e.g., visual feedback, auditory feedback by way of a microphone 236, or tactile feedback); and input from the user can be received in any form, including acoustic, speech, or tactile input. The input device 232 and the microphone 236 can be coupled to and convey information via the bus 204 by way of an input device interface 228. Other computing devices, such as dedicated servers, can omit one or more of the display 240 and display interface 214, the input device 232, the microphone 236, and input device interface 228.

(87) One or more aspects or features of the subject matter described herein can be realized in digital electronic circuitry, integrated circuitry, specially designed application specific integrated circuits (ASICs), field programmable gate arrays (FPGAs) computer hardware, firmware, software, and/or combinations thereof. These various aspects or features can include implementation in one or more computer programs that are executable and/or interpretable on a programmable system including at least one programmable processor, which can be special or general purpose, coupled to receive data and instructions from, and to transmit data and instructions to, a storage system, at least one input device, and at least one output device. The programmable system or computing system may include clients and servers. A client and server are generally remote from each other and typically interact through a communication network. The relationship of client and server arises by virtue of computer programs running on the respective computers and having a client-server relationship to each other.

(88) These computer programs, which can also be referred to as programs, software, software applications, applications, components, or code, include machine instructions for a programmable processor, and can be implemented in a high-level procedural language, an object-oriented programming language, a functional programming language, a logical programming language, and/or in assembly/machine language. As used herein, the term “machine-readable medium” refers to any computer program product, apparatus and/or device, such as for example magnetic discs, optical disks, memory, and Programmable Logic Devices (PLDs), used to provide machine instructions and/or data to a programmable processor, including a machine-readable medium that receives machine instructions as a machine-readable signal. The term “machine-readable signal” refers to any signal used to provide machine instructions and/or data to a programmable processor. The machine-readable medium can store such machine instructions non-transitorily, such as for example as would a non-transient solid-state memory or a magnetic hard drive or any equivalent storage medium. The machine-readable medium can alternatively or additionally store such machine instructions in a transient manner, such as for example as would a processor cache or other random access memory associated with one or more physical processor cores.

(89) To provide for interaction with a user, the subject matter described herein may be implemented on a computer having a display device (e.g., a CRT (cathode ray tube) or LCD (liquid crystal display) monitor) for displaying information to the user and a keyboard and a pointing device (e.g., a mouse or a trackball) and/or a touch screen by which the user may provide input to the computer. Other kinds of devices may be used to provide for interaction with a user as well; for example, feedback provided to the user may be any form of sensory feedback (e.g., visual feedback, auditory feedback, or tactile feedback); and input from the user may be received in any form, including acoustic, speech, or tactile input.

(90) In the descriptions above and in the claims, phrases such as “at least one of” or “one or more of” may occur followed by a conjunctive list of elements or features. The term “and/or” may also occur in a list of two or more elements or features. Unless otherwise implicitly or explicitly contradicted by the context in which it is used, such a phrase is intended to mean any of the listed elements or features individually or any of the recited elements or features in combination with any of the other recited elements or features. For example, the phrases “at least one of A and B;” “one or more of A and B;” and “A and/or B” are each intended to mean “A alone, B alone, or A and B together.” A similar interpretation is also intended for lists including three or more items. For example, the phrases “at least one of A, B, and C;” “one or more of A, B, and C;” and “A, B, and/or C” are each intended to mean “A alone, B alone, C alone, A and B together, A and C together, B and C together, or A and B and C together.” In addition, use of the term “based on,” above and in the claims is intended to mean, “based at least in part on,” such that an unrecited feature or element is also permissible.

(91) The subject matter described herein can be embodied in systems, apparatus, methods, and/or articles depending on the desired configuration. The implementations set forth in the foregoing description do not represent all implementations consistent with the subject matter described herein. Instead, they are merely some examples consistent with aspects related to the described subject matter. Although a few variations have been described in detail above, other modifications or additions are possible. In particular, further features and/or variations can be provided in addition to those set forth herein. For example, the implementations described above can be directed to various combinations and subcombinations of the disclosed features and/or combinations and subcombinations of several further features disclosed above. In addition, the logic flows depicted in the accompanying figures and/or described herein do not necessarily require the particular order shown, or sequential order, to achieve desirable results. Other implementations may be within the scope of the following claims.