High-Precision Arithmetic in Homomorphic Encryption

In most RLWE-based homomorphic encryption schemes the native plaintext elements are polynomials in a ring Zt[x]/(xn+1)

${\mathbb{Z}}_t[x]/(x^n+1)$

, where n is a power of 2, and t an integer modulus. For performing integer or rational number arithmetic, one typically uses an encoding scheme which converts the inputs to polynomials, and allows the result of the homomorphic computation to be decoded to recover the result as an integer or rational number, respectively. The problem is that the modulus t often needs to be extremely large to prevent the plaintext polynomial coefficients from being reduced modulo t during the computation, which is a requirement for the decoding operation to work correctly. This results in larger noise growth, and prevents the evaluation of deep circuits, unless the encryption parameters are significantly increased.

We combine a trick of Hoffstein and Silverman, where the modulus t is replaced by a polynomial x−b

$x-b$

, with the Fan-Vercauteren homomorphic encryption scheme. This yields a new scheme with a very convenient plaintext space Z/(bn+1)Z

$\mathbb{Z}/(b^n+1)\mathbb{Z}$

. We then show how rational numbers can be encoded as elements of this plaintext space, enabling homomorphic evaluation of deep circuits with high-precision rational number inputs. We perform a fair and detailed comparison to the Fan-Vercauteren scheme with the Non-Adjacent Form encoder, and find that the new scheme significantly outperforms this approach. For example, when the new scheme allows us to evaluate circuits of depth 9 with 32-bit integer inputs, in the same parameter setting the Fan-Vercauteren scheme only allows us to go up to depth 2. We conclude by discussing how known applications can benefit from the new scheme.