Low-Complexity Integer Divider Architecture for Homomorphic Encryption

Homomorphic encryption (HE) allows computations to be directly carried out on ciphertexts and enables privacy-preserving cloud computing. The computations on the coefficients of the polynomials involved in HE are always followed by modular reduction, and the overall complexity of ciphertext multiplication can be reduced by utilizing the quotient. Our previous design considers the cases that the dividend is an integer multiple of the modulus and the modulus is in the format of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2^{w}-2^{u}\pm1$</tex>, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$u &lt; w/2$</tex>. In this paper, the division is generalized for larger <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$u$</tex> and dividend not an integer multiple of the modulus. An algorithm is proposed to compute the quotient and vigorous mathematical proofs are provided. Moreover, efficient hardware architectures are developed for implementing the proposed algorithm. Compared to the best previous design, synthesis results show that the proposed design for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$w=32$</tex> has at least 40% higher efficiency in terms of area-delay product for 75% possible values of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$u$</tex>.