  Machine learning as a service has been widely deployed to utilize deep neural
network models to provide prediction services. However, this raises privacy
concerns since clients need to send sensitive information to servers. In this
paper, we focus on the scenario where clients want to classify private images
with a convolutional neural network model hosted in the server, while both
parties keep their data private. We present FALCON, a fast and secure approach
for CNN predictions based on Fourier Transform. Our solution enables linear
layers of a CNN model to be evaluated simply and efficiently with fully
homomorphic encryption. We also introduce the first efficient and
privacy-preserving protocol for softmax function, which is an indispensable
component in CNNs and has not yet been evaluated in previous works due to its
high complexity. We implemented the FALCON and evaluated the performance on
real-world CNN models. The experimental results show that FALCON outperforms
the best known works in both computation and communication cost.
