Polynomial evaluation under fully homomorphic encryption

A computer program product comprising one or more computer readable storage media, and program instructions collectively stored on the one or more computer readable storage media, the program instructions executable by a processor to cause the processor to perform operations comprising:

• reducing computational error and enhancing an accuracy of an evaluation output of an application performing Fully Homomorphic Encryption (FHE) computation, the reducing comprising:
• expanding a polynomial expression in memory into a plurality of products instructions, each product instruction in the plurality of products instructions executing to perform a scaling coefficient multiplied by a sub-polynomial, each sub-polynomial comprising a sum of a plurality of addends, wherein a degree of each sub-polynomial is equal to a grouping parameter;
• computing a plurality of ciphertext products, each ciphertext product equal to a ciphertext multiplied by itself a number of times, the number of times ranging from two to the grouping parameter;
• computing, using the ciphertext and the plurality of ciphertext products in place of a variable of the polynomial, each of the plurality of products;
• and
• multiplying the plurality of products together such that in the evaluation output of the FHE computation a number of non-scalar product computations is minimized and a depth of computation tree is minimized by parallelizing a multi-product multiplication.

A computer system comprising a processor and one or more computer readable storage media, and program instructions collectively stored on the one or more computer readable storage media, the program instructions executable by the processor to cause the processor to perform operations comprising:

• reducing computational error and enhancing an accuracy of an evaluation output of an application performing Fully Homomorphic Encryption (FHE) computation, the reducing comprising:
• expanding a polynomial expression in memory into a plurality of products instructions, each product instruction in the plurality of products instructions executing to perform a scaling coefficient multiplied by a sub-polynomial, each sub-polynomial comprising a sum of a plurality of addends, wherein a degree of each sub-polynomial is equal to a grouping parameter;
• computing a plurality of ciphertext products, each ciphertext product equal to a ciphertext multiplied by itself a number of times, the number of times ranging from two to the grouping parameter;
• computing, using the ciphertext and the plurality of ciphertext products in place of a variable of the polynomial, each of the plurality of products;
• and
• multiplying the plurality of products together such that in the evaluation output of the FHE computation a number of non-scalar product computations is minimized and a depth of computation tree is minimized by parallelizing a multi-product multiplication.