Non-Interactive Decision Trees and Applications with Multi-Bit TFHE

Abstract

Machine learning classification algorithms, such as decision trees and random forests, are commonly used in many applications. Clients who want to classify their data send them to a server that performs their inference using a trained model. The client must trust the server and provide the data in plaintext. Moreover, if the classification is done at a third-party cloud service, the model owner also needs to trust the cloud service. In this paper, we propose a protocol for privately evaluating decision trees. The protocol uses a novel private comparison function based on fully homomorphic encryption over the torus (TFHE) scheme and a programmable bootstrapping technique. Our comparison function for 32-bit and 64-bit integers is 26% faster than the naive TFHE implementation. The protocol is designed to be non-interactive and is less complex than the existing interactive protocols. Our experiment results show that our technique scales linearly with the depth of the decision tree and efficiently evaluates large decision trees on real datasets. Compared with the state of the art, ours is the only non-interactive protocol to evaluate a decision tree with high precision on encrypted parameters. The final download bandwidth is also 50% lower than the state of the art.

1. Introduction

Machine learning seeks to develop techniques for building models that can accurately and efficiently predict unseen data based on a given training dataset. It is widely used in the areas of computer vision, natural language processing, and many other fields. There is a growing demand for cloud-based machine learning services, where users can upload query data and get back their predicted result. However, these classifiers sometimes require access to sensitive data, raising concerns about the security and privacy of the query data. For example, a client may have to reveal their entire medical record to the diagnosis server. Any leak of such data can have severe repercussions, and it is crucial to ask whether this prediction service can run without revealing any information. Similarly, the model is the result of dedicated research, with considerable effort and resources expended in its development cycle. It is a valuable asset for an organization; exposing it is not an option. Furthermore, recent work [1] shows that models are susceptible to inversion attacks, which recover information about the training data when given access to the model. Therefore, machine learning as a service protocol is only secure if, after execution, the client only learns the result, and the server learns nothing.

A decision tree is a classifier that is more efficient when the data have a hierarchical structure. It is a binary tree storing a threshold in each branching node and a classification result in the leaf nodes. The classifier compares the thresholds with the feature vector elements and decides which node to traverse. This level-by-level traversal continues until it arrives at some leaf node representing the classification result. A decision tree requires less parameter tuning and training cost than other classifiers, such as neural networks. In this work, we focus on privacy-preserving classification using a decision tree. The secure evaluation of the decision tree involves the data owner, the model owner and a third-party evaluator, such as a cloud server. The model owner encrypts the model, and the data owner encrypts the feature vector. A third-party evaluator, such as a public cloud service, evaluates the query using the encrypted model parameters and returns the result, which the data owner decrypts, as shown in Figure 1. The main challenge in secure evaluation is to have an efficient way to compare the thresholds with the feature vector securely. We propose a secure comparison algorithm using fully homomorphic encryption (FHE) [2] and a decision tree evaluation protocol that preserves all the functionality without compromising the privacy of the data and model owners.

This work aims to design and implement a private decision tree evaluation protocol that is both efficient and non-interactive. To this end, we propose a new non-interactive private comparison method that allows its output to be further used in the decision tree evaluation. This method can compare two encrypted integers, a and b, and return a ciphertext that decrypts to 1 if $a>b$ and 0 otherwise. We encrypt each nibble of integer a and b using the fully homomorphic encryption over the torus (TFHE) [3] scheme, and then we compare the encrypted nibbles using programmable bootstrapping [4]. Since the TFHE scheme supports bootstrapping, we can use the encrypted output in further homomorphic operations. This method’s non-interactive property is used in the non-interactive private decision tree evaluation protocol. In this protocol, we use our private comparison method to compare the thresholds of the decision tree with the feature vector elements. Then, we use the output of the private comparison method to traverse the decision tree to evaluate the classification result. We implemented and conducted rigorous experiments to study the effect of different bit lengths to assess scalability. We also conducted experiments with decision trees trained with real datasets from the UCI machine learning repository [5] and compared them with the existing protocols.

Existing approaches to the comparison of encrypted integers are not suitable for our purpose. The performance of bit-wise comparison operation using naive TFHE encryption is very slow and grows linearly with bit length. The state-of-the-art comparison operation using XCMP [6] only performs well for integers with a small bit length and grows exponentially with bit length. Even though the comparison operation proposed by Iliashenko et al. [7] can make the comparison for arbitrary length, it is hard to accelerate the comparison operation, as it is not using a $2^n$-cyclotomic polynomial. It also does not support the bootstrapping needed for our decision tree evaluation protocol. Therefore, we propose the first multi-bit comparison method using the TFHE scheme to compare integers.

In summary, we make the following improvements to the existing protocols:

