Speeding Up Fully Homomorphic Encryption
Like machine learning, much of our existing Fully Homomorphic Encryption (FHE) methods use vector and matrix operations. Unfortunately, our generalised CPUs are not well set up for these operations, especially in the way that registers are setup. With a GPU, we support complex operations within minimal clock operations, such as for matrix multiplication, rotation and addition.
Within FHE, use lattices, and where our binary values are represented as polynomials, such as where a point at (9,5,16) is represented by:
16x²+5x+9
We can then define a finite field for the polynomial with a (mod p) operation:
16x²+5x+9 (mod p)
Overall, FHE uses a LWE (Learning With Errors) approach [video]:
We thus need processors that can compute with matrices in an efficient way. For this, we can understand the performance of GPUs and CPUs from this paper [here][1]:
For this, the researchers compared the 4.2GHz Ryzen7 CPU against the RTX3060Ti and GTX1080 GPU devices:
In this tests, we see that multiplication and rotation are the most intensive tasks. The variation relates to the n and log2(q). With n we have the sizes of the vector and matrices, and for log2(q) with have the modulus value (2^q). We see that for homomorphic adding with n=2¹⁴ gives 233 microseconds for SEAL on a CPU, and 12.3 microseconds on a GPU. This gives a 18.94 times improvement between the GPU and the CPU:
For multiplication, we see an even better improvement, and where the GPU is around 63.4 times faster. When it comes to power consumption, we see that for n=2¹⁴, the power consumption for a GPU is 60.8 W for 100 cycles, and it is 44.61 W for the GPU. This means that the GPU consumes around 25% less energy than the CPU.
Conclusions
Like it or not, our generalised CPUs just don’t match well to the requirements for machine learning and homomorphic encryption. For this, we need to turn to GPUs and ASIC devices to improve the performance. From the tests, we can see that the speed is around x50.
Here are some SEAL examples:
https://asecuritysite.com/seal
and for OpenFHE:
and here:
and here:
References
[1] Özcan, A. Ş., Ayduman, C., Türkoğlu, E. R., & Savaş, E. (2023). Homomorphic encryption on GPU. IEEE Access, 11, 84168–84186.