Anselme Tueno
email: anselme.kemgne.tueno@sap.com

Yordan Boev

Florian Kerschbaum

Non-interactive Private Decision Tree Evaluation

Keywords: Machine Learning, Private Decision Tree Evaluation, Secure Multiparty Computation, Fully/Somewhat Homomorphic Encryption

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Machine learning (ML) classifiers are valuable tools in many areas such as healthcare, finance, spam filtering, intrusion detection, remote diagnosis, etc. [START_REF] Witten | Data Mining: Practical Machine Learning Tools and Techniques[END_REF]. To perform their task, these classifiers often require access to personal sensitive data such as medical or financial records. Therefore, it is crucial to investigate technologies that preserve the privacy of the data, while benefiting from the advantages of ML. On the one hand, the ML model itself may contain sensitive data. On the other hand, the model may have been built on sensitive data. It is known that white-box and sometimes even black-box access to a ML model allows so-called model inversion attacks [START_REF] Fredrikson | Model inversion attacks that exploit confidence information and basic countermeasures[END_REF][START_REF] Tramèr | Stealing machine learning models via prediction apis[END_REF][START_REF] Wu | A methodology for formalizing model-inversion attacks[END_REF], which can compromise the privacy of the training data. As a result, making the ML model public could violate the privacy of the training data.

In this paper, we therefore address the problem of private decision tree evaluation (PDTE) on private data. This scenario consists of a server holding a private decision tree model and a client wanting to classify its 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. The problem can be solved using any generic secure multiparty computation.

Generic secure multiparty computation [START_REF] Damgård | Multiparty computation from somewhat homomorphic encryption[END_REF][START_REF] Goldreich | Foundations of Cryptography: Volume 2, Basic Applications[END_REF] can implement PDTE. There exist frameworks such as ObliVM [START_REF] Liu | Oblivm: A programming framework for secure computation[END_REF] or CBMC-GC [START_REF] Franz | CBMC-GC: an ANSI C compiler for secure two-party computations[END_REF], HyCC [START_REF] Büscher | Hycc: Compilation of hybrid protocols for practical secure computation[END_REF] that are able to automate the transformation of the plaintext decision tree program, written in a high level programming language, into oblivious programs suitable for secure computation. Their straightforward application to decision tree programs does certainly improve performance. However, the size of the resulting oblivious program is still proportional to the size of the tree. As a result generic solution are in general inefficient, in particular when the size of the tree is large.

Specialized protocols [START_REF] Barni | Secure evaluation of private linear branching programs with medical applications[END_REF][START_REF] Bost | Machine learning classification over encrypted data[END_REF][START_REF] Brickell | Privacy-preserving remote diagnostics[END_REF][START_REF] Joye | Private yet efficient decision tree evaluation[END_REF][START_REF] Kiss | Sok: Modular and efficient private decision tree evaluation[END_REF][START_REF] Tai | Privacy-preserving decision trees evaluation via linear functions[END_REF][START_REF] Tueno | Private evaluation of decision trees using sublinear cost[END_REF][START_REF] Wu | Privately evaluating decision trees and random forests[END_REF] exploit the domain knowledge of the problem at hand and make use of generic techniques only where it is necessary, resulting in more efficient solutions. Existing protocols for PDTE have several rounds requiring several interactions between the client and the server. Moreover, the communication cost depends on the size of the decision tree, while only a single classification is required by the client. Finally, they also require computational power from the client that depends on the size of the tree.

Our goal is to design and implement a novel client-server protocol that delegates the complete tree evaluation to the server while preserving privacy and keeping the performance acceptable. The idea is to use fully or somewhat homomorphic encryption (FHE/SHE) and evaluate the tree on ciphertexts encrypted under the client's public key. As a result, no intermediate or final computational result is revealed to the evaluating server. However, since current SHE/FHE schemes have high overhead, we combine efficient data representations with different algorithmic optimizations to keep the computational overhead and the communication cost low. At the end, the computational overhead might still be higher than in existing protocols, however the computation task can be parallelized resulting in a reduced computation time. As a result, we are able to provide the first non-interactive protocol, that allows the client to delegate the evaluation to the server by sending an encrypted input and receiving only the encryption of the result. Finally, existing approaches are secure in the semi-honest model (i.e., parties follow the protocol) and can be made one-sided simulatable using techniques that may double the computation and communication costs. A one-sided simulatable protocol forces the client to behave semi-honestly and guarantees that a malicious server learns nothing [START_REF] Hazay | Efficient Secure Two-Party Protocols: Techniques and Constructions[END_REF]. Our approach is one-sided simulatable by default, as the client does no more than encrypting its input and decrypting the final result of the computation (simulating the client is straightforward), while the server evaluates on ciphertexts encrypted with a semantically secure encryption under the client's public key.

Concrete motivation of our approach are machine learning settings (with applications in areas such as healthcare, finance etc.) where the server is computationally powerful, the client is computationally weak and the network connection is not very fast. Our contributions are as follows:

-We propose a non-interactive protocol for PDTE. Our scheme allows the client to delegate the evaluation to the server by sending an encrypted input and receiving only the encryption of the result. -We propose Pdt-Bin which is an instantiation of the main protocol with binary representation of the input. We combine efficient data representations with different algorithmic optimizations to keep the computational overhead and the communication cost low. -Finally, we implement and benchmark using HElib [START_REF] Halevi | Algorithms in helib[END_REF] and TFHE [START_REF] Chillotti | TFHE: Fast fully homomorphic encryption library[END_REF].

The remainder of the paper is structured as follows. We review preliminaries in Section 2 before defining correctness and security of our protocol in Section 3. The basic construction itself is described in Section 4. In Section 5, we describe implementation and optimization using a binary representation. We discuss implementation and evaluation details in Section 6. We review related work in Section 7 before concluding our work in Section 8. Due to space constraints, we discuss further details in the appendix.

Preliminaries

For ease of exposition, we abstract away the mathematical technicalities behind HE and refer to the literature [START_REF] Albrecht | Homomorphic encryption security standard[END_REF][START_REF] Brakerski | Fully homomorphic encryption without bootstrapping[END_REF][START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF][START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF][START_REF] Smart | Fully homomorphic simd operations[END_REF]. We start with the notation. Notation. In this paper, µ denotes the bit length of attribute values, n denotes the dimension of the attribute vector, m denotes the number of decision nodes, d denotes the depth of the decision tree. Homomorphic Encryption. We focus on (lattice-based) homomorphic encryption (HE) schemes that allow many chained additions and multiplications to be computed on plaintext. In these schemes, the plaintext space is usually a ring Z q [X] (X N + 1), where q is prime and N might be a power of 2.

A HE consists of the usual algorithms for key generation (pk, sk) ← KGen(λ), encryption Enc(pk, m) (we denote Enc(pk, m) by ⟦m⟧), decryption Dec(sk, c). HE has an additional evaluation algorithm Eval(pk, f, c 1 , . . . , c n ) that takes pk, an nary function f and ciphertexts c 1 , . . . c n . It outputs a ciphertext c such that if c i = ⟦m i ⟧ then it holds: Dec(sk, Eval(f, ⟦m 1 ⟧, . . . , ⟦m n ⟧)) = Dec(sk, ⟦f (m 1 , . . . , m n )⟧). We require HE to be IND-CPA secure.

The encryption algorithm Enc adds 'noise' to the ciphertext which increases during homomorphic evaluation. While addition of ciphertexts increases the noise slightly, the multiplication increases it significantly [START_REF] Brakerski | Fully homomorphic encryption without bootstrapping[END_REF]. 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 f low enough or use bootstrapping procedure which reduces the noise in a ciphertext, i.e., fully HE (FHE). In this paper, we will consider both bootstrapping and the possibility of keeping the circuit's depth low by designing our PDTE using so-called leveled FHE. A leveled FHE has an extra parameter L such that the scheme can evaluate all circuits of depth at most L without bootstrapping. Homomorphic Operations. We assume a BGV type HE scheme [START_REF] Brakerski | Fully homomorphic encryption without bootstrapping[END_REF]. Plaintexts can be encrypted using an integer representation (an integer x i is encrypted as ⟦x i ⟧) or a binary representation (each bit of the bit representation x b i = x iµ . . . x i1 is encrypted). We describe below HE operations in the binary representation (i.e., arithmetic operations mod 2). They work similarly in the integer representation.

The FHE scheme might support Smart and Vercauteren's ciphertext packing (SVCP) technique [START_REF] Smart | Fully homomorphic simd operations[END_REF] 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. ⟦⋅ ⋅ . . . ⋅⟧. The encryption of a bit b replicates b to all slots, i.e., ⟦b⟧ = ⟦b b . . . b⟧. However, we can also pack the bits of x b i in one ciphertext and will denote it by ⟦⃗ x i ⟧ = ⟦x iµ . . . x i1 0 . . . 0⟧.

The computation relies on some built-in routines, that allow homomorphic operations on encrypted data. The relevant routines for our 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).

The routine SheAdd performs a component-wise addition modulo two, i. Let

x i , x j be two integers, b ij = [x i > x j ], b ji = [x j > x i ],
the routine SheCmp takes ⟦x b i ⟧, ⟦x b j ⟧, compares x i and x j and returns ⟦b ij ⟧, ⟦b ji ⟧: (⟦b ij ⟧, ⟦b ji ⟧) ← SheCmp(⟦x b i ⟧, ⟦x b j ⟧). 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 [START_REF] Cheon | Search-and-compute on encrypted data[END_REF].

If ciphertext packing is enabled, then we also assume that HE supports shift operations. Given a packed ciphertext ⟦b 1 . . . b s ⟧, the shift left operation shifts all slots to the left by a given offset, using zero-fill, i.e., shifting ⟦b 1 . . . b s ⟧ by i positions returns ⟦b i . . . b s 0 . . . 0⟧.

Definitions

This section introduces relevant definitions. With [a, b], we denote the set of all integers from a to b. Let c 0 , . . . , c k-1 be the classification labels, k ∈ N >0 .

