# Non-Interactive Decision Trees and Applications with Multi-Bit TFHE
## 4 Private Comparison of Integers
### 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 \(SAB_{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 \(\bar{\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. Figure 5: Encrypted nibble comparator: HE-Nibble-Eq and HE-Nibble-Gt. ```
Input: Condition S, Input A, Input B, Zero \(\emptyset\) Output:\(A\) if Condition \(S\equiv 1\), \(B\) if \(S\equiv 0\) \(input\leftarrow[S,S,S,S,A,A,B,\emptyset]\) \(sum\leftarrow\textsc{Parallel-Prefix-Sum}(input)\) \(result\leftarrow\textsc{Pbs}(sum,f_{MUX}(x))\) \(result\leftarrow\textsc{Ks}(result)\) returnresult
```  
**Algorithm 1** HE-Mux  
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}(x)\) that evaluates the following truth table of the multiplexer shown in Figure 3.  
\[f_{MUX}(x)= \begin{cases}0&x=000_{2}\\ 0&x=001_{2}\\ 1&x=010_{2}\\ 1&x=011_{2}\\ 0&x=100_{2}\\ 1&x=101_{2}\\ 0&x=110_{2}\\ 1&x=111_{2}\end{cases}  \tag{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.