Approximating homomorphic evaluation: an analysis of approximation and optimisation techniques for accelerating homomorphic encryption

It is shown that skipping higher order terms in the logistic function provides an acceptable performance trade-off. Depth reduction improves both speed and accuracy of the Taylor-approximated exponential function.<br><br>Lazy relinearisation was also investigated; relinearisation usually occurs after every homomorphic multiplication to reduce ciphertext size, keeping ciphertext sizes manageable. Not performing relinearisation at the highest depth provides a speed-up of around 3% (logistic function) and 7% (exponential function).

Recommended pre-processing approximation techniques are combined with lazy relinearisation and analysed for HE function evaluation. Depending on how many depths are relinearised, the run-time speed-up is between 9-18% (logistic function) and between 8-16% (exponential function). Not relinearising at the highest depth is recommended as this has minimal impact on accuracy.<br><br>Lastly, the aforementioned pre-processing and algorithmic optimisation approaches are applied to activation functions used in Convolutional Neural Networks (CNNs).

Task skipping and depth reduction as well as Newton-Raphson division, where suitable, are applied to homomorphically-friendly approximations of the Rectified Linear Unit (ReLU), Softmax and hyperbolic tangent functions. The most suitable ReLU approximation, and AC-adapted versions, are applied as a proof of concept to two CNNs. The research in this thesis shows that optimisations at the pre-processing and algorithmic stages of homomorphic evaluation are promising for real-world, efficient HE applications.<br><br>