Definition 1 (Decision Tree). A decision tree (DT) is a function T ∶ Z n → {c 0 , . . . , c k-1 } that maps an attribute vector x = (x 0 , . . . , x n-1 ) to a finite set of classification labels. A DT consists of internal or decision nodes containing a test condition, and leaf nodes containing a classification label. A decision tree model consists of a DT and the following functions: a function thr that assigns to each decision node a threshold value, thr ∶ [0, m -1] → Z; a function att that assigns to each decision node an attribute index, att ∶ [0, m-1] → [0, n-1], and; a labeling function lab that assigns to each leaf node a label, lab ∶ [m, M -1] → {c 0 , . . . , c k-1 }. 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 att(v) ≥ thr(v)]. We use M = (T , thr, att) to denote a decision tree model. Definition 2 (Decision Tree Evaluation). Given an attribute vector x = (x 0 , . . . , x n-1 ) and M = (T , thr, att), then starting at the root, the Decision Tree Evaluation (DTE) evaluates at each reached node v the decision b ← [x 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. We denote this by T (x).

Definition 3 (Private DTE). Given a client with a private x = (x 0 , . . . , x n-1 ) and a server with a private M = (T , thr, att), a private DTE (PDTE) functionality evaluates the model M on input x, then reveals to the client the classification label T (x) and nothing else, while the server learns nothing, i.e.,

F PDTE (M, x) → (ε, T (x)).
Definition 4 (Correctness). Given a client with a private x = (x 0 , . . . , x n-1 ) and a server with a private M = (T , thr, att), a protocol Π correctly implements a PDTE functionality if after the computation it holds for the result c obtained by the client that c = T (x).

Two distributions D 1 and D 2 are computationally indistinguishable (denoted D 1 c ≡ D 2 ) if no probabilistic polynomial time (PPT) algorithm can distinguish them except with negligible probability. 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 [START_REF] Goldreich | Foundations of Cryptography: Volume 2, Basic Applications[END_REF].

Definition 5 (PDTE Security). Given a client C with a private input x = (x 0 , . . . , x n-1 ) and a server S with a private model M = (T , thr, att), a protocol Π PDTE securely implements the PDTE functionality in the semi-honest model if the following holds: there exists a PPT algorithm Sim pdte

The Basic Protocol

We present a modular description of our protocol starting by the data structure.

Data Structure

We follow the idea of previous protocols [START_REF] Bost | Machine learning classification over encrypted data[END_REF][START_REF] Cock | Efficient and private scoring of decision trees, support vector machines and logistic regression models based on pre-computation[END_REF][START_REF] Tai | Privacy-preserving decision trees evaluation via linear functions[END_REF] of marking edges of the tree with comparison result. So if the comparison at node v is the bit b then we mark the right edge to v with b and the left edge with 1 -b. For convenience, we will instead store this information at the child nodes of v and refer to it as cmp.

Definition 6 (Data Structure). For a decision tree model M = (T , thr, att), we let Node be a data structure that for each node v defines the following fields: v.threshold stores the threshold thr(v) of v; v.aIndex stores the associated index att(v); v.parent stores the pointer to the parent node (null for the root); v.left stores the pointer to the left child node (null for each leaf ); v.right stores the pointer to the right child node (null for each leaf ); v.cmp is computed during the tree evaluation and stores the comparison bit b ← [x att(v.parent) ≥ thr(v.parent)] if v is a right node. Otherwise it stores 1 -b; v.cLabel stores the classification label if v is a leaf node and the empty string otherwise. We use D to denote the set of all decision nodes and L the set of all leaf nodes of M. As a result, we use the equivalent notation M = (T , thr, att) = (D, L).

With the data structure defined above, we now define the classification function.

Definition 7 (Classification Function). Let x = (x 0 , . . . , x n-1 ) be the attribute vector and M = (D, L) be the DT model. We define the classification function to be f c (x, M) = tr(x, root), where root is the root node and tr is the traverse function define as: Proof. The proof follows by induction on the depth of the tree. In the base case, we have a tree of depth one (i.e., the root and two leaves). In the induction step, we have two trees of depth d and we joint them by adding a new root.

tr(x, v) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ tr(x, v.left) if v ∈ D and x v.aIndex < v.threshold tr(x, v.right) if v ∈ D and x v.aIndex ≥ v.threshold v if v ∈ L Lemma 1. Let x = (x 0 , . . . , x n-1 )

Algorithms

Initialization. The Initialization consists of a one-time key generation. The client generates appropriate pair (pk, sk) of public and private keys for a HE scheme, and sends pk to the server. For each input classification, the client just

Q.enqueue(v.right)
Algorithm 1: Aggregating Decision Bits encrypts its input and sends it to the server. The size of homomorphic ciphertexts are in general very large. 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 [START_REF] Beaver | Commodity-based cryptography[END_REF] 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. We refer to this algorithm as EvalDnode(D, ⟦x⟧). Aggregating Decision Bits. Then for each leaf node v, the server aggregates the comparison bits along the path from the root to v. We implement it using a queue and traversing the tree in BFS as illustrated in Algorithm 1.

Computing Decision Bits

Finalizing. After Aggregating the decision bits along the path to the leaf nodes, each leaf node v stores either v.cmp = 0 or v.cmp = 1. Then, the server aggregates the decision bits at the leaves by computing for each leaf v the value ⟦v.cmp⟧ ⊡ ⟦v.cLabel⟧ and summing all the results. We refer to this algorithm as Finalize(L).

Putting It All Together. As illustrated in Protocol 2, the whole computation is performed by the server. It sequentially computes the algorithms described above and sends the resulting ciphertext to the client. The client decrypts and outputs the classification label. The correctness follows from Lemma 1.

Binary Implementation

In this section, we describe Pdt-Bin, an instantiation of the basic scheme that requires encoding the plaintexts using their bit representation. Hence, ciphertexts encrypt bits and arithmetic operations are done mod 2.

Input Encoding

We encrypt plaintext bitwise. For each plaintext x i with bit representation

x b i = x iµ . . . x i1 ,
EvalPaths(D, L) ⟦T (x)⟧ ← Finalize(L) ⟦T (x)⟧
Protocol 2: The Basic Protocol of encryptions of the bits of x i . As a result, the client needs to send nµ ciphertexts for the n attribute values. Unfortunately, homomorphic ciphertexts might be quite large. We can already use the trusted randomizer as explained before to send blinded inputs instead of ciphertexts in this phase. This, however, improves only the online communication. We additionally want to use the SVCP SIMD technique that allows to pack many plaintexts into the same ciphertext and manipulate them together during homomorphic operations.

Ciphertext Packing

In the binary encoding, 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 the bit representation of each classification label in a single ciphertext and allow the server to send back a single ciphertext to the client. 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 DT model.

Packing Classification Label's Bits. Aggregating the decision bits using Algorithm 1 produces for each leaf v ∈ L a decision bit ⟦b v ⟧ which encrypts 1 for the classification leaf and 0 otherwise. Moreover, because of SVCP, the bit b v is replicated to all slots. Now, let k be the number of classification labels (i.e., L = k) and its bitlength be k . in the correct classification label. Note that, this assumes that one is classifying only one vector and not many as in the the next case.

Packing Attribute Values. Let x (1) , . . . , x (s) be s possible attribute vectors with

x (l) = [x (l) 1 , . . . , x (l) n ], 1 ≤ l ≤ s. For each x (l) i , let x (l) b i = x (l) iµ , . . . , x (l)
i1 be the bit representation. Then, the client generates for each attribute x i the ciphertexts ⟦cx iµ ⟧, . . . , ⟦cx i2 ⟧, ⟦cx i1 ⟧ as illustrated in Figure 3a.

To shorten the notation, let y j denote the threshold of the j-th decision node (i.e., y j = v j .threshold) and assume v j .aIndex = i. The server just encrypts each threshold bitwise which automatically replicates the bit to all slots. This is illustrated in Figure 3b.

Note that (⟦cy jµ ⟧, . . . , ⟦cy j1 ⟧) = ⟦y b j ⟧ holds because of SVCP. The above described encoding allows to compare s attribute values together with one threshold. This is possible because the routine SheCmp is compatible with SVCP such that we have: SheCmp((⟦cx iµ ⟧, . . . , ⟦cx i1 ⟧), ⟦y b j ⟧) = (⟦b

(1) ij . . . b (s) ij ⟧, ⟦b (1)
v = c v k . . . c v1 .
To select the correct classification label algorithm Finalize(L) is updated as follows. We compute ⟦c v k ⟧ ⊡ ⟦b v ⟧, . . . , ⟦c v1 ⟧ ⊡ ⟦b v ⟧ for each leaf v ∈ L and sum them componentwise over all leaves. This results in the encrypted bit representation of the correct classification labels. Packing Threshold Values. In this case, the client encrypts a single attribute in one ciphertext, while the server encrypts multiple threshold values in a single ciphertext. Hence, for an attribute value x i , the client generates the ciphertexts similar to in Figure 3a. Let m i be the number of decision nodes that compare to the attribute x i (i.e., m i = {v j ∈ D ∶ v j .aIndex = i} ). The server packs all corresponding threshold values in ⌈ mi s ⌉ ciphertext(s). The packing of threshold values allows to compare one attribute value against multiple threshold values together. Unfortunately, we do not have access to the slots while performing homomorphic operation. Hence, to aggregate the decision bits, we make m i copies of the resulting packed decision bits and shift left each decision bit to the first slot. Then the aggregation of the decision bits 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 can be set to 0.

Efficient Path Evaluation

Homomorphic multiplication increases the noise significantly [START_REF] Brakerski | Fully homomorphic encryption without bootstrapping[END_REF]. To evaluate paths, we need to keep the multiplication depth small. Definition 8 (Multiplicative Depth). Let f be a function, C f be a boolean circuit that computes f and consists of AN D-gates or multiplication (modulo 2) gates and XOR-gates or addition (modulo 2) gates. The circuit depth of C f is the maximal length of a path from an input gate to an output gate. The multiplicative depth of C f is the path from an input gate to an output gate with the largest number of of multiplication gates.

Path evaluation requires to homomorphically compute f ([a 1 , . . . , a n ]) = Π n i=1 a i , where the a i are comparison results on the path.

Lemma 2 (Logarithmic Multiplicative Depth). Let [a 1 , . . . , a n ] be an array of n integers and f be the function:

f ([a 1 , . . . , a n ]) = [a ′ 1 , . . . a ′ ⌈ n 2 ⌉ ],
where

a ′ i = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ a 2i-1 ⋅ a 2i if (n mod 2 = 0) ∨ (i < ⌈ n 2 ⌉), a n if (n mod 2 = 1) ∧ (i = ⌈ n 2 ⌉).
Moreover, let f be an iterated function where f i is the i-th iterate defined as:

f i ([a 1 , . . . , a n ]) = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ [a 1 , . . . , a n ] if i = 0, f (f i-1 ([a 1 , . . . , a n ])) if i ≥ 1.
The n -th iterate f n of f computes Π n i=1 a i and has multiplicative depth n -1 if n is a power of two and n otherwise, where n = log n is the bitlength of n:

f n ([a 1 , . . . , a n ]) = [Π n i=1 a i ].
Due to space constraints, we provide the algorithm for path evaluation with multiplicative depth in the Appendix (Algorithm 6). This algorithm consists of a main function EvalPathsE that collects for each leaf v encrypted comparison results on the path from the root to v, and a sub-function EvalMul which multiplies comparison results according to Lemma 2.

Although highly parallelizable, EvalPathsE is still not optimal, as each path is considered individually. Since multiple paths in a binary tree share a common prefix (from the root), one would ideally want to handle common prefixes one time and not many times for each leaf. This can be solved using memoization technique which is an optimization that stores results of expensive function calls such that they can be used latter if needed. Unfortunately, naive memoization would require a complex synchronization in a multi-threaded environment and linear multiplicative depth. The next section describes a pre-computation on the tree, that would allow us to have the best of both worlds -multiplication with logarithmic depth along the paths, while reusing the result of common prefixes.

Improving Path Evaluation with Pre-Computation

The idea behind this optimization is to use directed acyclic graph which we want to define first.

Definition 9 (DAG).

A directed acyclic graph (DAG) is a graph with directed edges in which there are no cycles. A vertex v of a DAG is said to be reachable from another vertex u if there exists a non-trivial path that starts at u and ends at v. The reachability relationship is a partial order ≤ and we say that two vertices u and v are ordered as u ≤ v if there exists a directed path from u to v.

We require our DAGs to have a unique maximum element. The edges in the DAG define dependency relation between vertices.

Definition 10 (Dependency Graph). Let h be the function that takes two

DAGs G 1 , G 2 and returns a DAG G 3 that connects the maxima of G 1 and G 2 . We define the function g([a 1 , . . . , a n ]) that takes an array of integers and returns:

a graph with a single vertex labeled with a

1 if n = 1 -h(g([a 1 , . . . , a n ′ ]), g([a n ′ +1 , . . . , a n ])) if n > 1 holds, where n ′ = 2 n -1 and n
denotes the bitlength of n.

We call the DAG G generated by G = g([a 1 , . . . , a n ]) a dependency graph.

For each edge (a i , a j ) in G such that i < j, we say that a j depends on a i and denote this by adding a i in the dependency list of a j . We require that if L(j) = [a i1 , . . . , a i L(j) ] is the dependency list of a j then it holds i 1 > i 2 > . . . i L(j) .

An example of dependency graph generated by the function g([a 1 , . . . , a n ]) is illustrated in Figure 4a for n = 4 and n = 5.

Lemma 3. Let [a 1 , . . . , a n ] be an array of n integers. Then g([a 1 , . . . , a n ]) as defined above generates a DAG whose maximum element is marked with a n .

Lemma 4. Let [a 1 , . . . , a n ] be an array of n integers, G = g([a 1 , . . . , a n ]) be a DAG as above, and L(j) = [a i1 , . . . , a i L(j) ] be the dependency list of a j . Then the algorithm in Figure 4b computes Π n i=1 a i with a multiplicative depth of log(n).

The proofs of Lemmas 3 and 4 follow by induction similar to Lemma 2. Before describing the improved path evaluation algorithm, we first extend our Node data structure by adding to it a new field representing a stack denoted dag, that stores the dependency list. Moreover, we group the nodes of the DT by level and use an array denoted level[], such that level[0] stores a pointer to the root and level[i] stores pointers to the child nodes of level[i -1] for i ≥ 1. Now, we are ready to describe the improved path evaluation algorithm which consists of a pre-computation step and an online step.

The pre-computation is a one-time computation that depends only on the structure of the DT and requires no encryption. As described in Algorithm 7, its main function ComputeDag uses the leveled structure of the tree and the dependency graph defined above to compute the dependency list of each node in the tree (i.e., the DAG defined above). The sub-function AddEdge is used to actually add nodes to the dependency list of another node (i.e., by adding edges between these nodes in the DAG).

The online step is described in Algorithm 8. It follows the idea of the algorithm in Figure 4b by multiplying decision bit level-wise depending on the dependency lists. The correctness follows from Lemma 4.

Evaluation

In this section, we discuss some implementation details and evaluate our schemes.

Implementation Details

We implemented our algorithms using HElib [START_REF] Halevi | Algorithms in helib[END_REF] and TFHE [START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF][START_REF] Chillotti | TFHE: Fast fully homomorphic encryption library[END_REF]. We also implemented the main algorithm using an arithmetic circuit based on Lin-Tzeng comparison protocol [START_REF] Lin | An efficient solution to the millionaires' problem based on homomorphic encryption[END_REF][START_REF] Tueno | Secure computation of the kth-ranked element in a star network[END_REF]. We refer to this implementation as Pdt-Int. HElib is a C++ library that implements FHE. The current version includes an implementation of the BGV scheme [START_REF] Brakerski | Fully homomorphic encryption without bootstrapping[END_REF]. HElib also includes various optimizations that make FHE runs faster, including ciphertext packing (SVCP) techniques [START_REF] Smart | Fully homomorphic simd operations[END_REF].

TFHE is a C/C++ library that implements FHE proposed by Chillotti et al. [START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF]. It allows to evaluate any boolean circuit on encrypted data. The current version implements a very fast gate-by-gate bootstrapping, i.e., bootstrapping is performed after each gate evaluation. Future versions will include leveled FHE and ciphertext packing Chillotti et al. [START_REF] Chillotti | TFHE: fast fully homomorphic encryption over the torus[END_REF]. Dai and Sunar [START_REF] Dai | cuhe: A homomorphic encryption accelerator library[END_REF][START_REF] Dai | Cuda-accelerated fully homomorphic encryption library (August 2019[END_REF] propose an implementation of TFHE on CUDA-enabled GPUs that is 26 times faster. We evaluated our scheme on an AWS instance with Intel(R) Xeon(R) Platinum 8124M CPU @ 3.00GHz running Ubuntu 18.04.2 LTS; with 36 CPUs, 144 GB Memory and 8 GB SSD. As the bottleneck of our scheme is the overhead of the HE, we focus on the computation done by the server. We describe HE parameters and the performance of basic operations in Appendix A.

Performance of Pdt-Bin

In this section, we report on our experiment with Pdt-Bin on complete trees. Recall that for FHE supporting SIMD, we can use attribute values packing that allows to evaluate many attribute vectors together. We, therefore, focus on attribute packing to show the advantage of SIMD. Figure 5a illustrates the amortized runtime of Pdt-Bin with HElib. That is, the time of one PDTE evaluation divided by the number of slots in a ciphertext. As one can expect, the runtime clearly depends on the bitlength of the attribute values and the depth of the tree. The results show a clear advantage of HElib when classifying large data sets. For paths aggregation, we proposed EvalPathsE (Algorithm 6) and EvalPathsP (Algorithm 8). Figure 5b illustrates Pdt-Bin runtime using these algorithms in a multi-threaded environment and shows a clear advantage of EvalPathsP which will be used in the remaining experiments with Pdt-Bin. Figure 5c illustrates the runtime of Pdt-Bin with HElib med showing that the computation cost is dominated by the computation of decision bits which involves homomorphic evaluation of comparison circuits. In Figure 5d, we report the evaluation of Pdt-Bin using TFHE, which shows a clear advantage compared to HElib. For the same experiment with 72 threads, TFHE evaluates a complete tree of depth 10 and 64-bit input in less than 80 seconds, while HElib takes about 400 seconds for 16-bit input. Recall that, a CUDA implementation [START_REF] Dai | cuhe: A homomorphic encryption accelerator library[END_REF][START_REF] Dai | Cuda-accelerated fully homomorphic encryption library (August 2019[END_REF] of TFHE can further improve the time of Pdt-Bin using TFHE.

Performance on Real Datasets

We also performed experiments on real datasets from the UCI repository [START_REF]Uci repository[END_REF].

For Pdt-Bin, we reported the costs for HElib (single and amortized) and the costs for TFHE. Since TFHE evaluates only boolean circuits, we only have implementation and evaluation of Pdt-Int with HElib. We also illustrate in Table 1 the costs of two best previous works that rely only on HE, whereby the figures are taken from the respective papers [START_REF] Lu | Non-interactive and output expressive private comparison from homomorphic encryption[END_REF][START_REF] Tai | Privacy-preserving decision trees evaluation via linear functions[END_REF]. For one protocol run, Pdt-Bin with TFHE is much more faster than Pdt-Bin with HElib which is also faster than Pdt-Int with HElib. However, because of the large number of slots, the amortized cost of Pdt-Bin with HElib is better. For 16-bit inputs, our amortized time with HElib and our time with TFHE outperform XCMP [START_REF] Lu | Non-interactive and output expressive private comparison from homomorphic encryption[END_REF] which used 12-bit inputs. For the same input bitlength, XCMP is still much more better than our one run using HElib, since the multiplicative depth is just 3. However, our schemes still have a better communication and Pdt-Bin has no leakage. While the scheme of Tai et al. [START_REF] Tai | Privacy-preserving decision trees evaluation via linear functions[END_REF] in the semi-honest model has a better time for 64-bit inputs than our schemes for 16-bit inputs, it requires a fast network communication and at least double cost in the malicious model. The efficiency of Tai et al. is in part due to their ECC implementation of the lifted ElGamal, which allows a fast runtime and smaller ciphertexts, but is not secure against a quantum attacker, unlike lattice-based FHE as used in our schemes.

Related Work

Our work is related to secure multiparty computation (SMC) [START_REF] Damgård | Multiparty computation from somewhat homomorphic encryption[END_REF][START_REF] Goldreich | Foundations of Cryptography: Volume 2, Basic Applications[END_REF], private function evaluation (PFE) [START_REF] Kiss | Valiant's universal circuit is practical[END_REF][START_REF] Mohassel | Actively secure private function evaluation[END_REF] particularly privacy-preserving DT evaluation [START_REF] Barni | Secure evaluation of private linear branching programs with medical applications[END_REF][START_REF] Bost | Machine learning classification over encrypted data[END_REF][START_REF] Brickell | Privacy-preserving remote diagnostics[END_REF][START_REF] Joye | Private yet efficient decision tree evaluation[END_REF][START_REF] Kiss | Sok: Modular and efficient private decision tree evaluation[END_REF][START_REF] Tai | Privacy-preserving decision trees evaluation via linear functions[END_REF][START_REF] Tueno | Private evaluation of decision trees using sublinear cost[END_REF][START_REF] Wu | Privately evaluating decision trees and random forests[END_REF] which we briefly review in this section and refer to the literature for more details. Brikell et al. [START_REF] Brickell | Privacy-preserving remote diagnostics[END_REF] propose the first protocol for PDTE by combining additively HE and garbled circuits (GC) in a novel way. Although the evaluation time of Brikell et al.'s scheme is sublinear in the tree size, the secure program itself and hence the communication cost is linear and therefore not efficient for large trees. Barni et al. [START_REF] Barni | Secure evaluation of private linear branching programs with medical applications[END_REF] improve the previous scheme by reducing the computation costs by a constant factor. Bost et al. [START_REF] Bost | Machine learning classification over encrypted data[END_REF] represent the DT as a multivariate polynomial. The parties evaluate this polynomial interactively and encrypted under the client's public key using a fully HE Wu et al. [START_REF] Wu | Privately evaluating decision trees and random forests[END_REF] use different techniques that require only additively HE (AHE). They use the DGK protocol [START_REF] Damgård | Efficient and secure comparison for on-line auctions[END_REF] for comparison and reveal to the server comparison bits encrypted under the client's public key. Tai et al. [START_REF] Tai | Privacy-preserving decision trees evaluation via linear functions[END_REF] use the DGK comparison protocol [START_REF] Damgård | Efficient and secure comparison for on-line auctions[END_REF] and AHE as well, but mark the edges with the comparison results at each node. Tueno et al. [START_REF] Tueno | Private evaluation of decision trees using sublinear cost[END_REF] represent the tree as an array. Then, they traverse the tree interactively and use secure array indexing to select the next node and attribute. Kiss et al. [START_REF] Kiss | Sok: Modular and efficient private decision tree evaluation[END_REF] propose a modular design consisting of the sub-functionalities: selection of attributes, integer comparison, and evaluation of paths. De Cock et al. [START_REF] Cock | Efficient and private scoring of decision trees, support vector machines and logistic regression models based on pre-computation[END_REF] follow the same idea as some previous schemes, but operate in the information theoretic model using secret sharing (SS) based SMC and commodity-based cryptography [START_REF] Beaver | Commodity-based cryptography[END_REF]. Using a polynomial encoding of the inputs and BGV homomorphic scheme [START_REF] Brakerski | Fully homomorphic encryption without bootstrapping[END_REF], Lu et al. [START_REF] Lu | Non-interactive and output expressive private comparison from homomorphic encryption[END_REF] propose a non-interactive comparison protocol called XCMP which is output expressive (i.e., it preserves additive homomorphism). They implement the scheme of Tai et al. [START_REF] Tai | Privacy-preserving decision trees evaluation via linear functions[END_REF] using XCMP. The resulting PDTE is non-interactive and efficient because of the small multiplicative depth. However, it is not generic, as it primarily works for small inputs and depends explicitly on BGV-type HE scheme. Moreover, it does not support SIMD operations and is no longer output expressive as XCMP. Hence, it cannot be extended to a larger protocol (e.g., random forest [START_REF] Breiman | Random forests[END_REF]) while preserving the non-interactive property. Finally, its output length (i.e., the number of resulted ciphertexts from server computation) is exponential in the depth d of the tree, while the output length of our binary instantiation Pdt-Bin is at most linear in d. A comparison of PDTE protocols is summarized in Tables 2 and3.

A more detailed complexity analysis of our schemes is described in Appendix C.

Conclusion

While almost all existing PDTE protocols require many interaction between the client and the server, we designed and implemented novel client-server protocols that delegate the complete evaluation to the server while preserving privacy and keeping the overhead low.

B Security Analysis

It is straightforward to see that our protocols are secure. There is no interaction with the client during the computation and a semi-honest server sees only IND-CPA ciphertexts. A semi-honest client only learns the encryption of the result. A malicious server can only return a false classification result. This is inherent to PFE where the function (the DT in our case) is an input to the computation. A malicious client can send a too 'noisy' ciphertext, such that after the computation at the server a correct decryption is not possible, leaking some information. This attack works only with level FHE and is easy to deal with, namely the computation of a ciphertext capacity is a public function which the server can use to check the ciphertexts before starting the computation. As Pdt-Bin returns the bit representation of the resulted classification label whose bitlength is public (i.e., the set of possible classification labels is known to the client), there is no leakage beyond the final output. Pdt-Int returns as many ciphertexts as there are leaves and, therefore, leaks the number of decision nodes.

C Complexity analysis

We now analyse the complexity of our schemes. We assume that the decision tree is a complete tree with depth d.

Complexity of Pdt-Bin. The SHE comparison circuit has multiplicative depth µ-1 +1 and requires O (µ ⋅ µ ) multiplications [START_REF] Cheon | Search-and-compute on encrypted data[END_REF]. That is, the evaluation of all decision nodes requires O 2 d µ ⋅ µ multiplications. The path evaluation has a multiplicative depth of d -1 and requires for all 2 d paths O d2 d multiplications. The evaluation of the leaves has a multiplicative depth of 1 and requires in total 2 d multiplications. The total multiplicative depth for Pdt-Bin is, therefore, µ-1 + d-1 +2 ≈ µ + d +2 while the total number of multiplications is O

2 d µ ⋅ µ + d2 d + 2 d ≈ O d2 d .
For the label packing, the bit representation of each classification label is packed in one ciphertext. This hold for the final result as well. As a result, if the tree is complete and all classification labels are distinct, then the server sends ⌈ d s ⌉ ciphertext(s) to client. In practice, however, ⌈ d s ⌉ = 1 holds as d is smaller that the number s of slots.

For threshold packing, the decision bit b v at node v is encrypted as ⟦b v 0 ... 0⟧. By encrypting the classification label c i = c i k ...c i1 as ⟦c i k 0 ... 0⟧, ..., ⟦c i1 0 ... 0⟧, the final result c l will be encrypted similarly such that with extra shifts, we can build the ciphertext ⟦c l k ... c l1 0 ... 0⟧. As a result, the server sends only 1 ciphertext back to the client.

For other cases (e.g., attribute packing, or no packing at all as in the current implementation of TFHE), the bits of a classification label are encrypted separately which holds for the final result as well. As a result the server sends back d ciphertexts to the client.

Complexity of Pdt-Int. The modified Lin-Tzeng comparison circuit has multiplicative µ -1 and requires O (µ -1) multiplications. As a result, the evaluation of all decision node requires O (µ -1)2 d multiplications. In Pdt-Int, the path evaluation does not requires any multiplication. However, the leave evaluation has a multiplicative depth of 1 and requires in total 2 d multiplications. The total multiplicative depth for Pdt-Int is therefore µ -1 + 1 ≈ µ + 1 while the total number of multiplications is O (µ -1)

2 d + 2 d ≈ O 2 d .
For Pdt-Int, it is not possible to aggregate the leaves as in Pdt-Bin. If the client is classifying many inputs, the server must send 2 d ciphertexts back. If the client is classifying only one input, then the server can use shifts to pack the result in ⌈ 2 d s ⌉ ciphertext(s).

  e., we have: SheAdd(⟦b i1 . . . b is ⟧, ⟦b j1 . . . b js ⟧) = ⟦b i1 ⊕ b j1 . . . b is ⊕ b js ⟧. Similarly, SheMult performs component-wise multiplication modulo two, i.e., we have: SheMult(⟦b i1 . . . b is ⟧, ⟦b j1 . . . b js ⟧) = ⟦b i1 ⋅ b j1 . . . b is ⋅ b js ⟧. We will denote addition and multiplication by ⊞ and ⊡, respectively.

S≡

  that simulates the server's view View Π PDTE S given only M = (T , thr, att) , i.e., Sim pdte S (M, ε) x); there exists a PPT algorithm Sim pdte C that simulates the client's view View Π PDTE C given only x and T (x), i.e., Sim pdte C (x, T (x)) c View Π PDTE C (M, x). A protocol Π PDTE securely implements the PDTE functionality with onesided simulation if the following conditions hold: For every pair x, x ′ of different client's inputs, it holds View Π PDTE S (M, x) c ≡ View Π PDTE S (M, x ′ ); and Π PDTE is simulatable against every PPT adversary controlling C.

  be an attribute vector and M = (T , thr, att) = (D, L) a DT model. We have T (x) = b ⋅ tr(x, root.right) + (1 -b) ⋅ tr(x, root.left), where b = [x att(root) ≥ thr(root)] is the comparison at the root node.

.

  The server starts by computing for each node v ∈ D the comparison bit b ← [x att(v) ≥ thr(v)] and stores b at the right child node (v.right.cmp = b) and 1 -b at the left child node (v.left.cmp = 1 -b).

  we use ⟦x b i ⟧ to denote the vector (⟦x iµ ⟧, . . . , ⟦x i1 ⟧), consisting Client Server Input: x Input: M = (D, L) Output: T (x) Output: ε ⟦x⟧ EvalDnode(D, ⟦x⟧)

  For each v ∈ L, we let c v denote the classification label v.cLabel which is k -bit long and has bit representation c b v = c v k . . . c v1 with corresponding packed encryption ⟦ ⃗ c v ⟧ = ⟦c v k . . . c v1 0 . . . 0⟧. As a result, computing ⟦b v ⟧ ⊡ ⟦ ⃗ c v ⟧ for each leaf v ∈ L and summing over all leaves results Packing many xi ⟦cyj1⟧ = ⟦yj1 . . . yj1⟧ . . . ⟦cyjµ⟧ = ⟦yjµ . . . yjµ⟧ (b) Packing yj

Figure 3 :

 3 Figure 3: Packing Attribute Values

>

  y j ] and b (l) ji = [y j > x (l) i ]. This results in a single ciphertext such that the l-th slot contains the comparison result between b (l) ij . Aggregating decision bits remains unchanged as described in Algorithm 1. It results in a packed ciphertext ⟦b v ⟧ = ⟦b (1) v . . . b (s) v ⟧ for each leaf v ∈ L, where b (l) v = 1 if x (l) classifies to leaf v and b (l) u = 0 for all other leaf u ∈ L ∖ {v}. For the classification label c v of a leaf node v ∈ L, let ⟦c b v ⟧ = (⟦c v k ⟧, . . . , ⟦c v1 ⟧) denote the encryption of the bit representation c b

5 1:

 5 DAG for n = 4 and n = for j = 1 to j = n do 2: for l = 1 to l = L(j) do 3: aj ← aj ⋅ ai l (b) Mult. Algorithm

Figure 4 :

 4 Figure 4: DAG Pre-computation and Multiplication Algorithm using DAG

  bit values (8 threads) PDTETFHE 32-bit value (8 threads) PDTETFHE 64-bit values (72 threads) (d) Pdt-Bin Runtime with TFHE

Figure 5 :

 5 Figure 5: Pdt-Bin Runtime

  Input: nodes stored by level in array level Output: Updated v.cmp for each v ∈ L 1: function EvalPathsP 2: for i = 1 to d do ▷ top to bottom level 3: for each v ∈ level[i] do 4: while NOT v.dag.empty() do ▷ stack 5: w ← v.dag.pop() 6: ⟦v.cmp⟧ ← ⟦v.cmp⟧ ⊡ ⟦w.cmp⟧ Algorithm 8: Aggregate Decision Bits with DAG

Table 1 :

 1 Runtime (in seconds) on Real Datasets: λ is the security level. µ is the input bit length. #thd is the number of threads. Column 'one' is the time for one protocol run while 'am.' is the amortized time (e.g., the time for one run divided by s).

			Pdt-Bin	Pdt-Bin	Pdt-Int	[28]	[32]
			(TFHE)	(HElib)	(HElib)	(HElib) (mcl [29])
	λ		128		150	135		128	128
	µ		16		16	16		12	64
	#thd		16		16	16		16	-
		n, d, m	one	am.	one	am.	one	one	one
	Heart-disease 13, 3, 5	0.94 0.05 40.61 0.0073 45.59	0.59	0.25
	Housing	13, 13, 92	6.30 0.35 252.38 0.90 428.23 10.27	1.98
	Spambase	57, 17, 58	3.66 0.24 174.46 0.72 339.60	6.88	1.80
	Artificial	16, 10, 500 22.39 1.81 1303.55 0.75 2207.13 56.37	10.42

Table 2 :

 2 Comparison of PDTE protocols.

	Scheme Rounds	Tools	Commu-Compa-Leakage
				nication	risons
	[7]	≈5	HE+GC	O 2 d		d	m, d
	[2]	≈4	HE+GC	O 2 d		d	m, d
	[4]	≥6	FHE/SHE	O 2 d		m	m
	[38]	6	HE+OT	O 2 d		m	m
	[32]	4	HE	O 2 d		m	m
	[12]	≈9	SS	O 2 d		m	m, d
	[34]	O (d)	GC,OT	O 2 d		d	m, d
			ORAM	O d 2
	[28]	1	FHE/SHE	O 2 d		m	m
	Pdt-Bin 1	FHE/SHE O (1), O (d)	m	-
	Pdt-Int 1		O 2 d s			m
	Scheme SIMD Generic Output-Multiplicative Output
			expressive	Depth	Length
	[28]	no	no	no		3	2 d+1
	Pdt-Bin yes	yes	yes	µ + d + 2	1 or d
	Pdt-Int yes	yes	no	µ + 1	⌈2 d s⌉

Table 3 :

 3 Comparison of 1-round PDTE protocols.

  Our solutions rely on SHE/FHE and evaluate the tree on ciphertexts encrypted under the client's public key. Since current SHE/FHE schemes have high overhead, we combine efficient data representations with different algorithmic optimizations to keep the computational overhead and the communication cost low. Input: Node v, integers currLvl and destLvl Output: Updated v.dag 1: function AddEdge(v, currLvl, destLvl) 2: w ← v 3: while currLvl > destLvl do 4: w ← w.parent 5: currLvl ← currLvl -1 6: v.dag.push(w)

	Input: leaves set L, decision nodes set D	6: w ← v
	Output: Updated v.cmp for each v ∈ L 1: function EvalPathsE(L, D) 2: for each v ∈ L do 3: let d = #nodes on the path (root → v) 4: let path = empty array of length d 5: l ← d	7: while w ≠ root do 8: path[l] ← ⟦w.cmp⟧ 9: l ← l -1 10: w ← w.parent 11: ⟦v.cmp⟧ ← EvalMul(1, d, path) ▷ path to root
	Input: integers from, to; array of nodes path Output: Product of elements in path 1: function EvalMul(from, to, path) 2: if from ≥ to then 3: return path[from]	4: n ← to -from + 1 5: mid ← 2 n-1 -1 + from -1 ▷ n = log 2 (n) 6: ⟦left⟧ ← EvalMul(from, mid, path) 7: ⟦right⟧ ← EvalMul(mid + 1, to, path) 8: return ⟦left⟧ ⊡ ⟦right⟧
	Algorithm 6: Paths Evaluation with log Multiplicative Depth
			▷
			non-deepest leaves
		9: for each v ∈ level[i] ∩ L do
		10:	AddEdge(v, i, mid)
		11: ComputeDag(up, mid)
		12: ComputeDag(mid + 1, low)
			▷ dag is a stack
	Algorithm 7: Pre-computation of Multiplication DAG

Input: integers up and low

Output: Computed v.dag for each v ∈ D ∪ L 1: function ComputeDag(up, low) 2: if up ≥ low then 3: return ▷ end the recursion 4: δ ← lowup + 1 5: mid ← 2 δ-1 -1 -1 + up ▷ δ bitlength of δ 6: for each v ∈ level[low]

do

7: AddEdge(v, low, mid) 8: for i = mid + 1 to low -1 do

A Encryption Parameters and Basic Operations

Recall that FHE schemes -as considered in this paper -are usually defined over a ring Z[X] (X N + 1) and that the encryption scheme might be a leveled FHE with parameter L. For HElib, the parameters N and L determines how to generate encryption keys for a security level λ which is at least 128 in all our experiments. The degree of the ring polynomial in HElib is not necessarily a power of 2. The ring polynomial is chosen among the cyclotomic polynomials. For HElib, we abuse the notation and use N to denote the N -th cyclotomic polynomial. Given the value of L and other parameters, the HElib function FindM(⋅) computes the N -th cyclotomic polynomial, that guarantees a security level at least equal to a given security parameter λ. Table 4 summarizes the parameters we used for key generation and the resulting sizes for encryption keys and ciphertexts. We refer to it as homomorphic context or just context. For HElib, one needs to choose L large enough than the depth of the circuit to be evaluated and then computes an appropriate value for N that ensures a security level at least 128. We experimented with tree different contexts (HElib small , HElib med , HElib big ) for the binary representation used in Pdt-Bin, and HElib int for the integer representation used in Pdt-Int. For TFHE, the default value of N is 1024 and the security level is 128 while L is infinite because of the gate-by-gate bootstrapping. We used the context TFHE 128 to evaluate Pdt-Bin with TFHE. The last two columns of Table 4


Marian Zaki
email: mzaki@hbu.edu

Adam J Lee
email: adamlee@cs.pitt.edu

Panos K Chrysanthis

Effective Access Control in Shared-Operator Multi-tenant Data Stream Management Systems

Keywords: access control, operator networks, stream processing engines

The proliferation of stream-based applications has led to the widespread use of Data Stream Management Systems (DSMSs), which can support the real-time requirements of these applications. DSMSs were developed to efficiently execute continuous queries (CQs) over incoming data. Multiple CQs can be optimized together to form a query network by sharing operators across CQs. DSMSs are also required to enforce access controls over operators according to data providers' policies. In this paper, we propose the first solution to satisfy access control policies at run-time in shared-operator networks in an non-disruptive, efficient manner. Specifically, we propose a new set of low overhead streaming operators, coined as Privacy Switches (PrSs), which are strategically placed in the operator network to dynamically allow or deny the flow of data in certain branches of the network based upon the current state of access control permissions. Our experimental evaluation confirms that our approach introduces low overheads in the shared operator networks while achieving high savings in the overall network performance.

Introduction

Nowadays, an increasing amount of data is produced in the form of high velocity data streams. This has led to the proliferation of stream-based applications such as sensor-based monitoring (surveillance, car traffic, air quality), financial applications (stock markets, fraud detection), and health care applications. At the same time, it has led to the widespread use of Data Stream Management Systems (DSMSs) [START_REF] Abadi | Aurora: A new model and architecture for data stream management[END_REF][START_REF] Abadi | The aurora and borealis stream processing engines[END_REF][START_REF] Cangialosi | The design of the borealis stream processing engine[END_REF][START_REF] Chen | Niagaracq: A scalable continuous query system for internet databases[END_REF][START_REF] Carbone | Apache flink: Stream and batch processing in a single engine[END_REF][START_REF] Liu | D-storm: Dynamic resource-efficient scheduling of stream processing applications[END_REF], developed to efficiently execute continuous queries (CQs) over streaming data to support these classes of applications. DSMSs are also referred to as Stream Processing Engines (SPEs) and stream processing systems.

CQs are stored queries that execute continuously over data streams as data arrives, on the fly. Since CQs are long-running, multiple CQs can be optimized together to form a query (operator) network, in which multiple queries may share one or more physical operators. The intermediate tuples produced by a shared operator are placed in a shared input queue for the downstream operators of the individual queries involved in the sharing. These optimizations increase the throughput of processing multiple CQs simultaneously and minimize the memory usage and computation times.

In DSMSs that host sensitive data, e.g., patient monitoring data, financial data, etc., data providers restrict data accesses via access control policies that describe the conditions under which users are permitted access to specific data streams. Accordingly, the CQs registered by the system users may be granted or denied access to specific data streams during the execution of these queries.

The most commonly used ways of applying access control over operators in query networks enforce access control either before (pre-filtering) or after (post-filtering) the execution of the network [START_REF] Nehme | A security punctuation framework for enforcing access control on streaming data[END_REF]. In both techniques, the fixed placement of the access control filters may considerably limit query performance. Pre-filtering means cutting off the streams in case any of the users lose access, which will affect the input streams feeding into downstream shared-operator networks. Post-filtering on the other hand, causes all operators to execute until the end and then denying access to the query results for the users who lost access. This wastes resources by processing query results that are never accessed.

An alternative solution is to isolate the queries that have temporarily lost access from the rest of the shared-operator network. This requires modifying the shared-operator network at runtime whenever access control changes are encountered. This can cause extensive overheads on the system that can potentially affect the system throughput and overall performance.

Under these challenges, it is vital for DSMSs to satisfy the access control policies at run-time in shared-operator networks in a non-disruptive and efficient manner, reinforcing both the need to share and need to protect design models. To balance these properties, we propose a cost-effective way for shared-operator networks to enforce access control within the network, thereby eliminating the need to perform any changes to the structure of the shared-operator networks in case of intermittent changes in the access control.

Specifically, in this paper we make the following contributions:

-We propose a new set of low overhead streaming operators that we refer to as Privacy Switches (PrSs). These switches dynamically allow or deny the flow of data streams in shared-operator networks based upon the current state of the access control permissions. Accordingly, certain branches of the query operator networks can be halted and spared execution to accommodate intermittent loss of access to different users. -We propose a placement algorithm to identify the best placement points for PrSs in an optimized shared-operator network. The strategic placement of the switches ensures seamless execution of CQs and reduces overheads in the networks while honoring all changes in access permissions. -We experimentally evaluate our approach by generating shared-operator networks with a controlled set of generation rules and input parameters. Our experiments show that PrSs introduce low overheads in shared-operator networks and achieving high savings in overall network performance.

The remainder of the paper is organized as follows. Section 3 describes prior work on access control in DSMSs and introduces the concept of security punctuations. Section 4 presents our system model, assumptions, and preliminaries. Section 5 describes our proposed approach, which is evaluated in Section 6. Section 7 concludes the paper.

Motivating Example

In the smart healthcare industry [START_REF] Kim | Privacy-preserving aggregation of personal health data streams[END_REF][START_REF] Chen | Stream query processing for healthcare bio-sensor applications[END_REF], wearable smart devices are equipped with various bio sensors that are used to measure and monitor diverse health data of individuals such as blood glucose levels, blood pressure, oxygen saturation, heart rate, etc. This data makes it possible for different health care applications to continuously query these data stream and provide an alarm service, notifying in the risk of health issues based on individual activities of daily living.

Even though a large collection of health data is a valuable asset to the smart healthcare field, serious concerns of data privacy are being raised. That is, indiscriminate collection of personal health data can cause significant privacy issues. Hence, most users do not agree to their health data being collected for the purposes of data analysis which presents a major obstacle for the development of smart healthcare services.

The following listing demonstrates three different data streams and Figure 1 illustrates two example CQs that can be used in smart healthcare applications. When executing these CQs in DSMSs, the queries optimizer will be able to identify the common sub-expressions (both SELECT timestamps within the same interval and have the same JOIN conditions on the input streams) found in the queries and accordingly construct a shared-operator network as shown in the same for all three data streams. Furthermore, in the figure, the highlighted vertices are annotated as "common-prefix" operators since those are the shared operators between both queries CQ 1 and CQ 2 (i.e., the output of these operators feed into two different operators belonging to the two queries).

Related Work

Prior work on access control enforcement in DSMSs can be divided into two different categories: cryptographic solutions and non-cryptographic solutions. Cryptographic solutions such as those presented in Streamforce [START_REF] Anh | Streamforce: Outsourcing access control enforcement for stream data to the clouds[END_REF], utilize Attribute-Based Encryption (ABE) to enforce access control which requires the data provider to be directly involved in the querying process. PolyStream [START_REF] Thoma | Polystream: Cryptographically enforced access controls for outsourced data stream processing[END_REF] allows untrusted third-party infrastructure to compute on encrypted data, allowing innetwork query processing and access control enforcement. PolyStream uses a combination of security punctuations, ABE, and hybrid cryptography to enable flexible (ABAC) access control policy management. Sanctuary [START_REF] Thoma | Behind enemy lines: Exploring trusted data stream processing on untrusted systems[END_REF] uses Intels SGX as a trusted computing base for executing streaming operations on untrusted cloud providers. Non-cryptographic solutions such as those presented by Carminati et al. [START_REF] Carminati | Specifying access control policies on data streams[END_REF][START_REF] Carminati | Enforcing access control over data streams[END_REF], provide access control via enforcing Role Based Access Control (RBAC) and replacing the operators with secure versions which determine whether a client can access a stream by referencing an RBAC policy. Lindner et al. [START_REF] Lindner | Securing the borealis data stream engine[END_REF] utilize limited disclosure by using filtering operators and applying them to the stream query processing results to filter the output based on relevant access control policies. Ng et al. [START_REF] Ng | Privacy preservation in streaming data collection[END_REF] also use the principles of limited disclosure to limit who can access and operate on data streams, requiring queries to be rewritten to match the level at which they can access the data.

Most non-cryptographic solutions require changing the underlying DSMS either by modifying the traditional operators to become security aware or by rewriting the queries, and therefore they are not globally applicable. Limited disclosure applies basic filtering to the query outputs which means that query operators execute at all times regardless of whether the output is used or not.

Unfortunately, all the cryptographic and non-cryptographic solutions that have been proposed to maintain privacy through access control focused mainly on independently executing queries. There has been no research to date that allows access control policies on the input data streams and queries to be applied over shared-operator networks to maintain both privacy and high performance. Our proposed privacy switches approach is the first work in this context.

Preliminaries and System Model

In this section we will introduce our system model, assumptions and the preliminaries used in our proposed solution.

SYSTEM MODEL

The system consists of the following four main classes (entities) as shown in Figure 3):

-Data Providers generate and distribute data streams to DSMSs. They have the choice of creating and updating the access control policies for the data streams that they emit. -Data Consumers can be individuals or applications who submit CQs to the DSMSs Data consumers must submit credentials to satisfy the policies protecting access to their registered queries. -DSMSs handle all the incoming data streams and submitted queries. They execute query optimizers to generate shared-operator networks for the interleaved execution of queries and schedule the operators' execution. They enforce the access control policies on the data streams and the corresponding query results. -Authorization Servers can be separate entities or an integral part of the DSMSs. They validate users' credentials to check authorizations, and inject relevant SPs into the incoming data streams. They keep track of system state changes such as new data consumers signing up, changes in access control policies, and changes in the users' credentials (e.g., revoked or expired). These changes can trigger the injection of new SPs into impacted data streams to alter which users are able to see the results of CQs.

Operators and Operator Networks

The following are the main defining elements of data streams, CQs, and operator networks that will be used throughout the remainder of this paper: -DSMSs are capable of processing long running set of continuous queries CQs = q 1 , q 2 , . . . , q n executing over data streams in the system. -S denotes the set of all input data streams in the system, while a continuous data stream s ∈ S is a potentially unbounded sequence of tuples that arrive over time. -Tuples in a data stream are of the form t = [sid, tid, A], where sid is the stream identifier, tid is the tuple identifier, and A is the set of attribute values of the tuple. -Queries are comprised of a set of relational query operators o 1 , o 2 , . . . , o n .

A relational operator o i is presented as operator predicate with an associated predicate. This may be a SELECT operator σ over one data stream, a JOIN operator between multiple data streams, a PROJECT operator Π that reduces the number of attributes included in a single data stream, or a GROUP AGGREGATE operator with predicate over a single attribute of a data stream to perform some algebraic aggregate function (e.g., MAX, COUNT, SUM, etc.).

For example, the following are valid query operators

expr 1 : o 1 = σ s2.speed<30 expr 2 : o 2 = s1.location=s2.location & s1.timestamp>6:00am & s1.timestamp<7:00pm
The query optimizer takes as input a set of continuous queries CQ and identifies groups of queries that share sub-expressions. The optimizer then generates a shared-operator network, arranged in a Directed Acyclic Graph (DAG) format, for each group of queries.

Definition 1 An interleaved execution plan for a group of queries is a DAG network N = (V, E, L). V, E, and L being the set of vertices, edges and set of labels, respectively, and are defined as follows:

-A vertex v i is introduced for every operator o i in query q i . If the results of o i are used by more than one operator belonging to different queries, then the vertex v i will be annotated as "Common-prefix" -If the results of o i are used in o j , an edge

(v i → v j ) is introduced -The label L(v i )
is the processing done by the corresponding operator o i (i.e., operator predicate )

Access Control

We assume that DSMSs can enforce query-based access restrictions that can be specified by both the data stream providers and/or the DSMSs over the entire data stream. For example, if a user does not renew his subscription to access certain query results in a DSMS, then this user could be temporarily denied access to any of his registered queries-by denying access to their corresponding data streams-until the subscription is renewed. Similarly, stream data providers can define policies to identify the different data consumers who are allowed to query those data streams. The work presented in this paper is very generic in that it can accommodate a wide range of access control models (e.g., RBAC [START_REF] Ferraiolo | A role-based access control model and reference implementation within a corporate intranet[END_REF], ABAC [START_REF] Hu | Attribute-based access control[END_REF], or DAC [START_REF] Sandhu | Access control: Principle and practice[END_REF]).

In general, let P denote the set of all authorization policies, each authorization policy P : P ∈ P enforced by a DSMS is defined as: P ⊆ CQ × U , where U is the set of users or user roles/attributes. Let function m be a mapping such that m : CQ → S, that is, m identifies the set of data streams that are being accessed by a continuous query.

For each policy P , the authorization server will perform the following:

1. evaluate the proofs of authorization for each (q i , u i ) pair in P 2. execute the mapping function m to identify the set of streams S that are involved in each query q i in the case of query-based policies 3. construct the necessary SPs to identify the access privileges of each user or group of users and inject them in the corresponding streams According to the outcome of the proofs of authorizations, the Sign field in the SP will be set to Sign = '+', if a user may access the data stream tuples for a given query at any time ts access ≥ ts or Sign = '-' if a user is denied access to the data stream at any time ts access ≥ ts. Accordingly, the injected SPs are used by our proposed algorithms to trigger the PrSs to turn on or off in the shared-operator networks to enforce access control.

Security Punctuations

We adopt the notion of Security Punctuations (SPs) [START_REF] Nehme | A security punctuation framework for enforcing access control on streaming data[END_REF][START_REF] Nehme | Fence: Continuous access control enforcement in dynamic data stream environments[END_REF] proposed to enforce access control in operator networks. SPs are considered meta-data in the form of predicates that are injected into data streams in the order of their timestamps and describe the access control privileges of each query. SPs are comprised of the following fields (see Figure 4): -Query ID: the identifier of the query that the SP is defining access for.

INSERT SP AS sp2 INTO STREAM s2 LET [sp2.] QID = q1, [sp2.] DDP = s1:all, [sp2.] SRP = ABAC: u2, [sp2.] SIGN = { -}, [sp2.] TS = <ts2>
-Data Description Part: indicates the schema fields of a data stream tuple that are protected by the policy. This can be at the granularity of an entire stream, or specific tuples or attributes within the tuples. -Security Restriction Part: defines the access control model type and the data user(s) authorized by the policy. -Sign: specifies if the authorization is positive (+) or negative (-).

-Timestamp: the time at which the SP is generated. Figure 4 shows an example input data stream with two SPs. Figure 5 shows an extension to the CQL syntax [START_REF] Arasu | The cql continuous query language: Semantic foundations and query execution[END_REF] to support the specification of SPs in data streams. The figure illustrates the syntax of an SP as well as an example of two SPs injected into two data streams. Each SP indicates the access privileges of a separate user over the tuples of the input data stream.

Privacy-Aware Shared Operator Networks

We now present the details of our proposed approach to achieve a cost-effective way of handling access control in shared-operator networks. As mentioned earlier in Section 1, the naive approaches of applying pre-or post-filtering may considerably limit the shared-operator network performance. The alternative approaches of constantly changing the interleaved shared-operator networks to isolate the queries that are no longer accessible by any of the users, or even maintaining different copies of shared-operator networks are both considered very costly approaches for handling access control.

To overcome these limitations, our proposed solution involves embedding a new set of operators called Privacy Switches(PrSs) in the networks. At a high level, the main idea is to strategically place these switches in the network to shut off branches of operators in the case of total access loss to certain query outputs or by filtering out the query results in the case of partial access loss to queries. By doing so, the shared-operator networks can execute disruptively and efficiently.

Privacy Switches

Privacy Switches (PrSs) are the novel set of operators that will be integrated within the shared-operator networks. These switches allow shared-operator networks to execute the queries impeccably while performing access control-based filtering. For this purpose, three different types of PrSs are introduced:

-initial-switches: placed at some of the input streams to each operator network and perform the traditional pre-filtering operations. -in-network switches: embedded within the operator network and are capable of temporarily shutting off certain branches in the network to save the unnecessary execution of some operators in certain access permission cases. -terminal-switches: placed at the query outputs and they act as multiplexers that can selectively filter query output to multiple users.

All three types of PrSs operate just like any other conditional query operator. They are similar to SELECT or PROJECT operators' that filters data input streams based on the security predicates determined by the SPs injected in the streams.

To better understand how the PrSs operate, assume there is a shared-operator network that interleaves the execution of multiple queries and each query could possibly be shared by multiple users in the DSMS. The three different types of the PrSs cover the following access scenarios:

-Case I: partial loss of access: In this case, only a subset of users lose access to the data streams processed by one or more of the interleaved queries in the shared-operator network. In this case, terminal switches will be in charge of granting access of the query results to the subset of users who did not lose their access privileges. -Case II: total loss of access: In this case, all users lose access to one or more of the interleaved queries in the shared-operator network. Accordingly, instead of operating terminal switches and having possibly unnecessary operators executing, both initial and in-network switches will shut off the isolated branches of operators in the network that are not shared by any other queries.

In this case, a considerable amount of unnecessary work will be saved and performance gains will be achieved. Initial and in-network PrSs are defined as: P rS =< T ype, QueryID, AccessCounter >, where T ype defines whether this is an initial or in-network PrS, QueryID is the query that the PrS is governing access to, and AccessCounter is a counter that changes during the execution of the PrS to identify the number of users who have access to that particular query. The counter will have a value greater than zero in the case of partial loss of access, and will be set to zero in the case of total loss. Terminal switches are defined as: P rS =< T ype, QueryID, U >, where U is the set of users that have access to the query QueryID governed by this switch.

Algorithm 1 shows the pseudocode for executing the different types of PrSs. The input to each PrS is a data stream with embedded SPs. The PrSs execute this algorithm only when new SPs arrive in the data streams. The algorithm shows how the PrSs will allow or prevent the data streams from flowing through the network based on the output of the authorization predicates indicated by the Sign value in each SP.

Both initial and in-network PrSs operate in a similar manner. Each of these PrSs increment their AccessCounter whenever an SP with a matching QueryID and a '+' sign is encountered in the input stream and decremented each time a matching SP with a '-' sign shows up. In the case of partial access loss, the AccessCounter will be greater than zero (i.e., there is at least one SP in a stream that grants access to any user). In this case, the PrS will be switched on and the data stream tuples will flow normally through the network (lines 14 and 15). Note that the assumption made here is that the authorization server will re-inject SPs for the same user or set of users only if there are changes in the access control permissions for those users.

In the case of total loss of access, the AccessCounter will decrement down to zero (i.e., the last user who had access to the query lost that access). Accordingly, the PrS will be switched off and the flow of the tuples will halt temporarily (lines 16 and 17) until new SPs show up with positive access signs.

Terminal switches operate slightly different. They multiplex the final query output tuples to the users that have positive access as defined by their SPs (lines 20 -24). Note that for privacy preservation, the default setup of terminal switches is deny the output to all users and only grant access when explicitly granted by an SP (i.e., they start by an empty set of users U ). Similarly, initial and in-network switches have their AccessCounter initialized to zeros, which by default will deny any access to the query outputs.

The operation of the PrSs is very similar to the well known notion of counting semaphores that are typically used by many systems to coordinate access to different resources. By looking at the status and counter of each PrS, the DSMSs can collect statistics about how many users in the system are currently allowed access to a certain query output. The PrSs present an effective and simple solution for enforcing access control in shared-operator networks. They allow the on-the-fly adjustment of the network status as changes in access control take place without the need to re-direct the input streams to different networks or the need to restructure the operator network.

Placement of Privacy Switches

Algorithm 2 shows the pseudo-code for the PrSs placement algorithm. This algorithm extends the query optimizer, i.e., after a query optimizer constructs a shared-operator network strategically embedding the switches in the network.

The input to the algorithm is a shared-operator network pre-computed by the queries optimizer in the DSMSs. The placement of terminal switches is straightforward, at the end of each query output a terminal-switch will be inserted (line 2). In-network switches placement requires some analysis of the network graph. The main idea is to find the operators that are shared by multiple queries. Those shared-operators annotated are the ones annotated as "Common-Prefixes". The in-network switches will be placed along the outgoing edges of the last set of operators that belong to the common-prefixes (line 15). Finally, the initial-switches are placed at the input streams (lines 7 and 8) to apply pre-filtering of the input streams in the case of total access loss.

Example Execution of Privacy Switches

Figure 6 shows the same shared-operator network as that of the motivating example from Section 4 with the PrSs embedded in the network according to the proposed placement algorithm.

Assume that this shared-operator network is being executed by multiple users who initially have access granted to all three data streams, hence all users can

⋈ ⋈ ∏ Q 1 tmp 5 ← (tmp 1 .location = tmp 2 .

location)

"Common-prefix" Fig. 6. Example of a privacy-aware shared-operators network view the output of both queries. From the figure, the dotted box highlights the "Common-prefix" zone of the operators shared by both executing queries. According to the switches placement Algorithm 2, the in-network privacy switches are placed right after those operators. Also at the output of both queries, terminal switches are placed, and at the front of the streams initial PrSs are placed.

In this particular example, if all users accessing Q2 lose access to the input streams feeding into this query, the PrSs will shut off six out of the ten operators in the network saving unnecessary processing and bandwidth. When any of these users gain their access back, the PrSs will resume operating all the nodes. This shows that the different switches orchestrated together are capable of enforcing the access control policies in shared-operator networks in a cost-effective way.

Evaluation

In the following sections we will present the details of the shared-operator networks simulator we implemented to evaluate the performance of our proposed privacy-aware shared-operator networks, as well as the experimental results.

Configurations and Experimental Setup

Generating synthetic shared-operator networks gave us control over the input parameters and the different scenarios of access control. The simulator takes as input the following parameters: number of input streams, number of interleaved queries, number of users executing those queries, number of query operators, and degree of sharing. The degree of sharing input parameter indicates the percentage of the query operators that will be included in the "common-prefix" of the network (i.e., how many query operators will be shared across the executing queries). An assumption is made that all shared operators are defined over the same window specifications which are omitted for simplicity of the analysis. Given these parameters the simulator generates shared-operator networks arranged as DAGs.

Some heuristics were enforced to assure the correctness and validity of the generated networks. For example, the "join-push-down" approach of operators was enforced (i.e., SELECT and shared SELECT nodes appear before JOIN and shared JOIN nodes). This is a common practice for queries optimizer to execute the SELECT operators first to filter out the tuples as early as possible and improve queries processing times. SELECT and PROJECT operators take one input stream and produce a filtered output stream, while JOIN operators take two different input streams and produce a single joined output stream.

After the random shared-operator networks are generated, our placement Algorithm 2 executes to identify the locations of the PrSs. The number of PrSs is dependent on the topology of the generated network. Finally, the users are randomly assigned to the query outputs of each generated graph. Figure 8 illustrates two randomly generated shared-operator networks by the simulator. Note that the final total number of query operators generated could be slightly higher than the initial input parameter.

In the experiments, the average processing time per tuple for each SELECT and PROJECT operator in the network was set to 0.1ms, and the average processing time per SP for each PrS to 0.1ms as well. JOIN operators average processing time per tuple was set to 0.3ms. Since these simulations are intended to compare and contrast the performance of different operator networks, these values were chosen as rough estimates and defined as constants throughout the execution of the networks. In reality, the processing times of operators would be different from one another. The upper bound on the processing time of each network to process 1000 input tuples was computed. Note that the reported times are upper bound since not every single operator in the network will process all 1000 tuples, as the input tuples get filtered by the SELECT operators, fewer tuples will be processed in the network. The arrival rate of SPs was set to be 100 tuples (i.e., for every 100 tuples, new SPs will show up in the input streams for each user in the system). The PrSs will process all SPs but will only take action for those SPs that match with the SP.QID = P rS.QueryID.

σ q 1 σ ⋈ ⋈ σ ⋈ ⋈ ⋈ q 2 s 1 s 2 s 3 ⋈ q 3 ⋈ σ ⋈ ⋈ (
To better understand the security enforcement overheads in different sharedoperator networks, the upper bound of the network execution times were compared for the following three cases: i)no-sharing -each user is executing a separate operator network for each submitted query (base case), ii)shared without PrSs -shared-operator network with only post-filtering applied, iii)shared with PrSs -shared-operator network with security enforcement using PrSs. To answer this question, the experiments computed the average processing times of 1000 input tuples for different degrees of sharing. Two different experiment settings were used, once for 3 interleaved queries with 15 operators and another for 5 interleaved queries with 25 operators. For each degree of sharing the network execution times were averaged for 10,000 randomly generated operator networks.