• Our private comparison method operates on two encrypted inputs with 128-bit security, facilitating the use of third-party evaluators, such as the public cloud. The performance of our method scales linearly with the input bit length and the depth of the decision tree.
• Our decision tree evaluation protocol is non-interactive, where the client sends encrypted input and receives the encrypted output. There is no other interaction between the client and the server.
• Experimentally evaluated the effect of bit lengths to assess the scalability of our method compared to other methods.
• In our implementation, we conducted experiments with decision trees trained with widely used real datasets from the UCI machine learning repository [5] and compared them with the existing protocols.
• The final output of the protocol consists of a ciphertext that decrypts the classification result. This can be extended to the decision tree returning categorical values, using one-hot encoding. The results from multiple decision trees can be combined to evaluate random forest classification.

The rest of the paper is organized as follows. The next section discusses related work on secure decision tree evaluation and integer comparison. Section 3 introduces the main ideas in fully homomorphic encryption and decision tree evaluation. Using an enhanced comparison protocol, Section 4 and Section 5 propose a new method for evaluating decision trees in a privacy-preserving manner. The computational complexity and performance are discussed in Section 6. Finally, Section 7 concludes the paper.

2. Related Work

Earlier works [8,9] focus on securely constructing the decision tree using data mining techniques on joint data without sharing the participant’s data. With the advent of cloud computing, privacy-preserving decision tree evaluation has become increasingly important. Generic secure multiparty computation protocols, such as Yao’s garbled circuits [10], were proposed for this problem. However, this approach requires one party to create the circuit and the other to evaluate it, resulting in the client participating in the computation. It also incurs high communication costs.

Specialized protocols for the private evaluation of decision trees were subsequently developed that only used generic methods as and when needed. Brickell et al. [11] and Barni et al. [12] proposed a secure protocol for linear branching programs that utilizes both garbled circuits and homomorphic encryption. After that, new interactive protocols were built for decision tree evaluation using a combination of fully homomorphic encryption (FHE), oblivious transfer (OT), and somewhat homomorphic encryption (SHE), requiring multiple rounds of communication. All suffer from high communication and computation overhead. These protocols also do not allow the model to be shared with an evaluator without leaking the model.

Order-preserving encryption (OPE) was proposed by Agrawal et al. [13] and is a type of encryption scheme that preserves the order relationship between plaintexts. Boneh et al. [14] proposed the order-revealing encryption (ORE) scheme, which uses multi-linear maps to generalize OPE. Even though these schemes look appealing for integer comparison operation, their order-revealing nature results in the leakage of plaintext from ciphertext using frequency analysis and is vulnerable to inference attacks [15].

Efficient homomorphic encryption-based integer comparison methods, such as the DGK protocol [16,17,18], compare an encrypted integer with a plaintext integer. Multiple rounds of interaction during protocol execution are required for methods such as that of Bost et al. [19]. The comparison operation from Illashenko et al. [7] does not support bootstrapping and is unsuitable for our purpose. The current state-of-the-art non-interactive integer comparison protocol XCMP [6] has a limitation on the bit length of the inputs.

3. Preliminaries

This section presents some fundamental concepts used in the rest of the paper. In particular, we describe and revisit the TFHE encryption scheme and decision tree structure before applying it in privacy-preserving decision tree evaluation. Further, we discuss a combinational digital circuit that comprises comparators and multiplexers.

3.1. Fully Homomorphic Encryption

Homomorphic encryption, unlike traditional encryption, allows the user to operate on ciphertexts securely. A fresh homomorphic encryption ciphertext is a summation of the plaintext $\in {\mathbb{Z}}_p/\langle x^n+1\rangle$, a mask $\in {\mathbb{Z}}_q/\langle x^n+1\rangle ,q>p$ which is removable using the secret key, and an initial noise which can be removed using the modulus p operations. The initial noise is usually sampled from discrete Gaussian distribution and is small in terms of the coefficient’s size. Whenever we perform a homomorphic operation, we add additional noise to the ciphertexts. At some point, if the noise becomes too big, we will not be able to decrypt the ciphertext successfully. In this paper, we use a fully homomorphic encryption scheme, where the ciphertext is refreshed using the bootstrapping technique to reduce the noise level whenever it exceeds a certain threshold. We choose the TFHE scheme [3] to implement our algorithms, as its bootstrapping technique is programmable to evaluate complex functions.

Gentry [2] defines Bootstrapping as a technique to reduce the noise in the ciphertext when it grows beyond a specific limit. It is done using a bootstrapping key, which is nothing but the encryption of a secret key using another secret key, i.e., $bk=Enc\left(sk\right)$. Given a ciphertext $ct$ corresponding to encryption of plaintext m, then $De{c}_{sk}\left(ct\right)=m$. Let $F\left(x\right)=De{c}_x\left(ct\right)$ be a function which decrypts a ciphertext given a secret key x. Let $c{t}^{\prime }$ be the decryption using the bootstrapping key $bk$.

$$c{t}^{\prime }=F\left(bk\right)=F\left(Enc\left(sk\right)\right)=Enc\left(F\left(sk\right)\right)=Enc\left(De{c}_{sk}\left(ct\right)\right)=Enc\left(m\right)$$

(1)

Hence, $c{t}^{\prime }$ is another encryption of the same message m, but with a lower noise level.

