## 4 Analysis
### Performance Analysis  
In this section, we provide the performance analysis both from a theoretical perspective and with experimental results. In our protocol, we consider input data and weights to be real numbers, and we use floating-point operations (FLOPs) to denote the addition and multiplication operation. We consider a typical network structure AlexNet for our analysis.  
**Computational Cost** Given a convolutional layer with \(H\ k\times k\times D\) kernels, stride \(\hat{s}\), and padding \(p\), for each input data of size \(\hat{n}\times\hat{n}\times D\), the output tensor is of size \(\hat{n}^{\prime}\times\hat{n}^{\prime}\times H\), where \(\hat{n}^{\prime}=\frac{\hat{n}-k+2p}{\hat{s}}\). An IoT device needs to performs \(\hat{n}^{2}DT\) FLOPs and \(\hat{n}^{\prime 2}HT\) FLOPs to encrypt and decrypt, respectively. In comparison, the computational cost for local execution is \(2H\hat{n}k^{2}\hat{n}^{\prime 2}\) FLOPs. Moreover, it is noteworthy that the operations in our protocol are addition/subtraction only, while the local execution contains \(H\hat{n}k^{2}\hat{n}^{\prime 2}\) multiplication and \(H\hat{n}k^{2}\hat{n}^{\prime 2}\) addition. For a fully-connected layer of input size \(\hat{n}\) and output size \(\hat{m}\), the IoT device needs to perform \(\hat{n}T\) FLOPs for encryption and \(\hat{m}T\) FLOPs for decryption. For comparison, the IoT device needs to perform \(\hat{n}\hat{m}\) FLOPs if it executes such a fully-connected layer on IoT device without outsourcing. It is worth noting that, when executing the fully-connected layer at local, the IoT device is performing \(\hat{n}\hat{m}\) multiplications, while, in our scheme, the IoT device only needs to preform \((\hat{m}+\hat{n})T\) additions on its end. Moreover, IoT devices need to handle non-linear computation locally. As depicted in Table 3, the comparison of IoT computation on linear layers between local executions and our protocol shows that our design dramatically reduces the overhead and achieves better performance in CNN inference tasks, considering that the parameter \(T\) is usually small for practical security.  
**Communication Cost** The communication cost of our protocol is mainly from the transmission of the ciphertext and the outputs of the convolutional layers and fully-connected layers. To outsource a convolutional layer with \(\hat{n}\times\hat{n}\times D\) inputs, the IoT device first encrypts it and sends the corresponding ciphertext, which is of size \(D\hat{n}^{2}\), to the edge device. Then, the edge device computes the expected scalar products and sends back the results, which are matrices of size \(\hat{n}^{\prime}\times\hat{n}^{\prime}\times H\). Regarding the fully-connected layer, the IoT device transmits encrypted message vectors of exactly the same dimensions as the plaintext ones, i.e., \(\hat{n}\)-dimensional input vectors and \(\hat{m}\)-dimensional output vectors. Thus, the total communication cost for a fully-connected layer would be \(\hat{m}+\hat{n}\).  
**Storage Overhead** To assure correct decryption, the scalar products of the secret keys and weights shall be pre-computed and stored in the IoT device as showed in Table 2. The pre-computation occurs only in the initialization phase, and once finished, there would be no extra storage overhead introduced during the offloading process. To outsource a convolutional layer with \(H\) kernels of \(k\times k\) matrices, the IoT device needs to store the scalar products with secret keys of size \(sk^{2}H\) for decryption, which is quite small for most CNN architecture where the kernel sizes are normally \(3\times 3\) or \(1\times 1\). Moreover, the IoT device also stores a constant-size key pool measured by \(s\). To outsource a fully-connected layer with \(\hat{n}\)-dimensional input and \(\hat{m}\)-dimensional output, the IoT device needs to store \(s\hat{n}\hat{n}\) as a decryption key.