Figures 8a and8b show the reported execution times (in log 2 ms) of the networks. The figures show that the average execution time of shared-operator network outperforms the non-shared networks with approximately 92%. This validates the benefits of executing shared-operator networks in DSMSs. The experiments show that the PrSs add negligible overheads to the network performance (an average of 0.5% increase in the execution time). This behavior is justified by the fact that PrSs execute infrequently (only when they encounter a new SPs in the streams that match the query id). The experiments also show that both the number of PrSs inserted in the networks by the placement algorithm and the execution times were insensitive to the degree of sharing.

Experiment 2: Varying Access Control

These experiments were designed to answer the following two questions: Q2: how much cost savings in the networks can be achieved as users start losing access to queries? and Q3: how much does the overlap between queries affect the execution times as users start losing access to queries?

To answer both questions, the experiments measured the execution times of the networks as users start losing access to query outputs. To cover all cases, all different possible combinations of access loss were examined. For each degree of sharing examined, the network execution times were averaged for 10,000 randomly generated shared-operator networks. For each generated network, the execution times were measured in the following scenarios: shared network without PrSs and only post-filtering, shared network with PrSs and full access to all queries and all possible combinations of queries' losses. Figure 9 shows the results for networks generated with 3 input streams and 3 interleaved queries with an average total of 20 operators. On average 11 PrSs were inserted in the generated graphs.