Let us denote $\mathbb{T}=\mathbb{R}/\mathbb{Z}$ as the real torus. ${\mathbb{T}}_q:=q^{-1}\mathbb{Z}/\mathbb{Z}$ is the real torus modulo q. $\mathbb{B}$ is the integer subset $\{0,1\}$. We use the notation $a\stackrel{\$}{\leftarrow }S$ to denote that a is sampled uniformly at random from a set S. Similarly, $b\leftarrow \mathcal{D}$ denotes sampling from a probability distribution $\mathcal{D}$. For a real number x, $\lfloor x\rceil$ denotes the nearest integer to x. The standard algorithms [3] for key generation, encryption, decryption, homomorphic operations, and bootstrapping are below.

• KeyGen(${\mathbf{1}}^{\mathbf{\lambda }}$) On input security parameter $\lambda$, the key generator generates a secret key $sk$ and public parameters $\{n,\sigma ,p,q\}$. n is a positive integer. p and q are chosen such that $p\mid q$. A normal distribution $\chi =\mathcal{N}\left(0,{\sigma }^2\right)$ over $\mathbb{R}$ is used to create a discretized error distribution $\widehat{\chi }$ over $q^{-1}\mathbb{Z}$. The private key $sk$ is sampled uniformly at random from ${\mathbb{B}}^n$, i.e., $sk=\left(s_1,\dots ,s_n\right)\stackrel{\$}{\leftarrow }{\mathbb{B}}^n$. The plaintext space is $\mathcal{P}={\mathbb{T}}_p\subset {\mathbb{T}}_q$.
• Encrypt _sk(μ) The encryption of $\mu \in \mathcal{P}$ is given by

  $$c\leftarrow {\mathrm{TLWE}}_s\left(\mu \right)=\left(a_1,\dots ,a_n,b\right)\in {\mathbb{T}}_q^{n+1}$$

  (2)

  with

  $$\left\{\begin{array}{c}{\mu }^{*}=\mu +e\hfill \\ b=\sum _{j=1}^n{s}_j·a_j+{\mu }^{*}\hfill \end{array}\right.$$

  (3)

  for a random vector $\left(a_1,\dots ,a_n\right)\stackrel{\$}{\leftarrow }{\mathbb{T}}_{\mathrm{q}}^n$ and a small noise $e\leftarrow \widehat{\chi }$
• Decrypt _sk(c) To decrypt $c=\left(a_1,\dots ,a_n,b\right)$, use private key $s=\left(s_1,\dots ,s_n\right)$, compute

  $${\mu }^{*}=b-\sum _{j=1}^n{s}_j·a_j$$

  (4)

  and return

  $$\mu =\frac{⌊p{\mu }^{*}⌉modp}{p}$$

  (5)
• Addition of ciphertexts Let $c_1\leftarrow {TLWE}_s\left({\mu }_1\right)$ and $c_2\leftarrow {TLWE}_s\left({\mu }_2\right)$ be respective TLWE encryptions of ${\mu }_1$ and ${\mu }_2$, i.e., $c_1=\left(a_1,\dots ,a_n,b\right)$, $c_2=\left(a_1^{\prime },\dots ,a_n^{\prime },b^{\prime }\right)$, $b^{\prime }={\sum }_{j=1}^n{s}_j·a_j^{\prime }+{\mu }_2+e_2$, and $e_1,e_2$ small. Then

  $$c_3:=c_1+c_2$$

  (6)

  is a valid encryption of ${\mu }_3:={\mu }_1+{\mu }_2$ provided that the additive noise $e_3:=e_1+e_2$ remains small.
• Multiplication by a known constant Let $K>0$ be a small integer, and ciphertext c be the ${TLWE}_{\mathrm{s}}\left(\mu \right)$ where $\mu \in \mathcal{P}$. By multiplying K with every vector component of c, we obtain ${TLWE}_{\mathrm{s}}(K·\mu )$. If $c=\left(a_1,\dots ,a_n,b\right)\in {\mathbb{T}}_q^{n+1}$, then

  $$K·c=\left(K·a_1,\dots ,K·a_n,K·b\right).$$

  (7)

  provided that the resulting noise is kept small.
• Bootstrapping In Gentry’s seminal thesis [2], bootstrapping is performed by homomorphically decrypting a ciphertext using its key’s encryption to reduce the noise in the ciphertext.
  The bootstrapping of a TLWE ciphertext $c\leftarrow {TLWE}_s\left(\mu \right)\in$${\mathbb{T}}_q^{n+1}$ encrypted with secret key $s=\left(s_1,\dots ,s_n\right)\in {\mathbb{B}}^n$ is done in three steps.
  • $c^{\prime }\leftarrow {\mathrm{BlindRotate}}_{bsk}\left(c\right)$
    This operation returns a ring (torus polynomials) LWE ciphertext in ${\mathbb{T}}_{N,q}{\left[X\right]}^{k+1}$. This operation rotates a test polynomial homomorphically (the reason for naming it blind rotation) using a bootstrapping key, which consists of a list of encryptions of the elements of the secret key s.
  • $c^{\prime }\leftarrow \mathrm{SampleExtract}\left(c^{\prime }\right)$
    This operation extracts the constant coefficient of ${\mathbf{c}}^{\prime }$, resulting in an LWE ciphertext in ${\mathbb{T}}_q^{N+1}$
  • $c^{″}\leftarrow {\mathrm{KeySwitch}}_{ksk}\left(c^{\prime }\right)$
    This final step uses key-switching keys to return to the original LWE ciphertext in ${\mathbb{T}}_q^{n+1}$, encrypted with the original secret key s.
  More details can be found in reference [3].
• Programmable Bootstrapping This technique converts a high-noise ciphertext into a new one with less noise while simultaneously evaluating a function on the encrypted data. It is achieved by encoding a look-up table in the test polynomial used in the blind rotate operation during bootstrapping. Consider a function $f:{\mathbb{T}}_p\to {\mathbb{T}}_p$ and a noisy ciphertext $c\leftarrow {\mathrm{TLWE}}_s\left(\mu \right)$; programmable bootstrapping outputs a new ciphertext $c^{\prime }\leftarrow {TLWE}_s\left(f\left(\mu \right)\right)$, having a small amount of noise. Regular bootstrapping is a case of programmable bootstrapping where f is the identity function. The details regarding look-up table construction can be found in reference [4].

3.2. Combinational Digital Circuits

In this section, we give a brief overview of the combinational digital circuits that are used in our integer comparator circuits.

3.2.1. Comparator

A comparator decides whether two numbers are greater or less than the other or equal. It receives two n-bit binary numbers, X and Y, and outputs the comparison outcome as a bit. There are two common types of comparators. An equality comparator indicates whether X equals Y, and a magnitude comparator indicates whether the value of X is greater or lesser than the Y value.

The equality comparator is the more straightforward circuit compared to the magnitude comparator. It uses the XNOR gate to check that bits in X and Y corresponding to the same column are equal. If it is valid for all the columns, the numbers are equal.

The magnitude comparator also compares each bit of two numbers, such as $X=X_3{X}_2{X}_1$ and $Y=Y_3{Y}_2{Y}_1$. It starts from the most significant bits, checking if the pair of bits is equal and assigning the result to $E_3$.

$$E_3={\overline{X}}_3{\overline{Y}}_3+X_3{Y}_3$$

(8)

It then continues checking for the next most significant pair till it reaches the least significant pair of bits. Hence, $E_2={\overline{X}}_2{\overline{Y}}_2+X_2{Y}_2$ and $E_1={\overline{X}}_1{\overline{Y}}_1+X_1{Y}_1$.

If $X>Y$, then the following equation evaluates to 1.

$$X>Y=X_3{\overline{Y}}_3+E_3{X}_2{\overline{Y}}_2+E_3{E}_2{X}_1{\overline{Y}}_1$$

(9)

Suppose the most significant bits are $X_3>Y_3$, where $X>Y$, irrespective of the bit values in other places of the number. This logic corresponds to the first term $X_3{\overline{Y}}_3$ in the equation. On the other hand, if the most significant bits are equal, $X>Y$ if the next significant bit $X_2$ is greater than $Y_2$ as evaluated by the second term $E_3{X}_2{\overline{Y}}_2$ in the equation. Finally, the third term $E_3{E}_2{X}_1{\overline{Y}}_1$ evaluates to one if the least significant bit $X_1$ is greater than $Y_1$ and all other bits are the same.

The IC 7485 is a TTL family 16-pin 4-bit magnitude comparator with outputs $X=Y,X>Y$, and $X<Y$. Words of larger length are compared by cascading these comparator chips one after another, as shown in Figure 2.

The rightmost cascading inputs are connected to fixed logic values, and the leftmost cascading outputs provide important final outputs. Instead of the 4-bit comparator, a single-bit comparator can be used at each step. It tracks whether the numbers corresponding to the compared bit pairs are greater or lesser.

3.2.2. Multiplexer

Multiplexing means transmitting many information units over a smaller number of channels or lines. The function of a multiplexer is to choose an output from a selection of inputs such as a rotary switch. A digital multiplexer (MUX) is a combinational circuit that selects one of $2^n$ data input lines based on an n-bit address, directing it to one output line. A set of selection lines controls the selection of a particular input line.

A typical multiplexer has $2^n$ information inputs $(I_{(2^n-1)},\dots ,I_0)$, n select inputs $(S_{n-1},\dots ,S_0)$ and one information output Y. The simplest multiplexer when $n=1$ is a $2^1$-to-1 multiplexer, shown in Figure 3. The single selection variable S has two values, 0 and 1. When $S=0$, the multiplexer selects and outputs the first input, A. Similarly, when $S=1$, the multiplexer selects the second input B. Optimizing the truth table with Karnaugh maps gives the equation $Out=\overline{S}A+SB$.

3.3. Decision Tree

A decision tree is a popular classification model capable of fitting complex datasets. They are the fundamental building blocks for powerful machine learning algorithms, such as random forest. Decision tree training algorithms, such as CART, produce a binary tree where the interior nodes always contain two children. It is built by recursively splitting the data into smaller parts until the data are split into a single leaf node. The decision tree is a white-box model, where their decisions are more accessible to interpret than a black-box model, such as neural networks.

Given an attribute vector $\mathbf{x}=(x_1,\dots ,x_n)\in {\mathbb{Z}}^n$, the decision tree evaluates the input vector x and returns the output class. The decision tree with m internal nodes implements a function $\mathcal{T}:{\mathbb{Z}}^n\to \mathbb{Z}$ that maps an attribute vector $\mathbf{x}\in {\mathbb{Z}}^n$ to a classification result in $\{v_1,\dots ,v_{m+1}\}$. A decision tree with m decision nodes is a binary tree with m + 1 leaf nodes. The leaf nodes contain the output class $v_i$, and the interior nodes contain the threshold value ${\tau }_i$. Figure 4 shows a decision tree with $m=3$ decision nodes. The decision at each node is a comparison test on one of the feature attributes $x_{\sigma \left(i\right)}$ to a threshold value ${\tau }_i$ for node i. The $\sigma \left(i\right)$ is the feature attribute index used to make the decision. Decision tree evaluation starts from the root. It then moves on to the left or right child node based on the test on the current node. This step continues until reaching a leaf node storing the output class. The depth of a decision tree, denoted by d, is the length of the longest path between the root and any leaf.

4. Private Comparison of Integers

This section presents our novel comparison algorithm for encrypted integers, which is the critical component of our privacy-preserving decision tree evaluation.

We encrypt an unsigned integer by considering it a sequence of 4-bit integers or nibbles. The first nibble is the most significant, and the last nibble is the least significant. Each of these nibbles is encrypted separately using TFHE [3] encryption. The encrypted nibbles are then concatenated to form the encrypted integer.

The 4-bit integers are encoded to the plaintext space $\mathcal{P}={\mathbb{T}}_p$, where $p\mid q=2^{64}$. The value of p should be greater than 4-bits. As the leading bits, these extra bits accommodate the result of homomorphic operations such as addition. These leading bits are called padding bits [4] and are initialized to zero. The number of padding bits is denoted by $\overline{\omega }$.

4.1. Nibble Comparator

We define two operations on encrypted nibble: HE-Nibble-Eq and HE-Nibble-Gt. The first operation is a homomorphic equality operation, and the second is a homomorphic greater-than operation. Both of the operations start by subtracting the first encrypted nibble from the second encrypted nibble, as shown in Figure 5. The subtraction result is a ciphertext with $\overline{\omega }-1$ bits of padding.

The resulting ciphertext is then bootstrapped, using programmable bootstrapping. The univariate function, passed to the bootstrapping function for equality, checks if the input is zero. If it is true, it returns one. Else, it returns zero. Similarly, the univariate function checks if the input is greater than zero for greater-than checking. We also specify the programmable bootstrapping function to output the final ciphertext with the initial $\overline{\omega }$ bits of padding.

4.2. Integer Comparator

We compare the encrypted integers by cascading encrypted nibble comparators, similar to cascading comparators in Figure 2. Each comparator takes in two encrypted nibbles and the output from the previous comparator. If both the encrypted nibbles are equal, then the output of the comparator is the same as the output of the previous comparator. If the encrypted nibbles are not equal, then the output of the comparator is as follows. If the first encrypted nibble is greater than the second encrypted nibble, it is one. Otherwise, it is zero. A 2-to-1 multiplexer can realize this.

The equality and greater-than evaluation of the encrypted nibbles are done using the nibble comparator described in Figure 5. We design a homomorphic multiplexer HE-Mux algorithm which takes encrypted bits in the input and selection lines as described in Algorithm 1. Let A and B be the inputs and S be the selection line of the mux. We encode the A, B and S as bits of a binary number represented as $SA{B}_2$, with S being the most significant bit. The equivalent decimal number is deduced by multiplying S by $2^2$, A by $2^1$, and B by one and then adding all the terms. The output of the multiplexer is the encrypted bits of the decimal number.

We achieve the binary to decimal conversion homomorphically by using the parallel prefix sum [20] technique shown in Algorithm 2. If the encrypted bits have a padding $\overline{\omega }$ of 4, it is arranged in an array of length $n=8$. S is duplicated four times, and A is duplicated twice in the array. We append encryptions of zero to fill the array. We then use the Parallel-Prefix-Sum algorithm to sum the encrypted bits. The output is the encrypted sum.

Algorithm 1HE-Mux

Input: Condition S, Input A, Input B, Zero ∅ Output:A if Condition $S\equiv 1$, B if $S\equiv 0$ $input\leftarrow [S,S,S,S,A,A,B,\varnothing ]$ $sum\leftarrow$Parallel-Prefix-Sum$\left(input\right)$ $result\leftarrow$Pbs$(sum,f_{MUX}\left(x\right))$ $result\leftarrow$Ks$\left(result\right)$ return$result$

Algorithm 2Parallel-Prefix-Sum

Input: An encrypted array $\mathbb{X}$ of length n, encryption of zero $〚0〛$ Output: Sum of all the elements of the array $\mathbb{X}$ $m\leftarrow 2^{\lceil {log}_{2}n\rceil }$ Append $m-n$ zeros to the array $\mathbb{X}$ for$i\leftarrow 0$ to $\lceil {log}_{2}n\rceil -1$ do     for $j\leftarrow 0$ to $m-1$ do         $X[j+2^{i+1}-1]\leftarrow$HE-Nibble-Add$(X[j+2^i-1],X[j+2^{i+1}-1])$         $j\leftarrow j+2^{i+1}$     end for end for return$X[m-1]$

Adding two ciphertexts decreases the padding and increases the noise in the output ciphertext. This decrease happens at every algorithm iteration, as shown in Figure 6. The Parallel-Prefix-Sum algorithm ensures that the two ciphertexts in the add operation have the same padding.

The resulting sum is then bootstrapped using programmable bootstrapping with the function $f_{MUX}\left(x\right)$ that evaluates the following truth table of the multiplexer shown in Figure 3.

$$f_{MUX}\left(x\right)=\left\{\begin{array}{cc}0\hfill & x={000}_2\hfill \\ 0\hfill & x={001}_2\hfill \\ 1\hfill & x={010}_2\hfill \\ 1\hfill & x={011}_2\hfill \\ 0\hfill & x={100}_2\hfill \\ 1\hfill & x={101}_2\hfill \\ 0\hfill & x={110}_2\hfill \\ 1\hfill & x={111}_2\hfill \end{array}\right.$$

(10)

The final value is key switched to obtain the multiplexer output. All the operations in the multiplexer are summarized in Figure 7.

Our comparison algorithm PvtCmp of two encrypted integers of length n nibbles is summarized in Algorithm 3. If the encrypted integers contain just one nibble, then the result of the nibble comparator function HE-Nibble-Gt is used. Otherwise, the encrypted integers are traversed from the least significant nibble to the most significant nibble. The encrypted nibbles are compared using the nibble comparator functions HE-Nibble-Gt and HE-Nibble-Eq, and multiplexed using the HE-Mux multiplexer. The result is rippled from right to left, as shown in Figure 8, and the final result from the most significant nibble is returned.

Algorithm 3PvtCmp: Encrypted Greater Than Comparison Function

Input: An encrypted array $\mathbb{X}$, $\mathbb{Y}$ of length n nibbles, encryption of zero $〚0〛$ Output: Encrypted 1 if $\mathbb{X}>\mathbb{Y}$, encrypted 0 otherwise if$n\equiv 1$then     return HE-Nibble-Gt$\left(\mathbb{X}\right[0],\mathbb{Y}[0\left]\right)$ end if $result\leftarrow 0$ for$i\leftarrow 0$ to $n-1$ do     $eq\leftarrow$HE-Nibble-Eq$\left(\mathbb{X}\right[i],\mathbb{Y}[i\left]\right)$     $gt\leftarrow$HE-Nibble-Gt$\left(\mathbb{X}\right[i],\mathbb{Y}[i\left]\right)$     $result\leftarrow$HE-Mux$(eq,result,gt,0)$ end for return$result$

5. Applications of Private Integer Comparison: Decision Trees

In this section, we consider the application of our private integer comparison to decision trees.

5.1. Private Evaluation of Decision Trees

Recall from Figure 4 that evaluating the decision tree requires comparing each node threshold with one of the feature vector values. This comparison is made using our PvtCmp function, resulting in a tree with encrypted comparison results. For each node i, we assign $b_i\leftarrow$PvtCmp$(x_{\sigma \left(i\right)},{\tau }_i)$.

After computing all the decision values in the internal nodes, we assign a cost to each edge similar to Tai et al. [21], as shown in Figure 9. If the value of $b_i$ is 1, then the path cost on its right edge will be 0, whereas the path cost on the left edge will be 1. In other words, the traversal will have a penalty of 1 for continuing on the left edge. Similarly, if the value of $b_i$ is 0, then the path cost on its left edge will be 0, whereas the path cost on the right edge will be 1. The value $1-b_i$ is computed using programmable bootstrapping with the function below, which inverts the input bit.

$$f\left(x\right)=\left\{\begin{array}{cc}1\hfill & x=0\hfill \\ 0\hfill & x\ne 0\hfill \end{array}\right.$$

(11)

For each leaf node, we construct a path from the root node consisting of all the edges from it to the leaf node. The cost of a path is computed by adding the path cost of all the edges in its path. We make use of our Parallel-Prefix-Sum algorithm to compute the path cost. If the length is less than $2^m$, we append zero encryption to the path. If the length is greater than $2^m$, then we split the path into chunks of size $2^m$ and compute the path cost recursively by adding the path cost of the chunks. The paths of interest are those with a path cost of zero. Hence, we invert the path cost using a programmable bootstrapping function; the paths with zero path cost return one, and those with non-zero path cost return zero. The details of the algorithm are shown in Algorithm 4. The outputs of Is-Zero-Path-Cost are multiplied with the corresponding leaf value $v_i$, and the terms are added to obtain the final output.

Figure 10 shows the complete private decision tree evaluation. The client sends the encrypted integer as a sequence of encrypted nibble $\left[x_1\right],\left[x_2\right],\cdots \left[x_n\right]$ to the server. The model owner also encrypts the decision tree thresholds $\left[{\tau }_1\right],\left[{\tau }_2\right],\cdots \left[{\tau }_m\right]$ to the server. The server computes the private comparison values $\left[b_1\right],\left[b_2\right],\cdots \left[b_m\right]$ for each of the m interior nodes. The server then computes the edge costs $\left[ec\right]$ of each node. For all the paths $P_i$ where $i\in \{1,m+1\}$ from root to the leaf node, we calculate its edge path cost $p{c}_i$ using the Parallel-Prefix-Sum algorithm. The $\widetilde{p{c}_i}$ is calculated by inverting the $p{c}_i$ bit to indicate whether the path has zero edge path cost. The final result is obtained by pairwise multiplying $\widetilde{p{c}_i}$ with $v_i$ to obtain the final v value. The server sends the encrypted $\left[v\right]$ to the client, and the client decrypts the $\left[v\right]$ to obtain the final classification.

Algorithm 4Is-Zero-Path-Cost

Input: An encrypted bit array $\mathbb{X}\in 〚\mathbb{B}{〛}^n$, encryption of zero $〚0〛$ Output: An encrypted bit $b\in 〚\mathbb{B}〛$, such that $b\leftarrow 〚1〛$ if $〚1〛\in \mathbb{X}$ Split the array $\mathbb{X}$ into ${\mathbb{X}}_0,{\mathbb{X}}_1,\dots \in {\left[\mathbb{B}\right]}^k$, where $k\le n$ and $k=2^m$. Append $\left[0\right]$ to the last split if $k\nmid n$. for all${\mathbb{X}}_i$do     $partial\_sum\left[i\right]\leftarrow Parallel-Prefix-Sum\left({\mathbb{X}}_i\right)$     $partial\_sum\left[i\right]\leftarrow Pbs\left(partial\_sum\left[i\right],\lambda \left(x\right)=\left\{\begin{array}{cc}1\hfill & x=0\hfill \\ 0\hfill & x\ne 0\end{array}\right.\right)$     $partial\_sum\left[i\right]\leftarrow Ks(partial\_sum[i\left]\right)$ end for if$partial\_sum$ has more than one element then     return Is-Zero-Path-Cost(partial_sum) else     return $partial\_sum\left[0\right]$ end if

5.2. Extensions to Private Decision Tree Evaluation

In our protocol, we used label encoding to encode the class labels. Each leaf node has the output class encoded in $v_i$ as an integer value. This encoding is efficient for binary classification problems, or the number of classes is small. The scalar multiplication of $v_i$ with $\widetilde{p{c}_i}$ using Equation (7) is only feasible if the scaling of the noise is small. Therefore, we must use a different approach for multi-class problems and regression trees.

5.2.1. Multi-Class Decision Trees and Regression Trees

A one-hot encoding scheme encodes the class labels for multi-class problems. The one-hot encoding is a vector where the ith element is one if the ith class is selected and zero otherwise. We encode the output classes $v_i$ in the leaf nodes as shown in Figure 11. The scalar multiplication with $\widetilde{p{c}_i}$ is done element-wise using the vector. The vectors are then added element-wise using Parallel-Prefix-Sum to obtain the final v as an encrypted one-hot vector.

We use a similar approach for regression trees, where the output values are encoded as a binary vector. The final value after scalar multiplication and element-wise addition is the binary value of the regression tree.

5.2.2. Random Forest Classification

A random forest is a collection of decision trees, where the final decision is made by taking the majority vote of the decision trees. Even though the random forest algorithm can be used for regression, we focus on classification problems. Like multi-class classification, each decision tree in the random forest returns its output class as a one-hot encoded vector.

Once the server obtains the individual decision tree results, the server computes the final result by adding element-wise again using the Parallel-Prefix-Sum algorithm. The final result vector is then sent to the client. The client decrypts the result, and the class with the highest vote is selected as the final classification.

6. Evaluation

We evaluate the computational complexity and the performance of our private decision tree evaluation.

6.1. Computational Complexity

Let n be the number of entries in the feature vector and m be the number of decision nodes in the decision tree. Let these numbers be represented as t-bit integers. Since we encrypt all the integers as a sequence of 4-bit nibbles, encrypting n entries in the feature vector takes $O(n\times \lceil t/4\rceil )$ steps. Similarly, comparing m decision node thresholds takes $O(m\times \lceil t/4\rceil )$ steps. The time taken for the edge path cost is negligible compared to the threshold comparison.

We compare our protocol with recent protocols by Bost et al. [19], Wu et al. [22], and Tai et al. [21].

Table 1. Computational complexity summary.

Protocol	Complexity		Rounds	Scheme	Leakage
	Client	Server			Client	Server
Bost et al. [19]	$O\left(\right(n+m\left)t\right)$	$O\left(mt\right)$	≥6	Levelled-FHE	None	m
Wu et al. [22]	$O\left(\right(n+m)t+d)$	$O(mt+2^d)$	6	AHE	None	$m,d$
Tai et al. [21]	$O\left(\right(n+m\left)t\right)$	$O\left(mt\right)$	4	AHE	None	m
This work	$O(n\times \lceil t/4\rceil )$	$O(m\times \lceil t/4\rceil )$	2	TFHE w PBS	None	None

shows all protocols’ computational complexity.

6.2. Experimental Results

We implemented the comparison function and the classifiers in Rust using the concrete (https://github.com/zama-ai/concrete/tree/concrete-0.1.11 (accessed on 4 August 2022)) library [23] for the TFHE implementation. Our performance evaluations were run on a server with Intel Xeon Platinum 8170 (64-bit) processors running at 3.7 GHz and 192 GB RAM.

We chose the statistical security parameter $\lambda$ to be 128 and instantiated the TFHE scheme with the following parameters by the LWE estimator [24]. We used the default value for $q=2^{64}$ given by the library. The number of padding bits $\overline{\omega }$ was set to 4 while encoding the 4-bit integers. Hence, the value of $p=2^{4+4}$, i.e., uses 4-bits precision for representing the number and another 4-bits for padding.

The LWE key has a dimension of 750 and a noise with a standard deviation of $2^{-18}$. For the RLWE key, we used a polynomial of size 2048 and a standard deviation of $2^{-52}$. The bootstrapping key has base $2^7$ and level 3. The key-switching key has base $2^2$ and level 7.

We ran benchmarks for the performance of our comparison function and XCMP [6] non-interactive private method. Specifically, we measured the computation time for evaluating comparison, excluding the encryption and decryption time. The integer input size varied from 12 bits to 32 bits. The value of bit length for XCMP could only be measured to 19 bits because of the constraints of HElib [25]. The rest of the values for XCMP were extrapolated for higher bit length. The results are shown in Figure 12. Our comparison function for 32-bit and 64-bit integers is 26% faster than the naive TFHE implementation. A more efficient version of XCMP was mentioned in [26], but we could not compare its performance since its source code is not open sourced.

We measured the path cost computation time for long paths to see the impact on evaluation trees with high depth. The computation time grows linearly with the length of the path in every step of 4. The results are shown in Figure 13.

We trained our decision tree models on real datasets from the UCI repository [5] using the scikit-learn library [27]. The training phase was done on plain data without any encryption. The number of features, decision nodes and the depth of the trained models are summarized in

Table 2. Performance of secure evaluation on real datasets from UCI repository.

Dataset	n	d	m	Evaluation Time (s)
				This Work		XCMP [6]	Tai et al. [21]
				32-bit	64-bit	13-bit	64-bit
Heart-disease	13	3	5	24.29	47.52	0.59	0.25
Credit-screening	15	4	5	24.29	47.52	–	0.27
Breast-cancer	9	8	12	58.30	114.04	–	0.34
Housing	13	13	92	446.98	874.29	10.27	1.98
Spambase	57	17	58	281.79	551.19	6.88	1.80

. We measured the performance of our secure evaluation after both the client’s input and the decision tree thresholds were encrypted.

The performance gain achieved by the XCMP protocol is hindered by the fact that the feature vectors and decision tree thresholds cannot be more than 13 bits long. The work of Tai et al. [21], on the other hand, is an interactive protocol where the server needs to communicate with the client to determine the result.

The final LWE encrypted classification result is serialized and sent to the client. Hence, the download bandwidth is a constant size, irrespective of the structure of the decision tree. The JSON serialization of LWE ciphertext of dimension 750 takes 17 KB of space. This size is less than half the download bandwidth required by Wu et al. [22] for the heart-disease and credit-screening datasets. The download bandwidth for Wu et al. for other real datasets in Table 2 is more than a hundred times larger than our result ciphertext.

7. Conclusions and Future Work

This paper introduced a new non-interactive integer comparison protocol using TFHE with programmable bootstrapping. This protocol was tested with 128-bit security and scaled linearly with the input bit length. As an application, we developed an efficient protocol for the private evaluation of decision trees. The evaluation is done in a non-interactive manner, where there is no interaction between the client and server. The model owner can delegate the evaluation to a third-party evaluator, and the client can be offline after sending the feature vector to the evaluator. We experimented with widely used real datasets from the UCI machine learning repository and compared them with the existing protocols. The protocol can be extended to perform more complex inferences using random forest classification.

An important future extension to the protocol is to support ensemble and gradient boosting methods. This extension is possible if we can extend the protocol with homomorphic operations, such as division on encrypted numbers. Our solution evaluates the tree encrypted with the client’s public key. Therefore, it requires a key distribution mechanism to share the client’s public key with the model owner. An exciting direction for future work is to use multi-key homomorphic encryption [28,29] to encrypt the tree and the feature vector with different keys. This technique eliminates the need for key distribution between the client and the model owner.