# Non-Interactive Decision Trees and Applications with Multi-Bit TFHE
## 3 Preliminaries
### Fully Homomorphic Encryption
\tag{3}\]  
for a random vector \((a_{1},\ldots,a_{n})\stackrel{{\$}}{{\leftarrow}}\mathbb{T}_{q}^{n}\) and a small noise \(e\leftarrow\hat{\chi}\)
**Decrypt\({}_{\textbf{sk}}(\mathbf{c})\)**: To decrypt \(c=(a_{1},\ldots,a_{n},b)\), use private key \(s=(s_{1},\ldots,s_{n})\), compute  
\[\mu^{*}=b-\sum_{j=1}^{n}s_{j}\cdot a_{j} \tag{4}\]and return \[\mu=\frac{\lfloor p\mu^{*}\rceil\bmod p}{p}\] (5)
**Addition of ciphertexts**: Let \(c_{1}\leftarrow\mathrm{TLWE}_{\mathrm{s}}(\mu_{1})\) and \(c_{2}\leftarrow\mathrm{TLWE}_{\mathrm{s}}(\mu_{2})\) be respective TLWE encryptions of \(\mu_{1}\) and \(\mu_{2}\), i.e., \(c_{1}=(a_{1},\ldots,a_{n},b)\), \(c_{2}=\left(a_{1}^{\prime},\ldots,a_{n}^{\prime},b^{\prime}\right)\), \(b^{\prime}=\sum_{j=1}^{n}s_{j}\cdot 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 \(\mathrm{TLWE}_{\mathrm{s}}\left(\mu\right)\) where \(\mu\in\mathcal{P}\). By multiplying \(K\) with every vector component of \(c\), we obtain \(\mathrm{TLWE}_{\mathrm{s}}\left(K\cdot\mu\right)\). If \(c=(a_{1},\ldots,a_{n},b)\in\mathbb{T}_{q}^{n+1}\), then \[K\cdot c=(K\cdot a_{1},\ldots,K\cdot a_{n},K\cdot b).\] (7) provided that the resulting noise is kept small. **Bootstrapping**: In [PERSON]'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\mathrm{TLWE}_{\mathrm{s}}(\mu)\in\mathbb{T}_{q}^{n+1}\) encrypted with secret key \(s=(s_{1},\ldots,s_{n})\in\mathbb{B}^{n}\) is done in three steps. * \(c^{\prime}\leftarrow\mathrm{BlindRotate}_{\mathrm{bsk}}(c)\) This operation returns a ring (torus polynomials) LWE ciphertext in \(\mathbb{T}_{N,q}[X]^{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}(c^{\prime})\) This operation extracts the constant coefficient of \(c^{\prime}\), resulting in an LWE ciphertext in \(\mathbb{T}_{q}^{N+1}\)
* \(c^{\prime\prime}\leftarrow\mathrm{KeySwitch}_{\mathrm{bsk}}(c^{\prime})\) 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}\rightarrow\mathbb{T}_{p}\) and a noisy ciphertext \(c\leftarrow\mathrm{TLWE}_{\mathrm{s}}(\mu)\); programmable bootstrapping outputs a new ciphertext \(c^{\prime}\leftarrow\mathrm{TLWE}_{\mathrm{s}}(f(\mu))\), 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].