From Figure 9, and consistent with the previous experiments, the difference in execution times between shared networks with and without PrSs was minimal. As the queries start losing access, the savings in the execution times were noticeable when compared to the cases of shared with only post-filtering of query outputs and shared with PrSs and full access. The average execution time savings between the shared with PrSs and shared without PrSs was approximately 38% in the case of two out of three queries lose access, and 19% in the case of one query access loss.

Another observation is that PrSs improve the network performance when the queries have lower degrees of sharing (i.e., less common subexpressions). The reason is, with fewer shared-operators, the in-network switches can shut off more isolated (unshared) query operators in the case of total users loss of some query outputs. This behavior of the privacy-aware shared operator networks show that even with low degrees of sharing, the performance benefits would be even bigger when intermittent total access control loss is encountered.

Conclusions

In this paper we presented a novel solution for enforcing access control over shared-operator networks in DSMSs. The solution presented allows DSMSs to interleave the execution of multiple overlapping queries shared by multiple users while applying access control restrictions on a per user or group of users basis without disrupting the operation of the shared-operator networks. The solution introduces a new set of operators, Privacy Switches (PrS), that are capable of seamlessly configuring the network to allow or deny access to certain query results complying with the access control policies defined in the system. The experimental evaluations showed that the proposed technique induces minimal overheads on the shared-operator networks while achieving great gains in the network performance in the cases of intermittent access loss to some streams and queries. The technique proved to perform better in the case of total access loss with queries that have less common subexpressions, which shows greater benefits of the privacy-aware shared-operator networks even in lower degrees of sharing. A dynamically configurable shared-operator network saves not only time, but also bandwidth consumption, and several consequential monetary costs associated with configuring and executing shared-operator networks in DSMSs that could possibly be operating in cloud environments.

