Accelerated division of homomorphically encrypted data
Methods and systems for performing an operation on at least one homomorphically encrypted ciphertext, the method include determining, by a computing device, a value that is an initial approximation of a result of the operation on the at least one homomorphically encrypted ciphertext; and iteratively improving, by the computing device, the value using a recurrence relation wherein a number of iterations is determined based on a predetermined accuracy to minimize an approximation error.
1. A method executed at multiple computing devices connected via one or more network(s), the method comprising:
at a first computing device of the multiple computing devices:
securely storing unencrypted data and one or more private keys;
homomorphically encrypting the unencrypted data using the one or more private keys to generate a homomorphic encrypted ciphertext x;
at a second computing device of the multiple computing devices:
receiving, from the first computing device, over the one or more network(s) connecting the multiple computing devices, the homomorphic encrypted ciphertext x;
calculating a polynomial approximation of 1/x for a homomorphically encrypted ciphertext x without decrypting the denominator x of the polynomial approximation by:
receiving a first value, l, corresponding to a degree of the polynomial approximation to be calculated;
receiving a second value, α, and a third value, β, wherein the second value and the third value define a range over which the polynomial approximation is to be calculated; and
calculating the polynomial approximation of 1/x for the homomorphically encrypted ciphertext x using the expression using the expression:
∑
2
l
k
=
0
(
a
k
-
1
2
+
a
k
+
1
2
)
T
k
(
ξ
(
x
)
)
wherein a k (l) =2ξ 0 a k+1 (l) +a k+2 (l) for k=2 l −3,2 l −4, . . . ,1,0,
wherein
ξ
(
x
)
=
1
-
2
β
-
x
β
-
α
,
and
wherein T k (x) is a Chebyshev polynomial of the first kind of degree K.
2. The method of claim 1 , wherein 0 is included in the range defined by the second value and the third value.
3. A system comprising:
one or more network(s) connecting multiple computing devices;
a first computing device of the multiple computing devices comprising at least one processor and a memory containing instructions which, when executed by the at least one processor, cause the at least one processor to:
securely store unencrypted data and one or more private keys, and
homomorphically encrypt the unencrypted data using the one or more private keys to generate a homomorphic encrypted ciphertext x; and
a second computing device of the multiple computing devices comprising at least one processor and a memory containing instructions which, when executed by the at least one processor, cause the at least one processor to:
receive, from the first computing device, over the one or more network(s) connecting the multiple computing devices, the homomorphic encrypted ciphertext x;
calculate a polynomial approximation of 1/x for a homomorphically encrypted ciphertext x without decrypting the denominator x of the polynomial approximation by:
receiving a first value, l, corresponding to a degree of the polynomial approximation to be calculated;
receiving a second value, α, and a third value, β, wherein the second value and the third value define a range over which the polynomial approximation is to be calculated; and
calculating the polynomial approximation of 1/x for a homomorphically encrypted ciphertext x using the expression:
∑
2
l
k
=
0
(
a
k
-
1
2
+
a
k
+
1
2
)
T
k
(
ξ
(
x
)
)
wherein a k (l) =2ξ 0 a k+1 (l) +a k+2 (l) for k=2 l +3,2 l −4, . . . ,1, 0,
wherein
ξ
(
x
)
=
1
-
2
β
-
x
β
-
α
,
and
wherein T k (x) is a Chebyshev polynomial of the first kind of degree k.
4. The system of claim 3 , wherein 0 is included in the range defined by the second value and the third value.