Fast polynomial arithmetic for Somewhat Homomorphic Encryption operations in hardware with Karatsuba algorithm
Vincent Migliore, Maria Méndez Real, Vianney Lapôtre, Arnaud Tisserand, Caroline Fontaine, Guy Gogniat · 2016
Somewhat Homomorphic Encryption (SHE) schemes allow to carry out operations on data in the cipher domain. In a cloud computing scenario, personal information can be processed secretly, inferring a high level of confidentiality. Most practical Somewhat Homomorphic Encryption (SHE) schemes require the implementation of fast polynomial arithmetic, that is why hardware accelerators usually target the FFT/NTT algorithm. This paper proposes a co-design hardware/software approach to accelerate SHE using Karatsuba algorithm. Depending on the needs, Karatsuba algorithm allows to implement additional computations to the hardware in order to reduce software computation time. Our accelerator is designed to speed up arithmetic on degree 2560 polynomials with 125 bits coefficients. We provide 3 different approaches: An area efficient design, a balanced design, and a performance-oriented design. Our accelerator performs a polynomial multiplication in respectively 2.46 ms, 1.70 ms and 1.24 ms, and a relinearization operation in 2.28 ms, 1.53 ms and 1.1 ms, while a functionally equivalent design using the FFT [1] performs the multiplication in 1.96 ms and the relinearization in 4.79 ms for hardware resources consumption equivalent to the balanced design.