(i) terminal PrSs will only allow users specified by the SPs to access the tuples. (ii) in-network and initial PrSs only allow tuples to flow through the network if there is at least one user that has access granted.

Note that the terminal PrSs are the switches that have the ultimate control of which users can access the tuples of a particular data stream, even if the initial and in-network PrSs allow all the tuples to flow through the network. As such, proving the privacy of a shared-operators network is only dependent on proving that assertion (i) is true. Yet, to prove that a shared-operators network not only denies access to the data streams to those users who are not allowed access, but also ensures that access is granted to those users who are allowed access, then both assertions (i) and (ii) need to be true.

For the base case, assume that ∃ authorization policy P that specifies that u 1 can access q 1 and SP is used to encode this policy and is injected in all data streams used in processing q 1 . Let t ∈ T , where T is a set of tuples, be a tuple that belongs to the data stream used in processing q 1 . There are two cases to be considered to assert both (i) and (ii):

1. SP arrives prior to tuple t, 2. tuple t arrives prior to SP.

Case 1: if SP.q 1 is '+', then all initial and in-network PrSs processing this SP will increment their P rS.AccessCounter and allow the following data tuple t and SP.q 1 to reach to the terminal switches. Terminal switches will in turn add SP.SRP.u id to the list P rS.U and open up the access channel for this user to allow tuple t to flow into query output.

