Efficient Comparison and Addition for FHE With Weighted Computational Complexity Model.

Homomorphic encryption (HE) has broad application prospects in the cloud computing security field. Efficient homomorphic computations of primitive circuits are critical for the applications of HE. However, existing implementation methods over plaintext do not fit well with those over ciphertext. To address this issue, a concise evaluation model is proposed to compare different implementation methods, using weighted computational complexity (WCC). The number, depth, and distribution of homomorphic multiplications are considered together in the model for the first time. In addition, two primitive binary circuits on homomorphically encrypted data are optimized by using a unit called dot multiplication (DotMC). A novel comparison circuit based on DotMC is presented, and the number of homomorphic multiplications is reduced from ${O}(n {\mathrm{ log}} ~n)$ to ${O}({n})$ without increasing the multiplicative depth compared with the logarithm comparison, where ${n}$ is the bit length of the operand. The WCC of comparison is reduced from ${O}(n({\mathrm{ log}}~n)^{2})$ to ${O}({n}({\mathrm{ log}} ~{n}))$. The carry-lookahead adder is optimized by moving some DotMCs to levels with smaller weight, which reflects the effect of the distribution of homomorphic multiplications on performance. Finally, the proposed DotMC is accelerated with a single-instruction-multiple-data approach for even one operation; the number of homomorphic multiplication is reduced from ${O}({n})$ to ${O}({\mathrm{ log}}~n)$ compared with other comparison with the same strategy. Various circuits with the size from 4 to 2048 b are implemented with HElib to prove the optimization for comparison and addition, as well as the effectiveness of the proposed model. [ABSTRACT FROM AUTHOR]