# Non-Interactive Decision Trees and Applications with Multi-Bit TFHE
## 3 Preliminaries
### 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. [PERSON] [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(sk)\). Given a ciphertext \(ct\) corresponding to encryption of plaintext \(m\), then \(Dec_{sk}(ct)=m\). Let \(F(x)=Dec_{x}(ct)\) be a function which decrypts a ciphertext given a secret key \(x\). Let \(ct^{\prime}\) be the decryption using the bootstrapping key \(bk\). \[ct^{\prime}=F(bk)=F(Enc(sk))=Enc(F(sk))=Enc(Dec_{sk}(ct))=Enc(m) \tag{1}\]  
Hence, \(ct^{\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 (1)**: 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}\big{(}0,\sigma^{2}\big{)}\) over \(\mathbb{R}\) is used to create a discretized error distribution \(\hat{\chi}\) over \(q^{-1}\mathbb{Z}\). The private key \(sk\) is sampled uniformly at random from \(\mathbb{B}^{n}\), i.e., \(sk=(s_{1},\ldots,s_{n})\stackrel{{\$}}{{\leftarrow}}\mathbb{B}^{n}\). The plaintext space is \(\mathcal{P}=\mathbb{T}_{p}\subset\mathbb{T}_{q}\). **Encrypt\({}_{\textbf{sk}}(\mathbf{\mu})\)**: The encryption of \(\mu\in\mathcal{P}\) is given by  
\[c\leftarrow\text{TLWE}_{s}(\mu)=(a_{1},\ldots,a_{n},b)\in\mathbb{T}_{q}^{n+1} \tag{2}\]  
with  
\[\left\{ \begin{array}{l}\mu^{*}=\mu+e\\ b=\sum_{j=1}^{n}s_{j}\cdot a_{j}+\mu^{*}\end{array} \right.