If SP.q 1 is '-', then all initial and in-network PrSs will decrement their counters. If the counter value goes down to zero, this means this user was the last user to have access and the PrSs will not allow the tuples to flow to the output (total loss case). If the counter is greater than zero, then the tuples will flow to the terminal switches. For each terminal switch, if SP.SRP.u id ∈ P rS.U , then this user will be removed from the list, and the access channel to this user will be blocked. Case 2: tuple t will only flow to the channel assigned to user u 1 iff u 1 ∈ P rS.U . Since users are only added to the PrS users list and given access if an explicit SP with a '+' sign is encountered at time SP.T S < ts access , then if t arrives prior to the SP, the denial-by-default will be enforced.

The above cases account for the possible scenarios of a set of tuples T and their equivalent SPs showing up in the data streams. By proving that both assertions (i) and (ii) are true, it is shown that Theorem 1 holds in the base case.

Observe that an argument similar to that used in the base case shows that the same behavior of PrSs would apply to all policies. Furthermore, the inductive hypothesis can be used to prove that the value of the SP.Sign is in charge of activating or deactivating the users channels of the terminal PrSs. As such, only those tuples that are preceded with a positive SP sign will flow to the users specified by the SPs, and Theorem 1 holds for all policies.

  Stream1 : s t r e a m i d , l o c a t i o n , h e a r t R a t e , timestamp Stream2 : s t r e a m i d , l o c a t i o n , s p e e d Stream3 : s t r e a m i d , l o c a t i o n , s c r e e n t i m e , c a t e g o r y Listing 1.1. Data streams generated by smart devices SELECT s1.streamid, s1.heartRate FROM Stream1 as s1 [RANGE 5 min, SLIDE 1 min], Stream2 as s2 [RANGE 5 min, SLIDE 1 min] WHERE s1.location = s2.location AND s1.timestamp > 6:00am AND s1.timestamp < 7:00pm AND s2.speed < 30; SELECT s1.streamid, s1.heartRate FROM Stream1 as s1 [RANGE 10 min, SLIDE 1 min], Stream2 as s2 [RANGE 10 min, SLIDE 1 min], Stream3 as s3 [RANGE 10 min, SLIDE 1 min] WHERE s1.location = s2.location AND s2.location = s3.location AND s1.timestamp > 8:00am AND s1.timestamp < 7:00pm AND s2.speed < 0 AND s3.screentime > 5h;

