Addition Circuit optimization Using Carry-Lookahead and SIMD for Homomorphic Encryption

Homomorphic encryption can be applied to cloud computing to solve the privacy problem. However, it is not practical because of lack of efficiency. So, methods to reduce the high computational cost of HE is needed. In this paper, we introduce a novel way to evaluate addition circuit under homomorphic encryption circumstances. We apply Ladner-Fischer Carry-Lookahead Addition (CLA) circuit that performs best among all kinds of CLA structure. Moreover, we use Single-Instruction-Multiple-Data (SIMD) technique by organizing several bits packed in one plaintext to further improve performance in the situation where the numbers are larger. This method leads to a reduction of depth and the number of multiplications, achieves 8% increase in speed for 16-bit circuit without SIMD and 63% for 64-bit circuit with SIMD.