Fast Homomorphic Evaluation of Deep Discretized Neural Networks
F. Bourse, M. Minelli, M. Minihold, and P. Paillier.

The rise of machine learning as a service multiplies scenarios where one faces a privacy dilemma: either sensitive user data must be revealed  to  the  entity  that  evaluates  the  cognitive  model  (e.g.,  in  the Cloud),  or  the  model  itself  must  be  revealed  to  the  user  so  that  the evaluation can take place locally. Fully Homomorphic Encryption (FHE) offers an elegant way to reconcile these conflicting interests in the Cloud-based scenario and also preserve non-interactivity. However, due to the inefficiency  of  existing  FHE  schemes,  most  applications  prefer  to  use Somewhat  Homomorphic  Encryption  (SHE),  where  the  complexity  of the computation to be performed has to be known in advance, and the efficiency of the scheme depends on this global complexity. In this paper, we present a new framework for homomorphic evaluation of neural networks, that we call FHE–DiNN, whose complexity is strictly linear  in  the  depth  of  the  network  and  whose  parameters  can  be  set beforehand. To obtain this scale-invariance property, we rely heavily on the bootstrapping procedure. We refine the recent FHE construction by Chillotti et al.(ASIACRYPT  2016)  in  order  to  increase  the  message space and apply the sign function (that we use to activate the neurons in the network) during the bootstrapping. We derive some empirical results, using TFHE library as a starting point, and classify encrypted imagesfrom the MNIST dataset with more than 96% accuracy in less than 1.7seconds. Finally, as a side contribution, we analyze and introduce some variations to the bootstrapping technique of Chillotti et al. that offer an improvement in efficiency at the cost of increasing the storage requirements.