Efficient Generalized Integer Division and Modular Reduction Architectures for Homomorphic Encryption

Abstract Homomorphic encryption allows computations to be performed directly on ciphertexts, serving as a key enabler for privacy-preserving cloud computing. The computations over ciphertexts involve large integer modular multiplications. Besides, the overall complexity of ciphertext multiplication can be further reduced by utilizing quotients of integer divisions. An efficient quotient computation architecture was developed in our previous work for the case that the divisor has three nonzero bits. This paper first generalizes our prior design to accommodate divisors with more nonzero bits. To further reduce the latency, a new non-iterative quotient computation method is developed by simplifying the Barrett reduction. Rigorous mathematical proofs are provided for both proposed schemes, and they are also adopted for modular reduction. Besides, this paper developed efficient hardware implementation architectures for our proposed algorithms, and optimizations are carried out to reduce the complexity further. Compared to the best prior integer division (modular reduction) schemes, our proposed designs can achieve around 60% (57%) smaller area and 70% (71%) shorter latency when the modulus has 64 bits.