## 4 Analysis  
### Security Analysis  
This section provides the overall security analysis of our privacy-preserving CNN inference protocol. For any \(\kappa\)-bit message \(\mathcal{M}\), Theorem 1 states that the probability for a probabilistic polynomial time (PPT) adversary \(\mathcal{A}\) to output a correct guess of \(\mathcal{M}\) is negligible. Theorem 1: _Given the ciphertext \(\mathcal{C}=x_{i}+\mathbf{r}_{i}\) of a \(\kappa\)-bit message \(\mathcal{M}=x_{i}\) generated using iPPSP, the probability for a PPT adversary \(\mathcal{A}\) to output a correct guess for \(\mathcal{M}\) follows:_  
\[\Pr[(\mathcal{M}^{*}=\mathcal{M})|\mathcal{C}]-\Pr[\mathcal{M}^{*}=\mathcal{M }]\leq\epsilon,\]  
_where \(\epsilon=\text{negl}(\cdot)\) is a negligible function regarding the security parameter \(\lambda\), \(\mathcal{M}^{*}\) is the guess for \(\mathcal{M}\) made by \(\mathcal{A}\), and \(\Pr[\mathcal{M}^{*}=\mathcal{M}]\) denotes the probability that the adversary \(\mathcal{A}\) makes a correct guess on \(\mathcal{M}\)._  
Proof: Given a \(\kappa\)-bit input \(x_{i}\), iPPSP encrypts it with an \(\eta\)-bit random number \(\mathbf{r}_{i}\) generated by padding \(T\) random numbers of \(l\)-bit with a secure PRG, which indicates that the distribution of \(\mathbf{r}_{i}\) should be indistinguishable from uniform. To make a correct guess on \(\mathcal{M}\) without ciphertext, \(\mathcal{A}\) has \(Pr[\mathcal{M}^{*}=\mathcal{M}]=\frac{1}{2^{\kappa}}\). Given the ciphertext \(\mathcal{C}=x_{i}+\mathbf{r}_{i}\), \(\mathcal{C}\in[0,2^{\kappa}+2^{\eta}]\), we differentiate two different cases to discuss the impact of the value of \(\mathcal{C}\). In the first case, \(2^{\kappa}\leq\mathcal{C}\leq 2^{\eta}\), we have \(\Pr[(\mathcal{M}^{*}=\mathcal{M})|\mathcal{C}]=\frac{1}{2^{\kappa}}\), since \(\mathcal{C}\) is indistinguishable from \(\mathbf{r}_{i}\) within the range. If \(\mathcal{C}<2^{\kappa}\) or \(\mathcal{C}>2^{\eta}\), then the distribution of \(\mathcal{C}\) will be affected by \(\mathcal{M}\) and the total possible inputs are reduced to \(\mathcal{C}\) or \(\mathcal{C}-2^{\eta}\). Hence, we have \(Pr[(\mathcal{M}^{*}=\mathcal{M})|\mathcal{C}]=\frac{1}{\mathcal{C}}\) or \(Pr[(\mathcal{M}^{*}=\mathcal{M})|\mathcal{C}]=\frac{1}{\mathcal{C}-2^{\eta}}\), respectively. In these cases, \(Pr[(\mathcal{M}^{*}=\mathcal{M})|\mathcal{C}]>\frac{1}{2^{\kappa}}\). Consider the second case when \(\mathcal{C}<2^{\kappa}\) or \(\mathcal{C}>2^{\eta}\); this happens only when the value of encryption pad \(\mathbf{r}_{i}\) is either too big or too small. More specifically, this happens only when \(\mathbf{r}_{i}>2^{\eta-\kappa}\) or \(\mathbf{r}_{i}<2^{\kappa}\). The probability of this event is  
\[Pr[\mathbf{r}_{i}>2^{\eta}-2^{\kappa}\cup\mathbf{r}_{i}<2^{\kappa}]=\frac{2\cdot 2^{ \kappa}}{2^{\eta}}=\frac{1}{2^{\eta-\kappa+1}}.\]  
Thus, we require \(\eta-\kappa-1\) to be greater than some pre-set security parameter \(\lambda\) (e.g., \(\eta-\kappa-1>\lambda=128\)). In this case, the probability \(Pr[\mathbf{r}_{i}>2^{\eta}-2^{\kappa}\cup\mathbf{r}_{i}<2^{\kappa}]=\frac{1}{2^{\eta- \kappa+1}}\) is negligible, we denote it as \(\epsilon(\lambda)\). Combining the two cases:  
\[Pr[(\mathcal{M}^{*}=\mathcal{M})|\mathcal{C}]\leq\frac{1}{2^{\kappa}}\cdot(1- \epsilon(\lambda))+\epsilon=\frac{1}{2^{\kappa}}+(1-\frac{1}{2^{\kappa}}) \cdot\epsilon(\lambda).\]  
Hence, we have  
\[Pr[(\mathcal{M}^{*}=\mathcal{M})|\mathcal{C}]-Pr[\mathcal{M}^{*}=\mathcal{M}] =\frac{1}{2^{\kappa}}+(1-\frac{1}{2^{\kappa}})\cdot\epsilon(\lambda)-\frac{1} {2^{\kappa}}=(1-\frac{1}{2^{\kappa}})\cdot\epsilon(\lambda)<\epsilon.\]  
which concludes the proof. Theorem 1 shows that. with appropriate system parameters. the ciphertext distribution cannot be distinguished with non-negligible probability by a PPT adversary. Since inputs of different CNN layers are independently encrypted, this property holds for the entire CNN inference task. Next, we show that our protocol is semantically secure under the chosen-plaintext attack (CPA) model.