Fast polynomial evaluation under fully homomorphic encryption by products of differences from roots using rotations

Abstract

Evaluating polynomials for use under fully homomorphic encryption (FHE) is provided. An input polynomial of degree n is received, wherein n is equal to 2{circumflex over ( )}m. An input ciphertext containing an input value is also received. The input value is duplicated in n/2 slots. Two plaintext vectors each containing half of the roots in the polynomial are subtracted from the input ciphertext, obtaining second and third ciphertexts, which are multiplied elementwise to produce a result ciphertext comprising n/2 slots. The result ciphertext is rotated by 2{circumflex over ( )}i to generate a rotated ciphertext (i=iteration number) and multiplied by the rotated ciphertext to produce a new result ciphertext, for m−1 iterations. The final result ciphertext is multiplied with a leading coefficient of the polynomial, resulting in a final polynomial evaluation. An operation not supported under FHE is estimated according to the final evaluation.