Homomorphic WiSARDs: Efficient Weightless Neural Network training over
  encrypted data
Leonardo Neumann Antonio Guimarães Diego F. Aranha Edson Borin
The widespread application of machine learning algorithms is a matter of
increasing concern for the data privacy research community, and many have
sought to develop privacy-preserving techniques for it. Among existing
approaches, the homomorphic evaluation of ML algorithms stands out by
performing operations directly over encrypted data, enabling strong guarantees
of confidentiality. The homomorphic evaluation of inference algorithms is
practical even for relatively deep Convolution Neural Networks (CNNs). However,
training is still a major challenge, with current solutions often resorting to
lightweight algorithms that can be unfit for solving more complex problems,
such as image recognition. This work introduces the homomorphic evaluation of
Wilkie, Stonham, and Aleksander's Recognition Device (WiSARD) and subsequent
Weightless Neural Networks (WNNs) for training and inference on encrypted data.
Compared to CNNs, WNNs offer better performance with a relatively small
accuracy drop. We develop a complete framework for it, including several
building blocks that can be of independent interest. Our framework achieves
91.7% accuracy on the MNIST dataset after only 3.5 minutes of encrypted
training (multi-threaded), going up to 93.8% in 3.5 hours. For the HAM10000
dataset, we achieve 67.9% accuracy in just 1.5 minutes, going up to 69.9% after
1 hour. Compared to the state of the art on the HE evaluation of CNN training,
Glyph (Lou et al., NeurIPS 2020), these results represent a speedup of up to
1200 times with an accuracy loss of at most 5.4%. For HAM10000, we even
achieved a 0.65% accuracy improvement while being 60 times faster than Glyph.
We also provide solutions for small-scale encrypted training. In a single
thread on a desktop machine using less than 200MB of memory, we train over 1000
MNIST images in 12 minutes or over the entire Wisconsin Breast Cancer dataset
in just 11 seconds.