Fig. 1 .

 1 Fig. 1. Continuous queries CQ1 and CQ2

Figure 2 .

 2 Figure2. The figure excludes the window specifications, for clarity since they are the same for all three data streams. Furthermore, in the figure, the highlighted vertices are annotated as "common-prefix" operators since those are the shared operators between both queries CQ 1 and CQ 2 (i.e., the output of these operators feed into two different operators belonging to the two queries).

Fig. 3 .

 3 Fig. 3. DSMS system model

Fig. 5 .

 5 Fig. 5. SP syntax (right) and sample SPs injected in two separate data streams (left)

Algorithm 2 : 3 s 4 while s is not empty do 5 v 9 else 10 foreach

 2345910 PrSs placement algorithm input: A shared-operator network N = (V, E, L) Data: s defines a stack 1 foreach query qi output traverse N backwards (DFS-search) do 2 insert P rS = < T ype = "terminal", QueryID = qi, U = null > at the output of qi; .push(v); = s.pop(); 6 if v is NOT annotated "Common-prefix" then 7 if N .adjacentEdges(v)==φ then 8 insert P rS = < T ype = "inital", QueryID = qi, AccessCounter = 0 > at the input stream; edge from v to w ∈ N .adjacentEdges(v) do 11 s.push(w); 12 else 13 insert P rS = < T ype = "in -network", QueryID = qi, AccessCounter = 0 > at outgoing edge from v; tmp 32 ← (tmp 11 .location = tmp 31 .location)

Fig. 7 .Fig. 8 .

 78 Fig. 7. Samples of randomly generated shared-operator networks[input streams = 3, queries =3, total operators =12]

Fig. 9 .

 9 Fig. 9. Network execution time for varying degrees of sharing and access loss patterns

Acknowledgments

This work was produced while the first author was a PhD student at the University of Pittsburgh. This work was supported in part by the NSF award CNS1253204 and the NIH award U01HL137159. The content is solely the responsibility of the authors and does not necessarily represent the official views of the NSF and NIH.

Appendix A CORRECTNESS OF PRIVACY SWITCHES

In this appendix we will present proof of correctness of the PrSs operation to ensure that the data streams privacy are enforced at all times. The proof will show that the PrSs will only allow tuples of a particular stream to be accessed by the users that are specified in the SPs, otherwise they will enforce denial-bydefault.

Theorem 1 (PrSs Correctness). During the execution of the PrSs as described by Algorithm 1, for any tuple t, PrS will allow the flow of t only if its preceding SP has a '+' access sign, otherwise PrS will block the flow of t.

Proof. To prove this claim, the following must be asserted: