Fast computation of a single coefficient in an inverse polynomial

1. A method for computing, as part of a homomorphic encryption scheme a resultant and a free term of a scaled inverse of a first polynomial v(x) modulo a second polynomial f n (x), comprising:

receiving at a computing system the first polynomial v(x) modulo the second polynomial f n (x), where the second polynomial is of a form f n (x)=x n ±1, where n=2 k and k is an integer greater than 0;

computing by the computing system lowest two coefficients of a third polynomial g(z) that is a function of the first polynomial and the second polynomial, where g(z) Π i=0 n−1 (v(ρ i )−z), where ρ 0 , ρ 1 , . . . ρ n−1 are roots of the second polynomial f n (x) over a field;

outputting by the computing system the lowest coefficient of g(z) as the resultant; and

outputting by the computing system the second lowest coefficient of g(z) divided by n as the free term of the scaled inverse of the first polynomial v(x) modulo the second polynomial f n (x); and

using by the computing system the outputted resultant and the outputted free term in operations for the homomorphic encryption scheme.

2. The method as in claim 1 , where the first polynomial v(x) modulo the second polynomial f n (x) is derived from a sixth polynomial u(x) such that v(x)=x i ·u(x)mod f n (x), where i is an integer less than n: i<n.

3. The method as in claim 2 , where the free term of the scaled inverse of the first polynomial v(x) modulo the second polynomial f n (x) comprises the i-th coefficient of the scaled inverse of u(x).

4. The method as in claim 1 , where the free term of the scaled inverse of the first polynomial v(x) modulo the second polynomial f n (x) is used as a private key for decryption of a ciphertext.

5. A computer readable storage device tangibly embodying a program of instructions executable by a machine for performing operations for computing, as part of a homomorphic encryption scheme, a resultant and a free term of a scaled inverse of a first polynomial v(x) modulo a second polynomial f n (x), said operations comprising:

receiving the first polynomial v(x) modulo the second polynomial f n (x), where the second polynomial is of a form f n (x)=x n ±1, where n=2 k and k is an integer greater than 0;

computing lowest two coefficients of a third polynomial g(z) that is a function of the first polynomial and the second polynomial, where g(z) Π i=0 n−1 (v(ρ i )−z), where ρ 0 , ρ 1 , . . . , ρ n−1 are roots of the second polynomial f n (x) over a field;

outputting the lowest coefficient of g(z) as the resultant; and

outputting the second lowest coefficient of g(z) divided by n as the free term of the scaled inverse of the first polynomial v(x) modulo the second polynomial f n (x); and

using the outputted resultant and the outputted free term in operations for the homomorphic encryption scheme.

6. The computer readable storage device as in claim 5 , where the first polynomial v(x) modulo the second polynomial f n (x) is derived from a sixth polynomial u(x) such that v(x)=x i ·u(x)mod f n (x), where i is an integer less than n: i<n.

7. The computer readable storage device as in claim 5 , where the free term of the scaled inverse of the first polynomial v(x) modulo the second polynomial f n (x) comprises the i-th coefficient of the scaled inverse of u(x).

8. The computer readable storage device as in claim 5 , where the free term of the scaled inverse of the first polynomial v(x) modulo the second polynomial f n (x) is used as a private key for decryption of a ciphertext.

9. An apparatus comprising:

at least one storage medium configured to store program code and to store a first polynomial v(x) modulo a second polynomial f n (x), where the second polynomial is of a form f n (x)=x n ±1, where n=2 k and k is an integer greater than 0; and

at least one hardware processor configured, in response to execution of the program code, to cause the apparatus to perform operations as part of a homomorphic encryption scheme, the operations comprising:

computing a resultant and a free term of a scaled inverse of the first polynomial v(x) modulo the second polynomial f n (x) by computing lowest two coefficients of a third polynomial g(z) that is a function of the first polynomial and the second polynomial, where g(z) Π i=0 n−1 (v(ρ i )−z), where ρ 0 , ρ 1 , . . . , ρ n−1 are roots of the second polynomial f n (x) over a field;

outputting the lowest coefficient of g(z) as the resultant; and

outputting the second lowest coefficient of g(z) divided by n as the free term of the scaled inverse of the first polynomial v(x) modulo the second polynomial f n (x); and

using the outputted resultant and the outputted free term in operations for the homomorphic encryption scheme.

10. The apparatus as in claim 9 , where the first polynomial v(x) modulo the second polynomial f n (x) is derived from a sixth polynomial u(x) such that v(x)=x i ·u(x)mod f n (x), where i is an integer less than n: i<n.

11. The apparatus as in claim 10 , where the free term of the scaled inverse of the first polynomial v(x) modulo the second polynomial f n (x) comprises the i-th coefficient of the scaled inverse of u(x).

12. The apparatus as in claim 9 , where the free term of the scaled inverse of the first polynomial v(x) modulo the second polynomial f n (x) is used as a private key for decryption of a ciphertext.

13. The method of claim 1 , wherein using by the computing system the outputted resultant and the outputted free term in operations for the homomorphic encryption scheme further comprises using by the computing system the outputted resultant and the outputted free term in operations for key generation performed to generate one or more keys as part of the homomorphic encryption scheme.

14. The computer readable storage device of claim 5 , wherein using by the computing system the outputted resultant and the outputted free term in operations for the homomorphic encryption scheme further comprises using by the computing system the outputted resultant and the outputted free term in operations for key generation performed to generate one or more keys as part of the homomorphic encryption scheme.

15. The apparatus of claim 9 , wherein using the outputted resultant and the outputted free term in operations for the homomorphic encryption scheme further comprises using the outputted resultant and the outputted free term in operations for key generation performed to generate one or more keys as part of the homomorphic encryption scheme.