Algorithm Complexity and Security. The asymptotic complexity of our network architecture search algorithm is \(\mathcal {O}(n)\) , which means that \(n\)  mobile modules need to be evaluated. As Figure REF  shows, to build a HE-friendly network architecture based on SqueezeNet, totally four inferences have to be done on an encrypted CIFAR-10 image. The search overhead of Algorithm REF  is \(\sum _{i=1}^{n}Cost\_O^{\prime }_i\) , where \(O^{\prime }_i\)  is the \(i_{th}\)  network candidate. Our search algorithm is done offline before the PPNN is deployed on the server, so our algorithm does not expose any private information of input data. We maintain the same security level as [1]}, [2]}.
