Approximating homomorphic evaluation

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

Abstract

Homomorphic encryption (HE) allows computations on encrypted data, making it desirable for use in privacy-preserving data analytics. However, HE function evaluation is computationally intensive. Applying approximate computing (AC) techniques to homomorphic data analysis maximises performance. This thesis contributes to the development of real-time homomorphic evaluation by using approximate computing techniques for homomorphic evaluation of polynomially-represented non-linear functions.

At the pre-processing stage for homomorphic evaluation, AC techniques of task skipping and depth reduction are applied to the polynomial approximation of non-linear functions using the approximate HE scheme, CKKS, and implemented in SEAL and PALISADE. 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.

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.

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.

Date of Award	Jul 2024
Original language	English
Awarding Institution	Queen's University Belfast
Sponsors	Northern Ireland Department for the Economy
Supervisor	Ciara Rafferty (Supervisor) & Maire O'Neill (Supervisor)