View article

In most RLWE-based homomorphic encryption schemes the native plaintext elements are polynomials in a ring , 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 …