## 4 HeFUN: An iLHE-Based SNNI Framework
### Hefun
Based on this observation, we propose a novel algorithm, i.e., HePerm, to permute slots inside a ciphertext without the rotation operator. The algorithm is shown in Protocol 4. The correctness of the protocol is straightforward, as below. \[[\mathbf{x}]\odot\pi(\mathbf{I}) =[\mathbf{x}\cdot\pi(\mathbf{I})]\qquad\text{(Homomorphic property)}\] \[=[\pi(\mathbf{x}\cdot\mathbf{I})]\qquad\text{(Property (\ref{eq:1}))}\] \[=[\pi(\mathbf{x})]\]  
```
0: ciphertext \([\mathbf{x}]\), permutation \(\pi\)
0:\([\pi(\mathbf{x})]\)
1:\([\pi(\mathbf{x})]=[\mathbf{x}]\odot\pi(\mathbf{I})\)
2:return\(\mathbf{x}\)
```  
**Protocol 4**HePerm: Homomorphic permutation  
The HePerm algorithm allows us to permute any (encrypted) intermediate layers, i.e., \(\Big{[}\mathbf{x}^{(i)}\Big{]}\), prior to executing the HeReLU protocol. Hence, we can hide \(\mathbf{x}^{(i)}\overset{? }{=}0\) from \(\mathcal{C}\). Suppose each intermediate layer \(\Big{[}\mathbf{x}^{(i)}\Big{]}\) (before the ReLU layer) is permuted by a permutation \(\pi^{(i)}\). Then, the value obtained by \(\mathcal{S}\) (after running HeReLU) is \(\left[\pi^{i}(\mathbf{h}^{(i)})\right]\) (not \(\left[\mathbf{h}^{(i)}\right]\)). This value will be the input for the next linear layer. Therefore, to compute the next linear layer, \(\mathcal{S}\) first needs to _unpermute_\(\left[\pi^{i}(\mathbf{h}^{(i)})\right]\). To do so, \(\mathcal{S}\) runs HePerm on \(\left[\pi^{i}(\mathbf{h}^{(i)})\right]\) and \({\pi^{(i)}}^{-1}\), which results in \(\left[{\pi^{(i)}}^{-1}(\pi^{(i)}(\mathbf{h}^{(i)}))\right]=\left[\mathbf{h}^{(i)}\right]\). Then, \(\mathcal{S}\) can homomorphically evaluate the next linear layer on \(\left[\mathbf{h}^{(i)}\right]\), which results in \(\left[\mathbf{x}^{(i+1)}\right]\). Finally, \(\mathcal{S}\) can run HePerm to permute \(\left[\mathbf{x}^{(i+1)}\right]\) using permutation \(\pi^{(i+1)}\). Interestingly, for a fully connected layer, we can achieve permutation without the need of HePerm. This is because the fully connected layer can be homomorphically evaluated directly on \(\left[\pi^{(i)}(\mathbf{h}^{(i)})\right]\) by permuting each column in \(\mathbf{W}^{(i+1)}\) by \(\pi^{(i)}\) (based on Property (5)), namely \(\left[\pi^{(i)}(\mathbf{h}^{(i)})\right]\odot\pi^{(i)}(\mathbf{W}^{(i+1)},col)\oplus \mathbf{b}^{(i+1)}=\left[\pi^{(i)}(\mathbf{h}^{(i)})\cdot\pi^{(i)}(\mathbf{W}^{(i+1)},col )+\mathbf{b}^{(i+1)}\right]=\left[\mathbf{h}^{(i)}\cdot\mathbf{W}^{(i+1)}+\mathbf{b}^{(i+1)}\right]\). Therefore, we achieve permutation _for free_ in fully connected layers. Assume that \(\mathcal{S}\) chooses \(L\) random permutations \(\pi^{(1)},\ldots,\pi^{(L)}\) corresponding to layer 1 to layer \(L\), respectively. Notably, \(\pi^{(1)},\ldots,\pi^{(L)}\) can be chosen offline by \(\mathcal{S}\) before the inference process. Hence, we can save the inference time. The details of HeFUN are shown in Protocol 5, in which \(FC\) means fully connected layer and \(Conv\) means convolution layer. HeFUN's security follows Lemma 3. We now provide an analysis of the correctness and security of the protocol. ```
1:Input\(\mathcal{C}\): Data \(\mathbf{x}\), secret key \(sk\)
2:Input\(\mathcal{S}\): public key \(pk\), trained weights and biases \((\mathbf{W}_{i},\mathbf{b}_{i})\) with \(i=\overline{1,n}\)
3:Output\(\mathcal{C}\): \(z=f_{L}(\mathbf{W}_{L},f_{L-1}(\ldots f_{1}(\mathbf{W}_{1},\mathbf{x},\mathbf{b}_{1})),\mathbf{b} _{L})\), where \(f_{i}\) is ReLU function. 4:\(\



**Lemma 3**: HeFUN _protocol is secure in the semi-honest model._

**Proof. Correctness. ** We first consider the fully connected layers. At line 12, we have:

\[=(\mathbf{x}\cdot\mathbf{W}_{1},\ldots,\mathbf{x}\cdot\mathbf{W}_{n})\qquad\text{ (Property (\ref{eq:1}))}\]0 \[=\left[



in this section, we compare our proposed approach, HeFUN, with HE-MPC hybrid-based frameworks and LHE-based frameworks.