## 4 HeFUN: An iLHE-Based SNNI Framework
### Hefun  
We first present the intuition behind how can we hide \(\mathbf{x}^{(i)}\overset{? }{=}0\) from \(\mathcal{C}\). **Intuition. ** To tackle the issues of leaking \(\mathbf{x}^{(i)}\overset{? }{=}0\) to \(\mathcal{C}\), \(\mathcal{S}\) implements a random permutation on \(\mathbf{x}^{(i)}\) prior to executing the HeReLU protocol. Then, \(\mathbf{x}^{(i)}\) cannot determine the original position of a value, concealing whether the actual value of a particular slot is zero. Thus, \(\mathcal{C}\) only learns the number of zero values, which can be obscured by adding dummy elements. However, in SNNI, \(\mathbf{x}^{(i)}\) is in encrypted form, i.e., \(\left[\mathbf{x}^{(i)}\right]\). Unfortunately, permutation on \(\left[\mathbf{x}^{(i)}\right]\) is a challenging task. This is because the permutation requires swapping slots in the ciphertext, which requires numerous homomorphic rotations--a costly operator [11; 15]. This approach is not practical when the number of neurons in NN layers is large. The section below describes how we can overcome this challenge. Given a vector \(\mathbf{x}\in\mathbb{R}^{n}\), and \(\pi\) is a permutation over \(\{1,\dots,n\}\), let \(\pi(\mathbf{x})\) denote the permutation \(\mathbf{x}^{\prime}\)s slots according to \(\pi\), i.e., the \(i\)th slot in the permuted vector (\(\pi(\mathbf{x})\)) is \(\mathbf{x}_{\pi(i)}\) (instead of \(\mathbf{x}_{i}\)). Given a matrix \(\mathbf{W}\), we use \(\pi(\mathbf{W})\) to denote permutation of \(\mathbf{W}\) by columns, i.e., the \(i\)th column in the permuted matrix (\(\pi(\mathbf{W})\)) is \(\mathbf{W}_{\pi(i)}\) (instead of \(\mathbf{W}_{i}\)). Here are some obvious facts:  
* Permuting two vectors with the same permutation preserves element-wise addition: \[\pi(\mathbf{x})+\pi(\mathbf{y})=\pi(\mathbf{x}+\mathbf{y})\] (3)
* Permute two vectors with the same permutation and preserve their dot product: \[\pi(\mathbf{x})\cdot\pi(\mathbf{y})=\mathbf{x}\cdot\mathbf{y}\] (4)
* Permute a vector, and every column in a matrix with the same permutation preserves the vector-matrix product: \[\pi(\mathbf{x}).\pi(\mathbf{W},col)=\mathbf{x}.\mathbf{W}\] (5) where \(\pi(\mathbf{W},col)\) denotes that we apply the permutation \(\pi\) to every column of \(\mathbf{W}\). * In vector-matrix multiplication, (only) permutation of a matrix by column leads to the same permutation on the result. \[\mathbf{x}.\pi(\mathbf{W})=\pi(\mathbf{x}.\mathbf{W})\] (6)  
Proof. : Proof of Property (3): \(\pi(\mathbf{x})+\pi(\mathbf{y})=(\mathbf{x}_{\pi(1)}+\mathbf{y}_{\pi(n)},\dots,\mathbf{x}_{\pi(n) }+\mathbf{y}_{\pi(n)})=\pi(\mathbf{x}+\mathbf{y})\)Proof of Property (4):  
\[\pi(\mathbf{x})\cdot\pi(\mathbf{y}) =\sum_{i=1}^{n}\mathbf{x}_{\pi(i)}\mathbf{y}_{\pi(i)}\] \[=\sum_{i=1}^{n}\mathbf{x}_{i}\mathbf{y}_{i}\] \[=\mathbf{x}\cdot\mathbf{y}\]  
Proof of Property (5):  
\[\pi(\mathbf{x}).\pi(\mathbf{W},col) =\left[ \begin{array}{ccc}\mathbf{\longrightarrow}&\pi(\mathbf{x})&\mathbf{ \longrightarrow}\end{array} \right]\cdot \begin{bmatrix}\mathbf{|}&&\mathbf{|}\\ \pi(\mathbf{W}_{1})&\vdots&\pi(\mathbf{W}_{n})\\ \mathbf{|}&&\mathbf{|}\end{bmatrix} \] \[=(\pi(\mathbf{x})\cdot\pi(\mathbf{W}_{1}),\ldots,\pi\mathbf{x}\cdot\pi(\mathbf{W} _{n}))\] \[=(\mathbf{x}\cdot\mathbf{W}_{1},\ldots,\mathbf{x}\cdot\mathbf{W}_{n})\qquad\text{ (Property (\ref{eq:1}))}\] \[=\mathbf{x}\cdot\mathbf{W}\]  
Proof of Property (6):  
\[\mathbf{x}\cdot\pi(\mathbf{W}) =\mathbf{x}\Big{(}\mathbf{W}_{\pi(1)}^{T},\ldots,\mathbf{W}_{\pi(n)}^{T} \Big{)}\] \[=\Big{(}\mathbf{x}\cdot\mathbf{W}_{\pi(1)}^{T},\ldots,\mathbf{x}\cdot\mathbf{W}_ {\pi(n)}^{T}\Big{)}\] \[=\pi\Big{(}\mathbf{x}\cdot\mathbf{W}_{1}^{T},\ldots,\mathbf{x}\cdot\mathbf{W}_ {n}^{T}\Big{)}\] \[=\pi(\mathbf{x}\cdot\mathbf{W})\]  
Based on Property (6) and the fact that \(\mathbf{x}=\mathbf{x}\cdot\mathbf{I}\), where \(\mathbf{I}\) is the identity matrix, we can achieve permutation of \(\mathbf{x}\) by just permuting identity matrix \(\mathbf{I}\), namely \(\mathbf{x}\cdot\pi(\mathbf{I})=\pi(\mathbf{x}\cdot\mathbf{I})=\pi(\mathbf{x})\).