## 4 HeFUN: An iLHE-Based SNNI Framework
### HeReLU: Homomorphic ReLU Evaluation Protocol
**Correctness. ** The correctness of the protocol is straightforward. We first prove the correctness of computing \([\text{sign}(\mathbf{x})]\). At line 6, we have:  
\([\text{sign}(\mathbf{x}\times\mathbf{r})]\otimes\text{sign}(\mathbf{r})=[\text{sign}(\mathbf{x }\times\mathbf{r})\times\text{sign}(\mathbf{r})]=[\text{sign}(\mathbf{x})]\). Now, we prove the correctness of computing \([\text{ReLU}(\mathbf{x})]\). At line 7, we have:  
\(\frac{1}{2}\otimes([\mathbf{x}]\oplus[\mathbf{x}]\otimes[\text{sign}(\mathbf{x})])=\left[ \frac{1}{2}(\mathbf{x}+\mathbf{x}\times\text{sign}(\mathbf{x}))\right]=\left[\frac{1}{2}( \mathbf{x}+\mathbf{x}\times\text{sign}(\mathbf{x}))\right]=\left[\frac{\text{ReLU}(\mathbf{x} )}{2}\right]\) (Formula (2)). **Security. ** We now consider two cases as following Definition 1, i.e., corrupted \(\mathcal{C}\) and corrupted \(\mathcal{S}\). **Corrupted \(\mathcal{C}\)**: \(\mathcal{C}\)'s view is \(\text{View}_{\mathcal{C}}=(sk,[\mathbf{x}\times\mathbf{r}])\). Given \((sk)\), we build a simulator \(\text{Sim}_{\mathcal{C}}\) as below:  
1. Pick \(\mathbf{x}^{\prime}\leftarrow\mathbb{R}^{n}\);
2. Output \((sk,[\mathbf{x}^{\prime}])\). Even \(\mathcal{C}\) can decrypt \([\mathbf{x}\times\mathbf{r}]\) and obtain \(\mathbf{x}\times\mathbf{r}\), because \(\mathbf{r}\) was randomly chosen by \(\mathcal{S}\); hence, from the view of \(\mathcal{C}\): \(\mathbf{x}\times\mathbf{r}\approx_{c}\mathbf{x}^{\prime}\Leftrightarrow(sk,[\mathbf{x}\times \mathbf{r}])\approx_{c}(sk,[\mathbf{x}^{\prime}])\Leftrightarrow\text{View}_{\mathcal{ C}}\approx_{c}\text{Sim}_{\mathcal{C}}\). **Corrupted \(\mathcal{S}\)**: \(\mathcal{S}\)'s view is \(\text{View}_{\mathcal{S}}=(pk,[\mathbf{x}],[\text{sign}(\mathbf{x}\times\mathbf{r})])\). Given \((pk,[\mathbf{x}],[\text{ReLU}(\mathbf{x})])\), we build a simulator \(\text{Sim}_{\mathcal{S}}\) as below:  
1. Pick \(\mathbf{s}\leftarrow\{-1,0,1\}^{n}\); \begin{table}
\begin{tabular}{c c c} \hline \hline \(\text{sign}(\mathbf{r})\) & \(\text{sign}(\mathbf{x}\times\mathbf{r})\) & \(\text{sign}(\mathbf{x})\) \\ \hline \(1\) & \(1\) & \(1\) \\ \(1\) & \(0\) & \(0\) \\ \(1\) & \(-1\) & \(-1\) \\ \hline \(-1\) & \(1\) & \(-1\) \\ \(-1\) & \(0\) & \(0\) \\ \(-1\) & \(-1\) & \(1\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Logic table for \(\text{sign}()\) function. 2. Output \((pk,[x],[s])\). Based on the semantic security of HE schemes, it is obvious that \((pk,[x],[\mathsf{sign}({\mathbf{x}}\times{\mathbf{r}})])\approx_{c}(pk,[x],[s]) \Leftrightarrow\mathsf{View}_{\mathcal{S}}\approx_{c}\mathsf{Sim}_{S}\). The idea of computing the ReLU function is based on Equation (2), i.e., \(\mathsf{ReLU}(x)=\frac{1}{2}(x+x.\mathsf{sign}(x))\). This equation requires a division by 2, which is equivalent to multiplying by 0.5 in CKKS. However, the division is not supported by almost all other schemes that work on integers in the ring \(\mathbf{Z}_{n}\), such as BFV [23] and BGV [68]. In those schemes, the division by 2 can be replaced by multiplying by \(2^{-1}\), where \(2^{-1}\) is the inverse of 2 in \(\mathbb{Z}_{n}\). By doing so, our protocol can be compatible with both CKKS and other integer HE schemes. \(\mathsf{HeReLU}\) allows \(\mathcal{S}\) to obtain \([\mathsf{ReLU}({\mathbf{x}})]\) without leaking \({\mathbf{x}}\) to \(\mathcal{S}\) and \(C\). However, it leaks some unexpected information about \({\mathbf{x}}\) to \(\mathcal{C}\), namely, it leaks whether the \(i\)th slot in \({\mathbf{x}}\) is zero or not (we denote it by \({\mathbf{x}}\stackrel{{ 2}}{{=}}0\)). This leakage occurs at line 4 in Protocol 1. In particular, \(\mathcal{C}\) knows a slot \({\mathbf{x}}_{i}=0\) if the \(i\)th slot in \({\mathbf{x}}\times{\mathbf{r}}\) is 0 (as \({\mathbf{r}}\
eq 0\)). We address the information leakage by proposing a novel NN permutation. We detail this in Section 4.5.