Fast computation of a single coefficient in an inverse polynomial
View Patent ↗In one exemplary embodiment of the invention, a method for computing a resultant and a free term of a scaled inverse of a first polynomial v(x) modulo a second polynomial f n (x), including: 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 ) = def ∏ 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).
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
)
=
def
∏
i
=
0
n
-
1
(
v
(
ρ
i
)
-
z
)
,
where ρ 0 , ρ 1 , . . . , ρ n−1 are roots of the second polynomial f n (x) over a field, where computing the lowest two coefficients of the third polynomial g(z) comprises computing a fourth polynomial h(z), where h(z)=g(z)mod z 2 , and where computing the fourth polynomial comprises computing pairs of polynomials U j (x) and V j (x) for j=0, 1, . . . , log n, such that for all j it holds that g(z) is congruent modulo z 2 to a fifth polynomial G j (z), where
G
j
(
z
)
=
def
∏
i
=
0
n
2
j
(
V
j
(
ρ
i
2
j
)
-
z
U
j
(
ρ
i
2
j
)
)
;
outputting by the computing system the lowest coefficient of g(z) as the resultant;
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 of claim 1 , where V 0 (x)=v(x) and U 0 (x)=1 , where for every j the polynomials U j+1 (x 2 ) and V j+1 (x 2 ) are defined as:
U
j
+
1
(
x
2
)
=
def
U
j
(
x
)
V
j
(
-
x
)
+
U
j
(
-
x
)
V
j
(
x
)
mod
(
x
n
2
j
±
1
)
and
V
j
+
1
(
x
2
)
=
def
V
j
(
x
)
V
j
(
-
x
)
mod
(
x
n
2
j
±
1
)
.
3. The method of 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.
4. The method of claim 3 , 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).
5. The method of 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.
6. 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
)
=
def
∏
i
=
0
n
-
1
(
v
(
ρ
i
)
-
z
)
,
where ρ 0 , ρ 1 , . . . , ρ n−1 are roots of the second polynomial f n (x) over a field, where computing the lowest two coefficients of the third polynomial g(z) comprises computing a fourth polynomial h(z), where h(z)=g(z)mod z 2 , and where computing the fourth polynomial comprises computing pairs of polynomials U j (x) and V j (x) for j=0, 1, . . . , log n, such that for all j it holds that g(z) is congruent modulo z 2 to a fifth polynomial G j (z), where
G
j
(
z
)
=
def
∏
i
=
0
n
2
j
(
V
j
(
ρ
i
2
j
)
-
z
U
j
(
ρ
i
2
j
)
)
;
outputting the lowest coefficient of g(z) as the resultant;
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.
7. The computer readable storage device of claim 6 , where V 0 (x)=v(x) and U 0 (x)=1 , where for every j the polynomials U j+1 (x 2 ) and V j+1 (x 2 ) are defined as:
U
j
+
1
(
x
2
)
=
def
U
j
(
x
)
V
j
(
-
x
)
+
U
j
(
-
x
)
V
j
(
x
)
mod
(
x
n
2
j
±
1
)
and
V
j
+
1
(
x
2
)
=
def
V
j
(
x
)
V
j
(
-
x
)
mod
(
x
n
2
j
±
1
)
.
8. The computer readable storage device of claim 6 , 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.
9. The computer readable storage device of claim 8 , 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).
10. The computer readable storage device of claim 6 , 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.
11. An apparatus comprising:
at least one storage device configured 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 to compute, as part of a homomorphic encryption scheme, 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
)
=
def
∏
i
=
0
n
-
1
(
v
(
ρ
i
)
-
z
)
,
where ρ 0 , ρ 1 , . . . , ρ n−1 are roots of the second polynomial f n (x) over a field, where computing the lowest two coefficients of the third polynomial g(z) comprises computing a fourth polynomial h(z), where h(z)=g(z)mod z 2 , and where computing the fourth polynomial comprises computing pairs of polynomials U j (x) and V j (x) for j=0, 1, . . . , log n, such that for all j it holds that g(z) is congruent modulo z 2 to a fifth polynomial G j (z), where
G
j
(
z
)
=
def
∏
i
=
0
n
2
j
(
V
j
(
ρ
i
2
j
)
-
z
U
j
(
ρ
i
2
j
)
)
;
outputting the lowest coefficient of g(z) as the resultant; 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.
12. The apparatus of claim 11 , where V 0 (x)=v(x) and U 0 (x)=1 , where for every j the polynomials U j+1 (x 2 ) and V j+1 (x 2 ) are defined as:
U
j
+
1
(
x
2
)
=
def
U
j
(
x
)
V
j
(
-
x
)
+
U
j
(
-
x
)
V
j
(
x
)
mod
(
x
n
2
j
±
1
)
and
V
j
+
1
(
x
2
)
=
def
V
j
(
x
)
V
j
(
-
x
)
mod
(
x
n
2
j
±
1
)
.
13. The apparatus of claim 11 , 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.
14. The apparatus of claim 13 , 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).
15. The apparatus of claim 11 , 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.