## 3 Cryptographic Preliminaries
### Homomorphic Encryption  
Homomorphic encryption (HE) is a distinctive form of encryption that permits computation on ciphertexts without the need for decryption, thereby ensuring data confidentiality, even within untrusted environments. Current HE schemes vary, particularly concerning the data types they accommodate. For instance, integer-based HE schemes facilitate operations on integer vectors, whereas real number-based HE schemes cater to computations involving real vectors. Although our proposed frameworks are compatible with both types, our primary focus is on the CKKS scheme [10], which is prevalent in SNNI due to its inherent compatibility with real numbers. In CKKS, a ciphertext takes the form of \((b,a)\in\mathcal{R}_{q}^{2}\), with \(q\) being a prime number. The scheme enables the encryption of a vector consisting of \(N/2\) real numbers into \(N/2\) slotsof a single ciphertext, thanks to the batching technique [10]. CKKS facilitates homomorphic operations, applying identical computations to each slot concurrently. In particular, if we represent the ciphertext of a vector \(\mathbf{x}\in\mathbb{R}^{N/2}\) as \([\mathbf{x}]\), we can describe homomorphic operators as follows: \([\mathbf{x}]\oplus[\mathbf{y}]=[\mathbf{x}+\mathbf{y}]\), \([\mathbf{x}]\oplus\mathbf{y}=[\mathbf{x}+\mathbf{y}]\), \([\mathbf{x}]\otimes[\mathbf{y}]=[\mathbf{x}\times\mathbf{y}]\), \([\mathbf{x}]\otimes\mathbf{y}=[\mathbf{x}\times\mathbf{y}]\), and \(\mathsf{Rotate}([\mathbf{x}],\mathbf{r})=[\langle\mathbf{x}\rangle_{r}]\). **LHE-based SNNI** Leveraging the operators supported by homomorphic encryption, numerous LHE-based SNNI frameworks have been developed (as can be seen in Table 1). In NNs, two common operators that can be efficiently evaluated using HE schemes are matrix multiplication and convolution. A comprehensive explanation of these methods is beyond the scope of this paper; for detailed insights, we direct readers to [58; 59; 60; 61]. We briefly overview the operators that we used in this paper. Given a vector \(\mathbf{x}\) and a matrix \(\mathbf{W}\), the vector-matrix multiplication can be efficiently evaluated in the HE scheme, i.e., \([\mathbf{x}]\odot\mathbf{W}=[\mathbf{x}\cdot\mathbf{W}]\), where \(\odot\) denotes homomorphic (encrypted) vector and (plain) matrix multiplication. In the context of convolution, given an input image \(\mathbf{x}\) (we repurpose the symbol \(\mathbf{x}\), typically used for vectors, to represent images in this context) and a filter \(\mathbf{W}\) (for clarity, we presume the filter \(\mathbf{W}\) possesses a singular map; in scenarios with multiple maps, the operation can be repeated accordingly), we have \([\mathbf{x}]\oplus\mathbf{W}=[\mathbf{x}\ast\mathbf{W}]\), where \(\ast\) and  denote convolution and homomorphic convolution, respectively. In this paper, we employ convolution based on [60], in which convolution between an encrypted vector and a plain matrix can be computed based on element-wise operators in HE schemes. Additionally, it is noteworthy that the dot product is essentially a specific instance of matrix multiplication, illustrated as \([\mathbf{x}]\odot\mathbf{y}=[\mathbf{x}.\mathbf{y}]\). **LHE**. In CKKS, each ciphertext has a non-negative integer, termed as level, representing the capacity for homomorphic multiplication operations. After each homomorphic multiplication, the level is reduced by one through the rescaling procedure. After several multiplications, if the level \(\ell\) reduces to zero, the ciphertext can no longer support further multiplication operations. The initial setting of \(\ell\) is crucial and is determined based on the expected number of multiplications. For deep NN, \(\ell\) is large, resulting in a corresponding increase in the CKKS parameters, which subsequently leads to computational overheads. Another solution to expend ciphertext's computational capacity is the bootstrapping procedure [13] that turns the zero-level ciphertext into a higher-level ciphertext, thereby enabling further homomorphic multiplications.