Fully homomorphic encryption for fixed-point elements
A computer-implemented method comprising: receiving, as input, a ciphertext x representing a computational result of an approximated fully-homomorphic encryption (FHE) scheme, wherein ciphertext x comprises an underlying number m and an accumulated computational error e; iteratively, (i) performing a bit extraction operation to extract a current most significant bit (MSB) x′ of ciphertext x, (ii) calculating accuracy parameters α, β associated with x′; (iii) applying a step function to the extracted MSB x′, based, at least in part, on the calculated accuracy parameters α, β, to reduce or remove the accumulated computational error e and to return a clean MSB b, and (iv) repeating steps (i)-(iii) for all bits included in the underlying number m; and reconstructing and outputting, from all of the returned clean MSBs b, the number m.
1. A computer-implemented method comprising:
receiving, as input, a ciphertext x representing a computational result of an approximated fully-homomorphic encryption (FHE) scheme, wherein ciphertext x comprises a combination of an underlying number m and an accumulated computational error e;
iteratively,
(i) performing a bit extraction operation to extract a current most significant bit (MSB) x′ of ciphertext x,
(ii) calculating accuracy parameters input precision α, output precision β associated with x′,
(iii) applying a step function to said extracted MSB x′, based, at least in part, on said calculated accuracy parameters α, β, to reduce or remove said accumulated computational error e and to return a clean MSB b, and
(iv) repeating steps (i)-(iii) for all bits included in said underlying number m; and
reconstructing and outputting, from all of said returned clean MSBs b, said number m,
wherein m has fewer bits than x.
2. The computer-implemented method of claim 1 , wherein said number m is (i) an integer, or (ii) a fixed point element.
3. The computer-implemented method of claim 1 , wherein said accumulated computational error e of ciphertext x represents the result of one of one or more computational operations in said approximated FHE scheme.
4. The computer-implemented method of claim 3 , further comprising: (i) applying, after each of said one or more computational operations, a heuristic analysis to determine a size of said accumulated computational error e, and (ii) performing steps (i)-(iv) when said accumulated computational error e exceeds a predetermined threshold value.
5. The computer-implemented method of claim 1 , wherein said step function is a polynomial which provides a branch functionality.
6. The computer-implemented method of claim 1 , wherein said accuracy parameter α defines an available accuracy of an input to said step function, and said accuracy parameters β defines a required accuracy of an output of said step function.
7. The computer-implemented method of claim 1 , wherein said ciphertext x represents one of a set of index values associated with a plurality of entries in a lookup table, and wherein step (iii) applies a function which returns 1 when said ciphertext x is equal to one of said index values, and returns 0 otherwise.
8. A system comprising:
at least one hardware processor; and
a non-transitory computer-readable storage medium having program code embodied therewith, the program code executable by said at least one hardware processor to:
receive, as input, a ciphertext x representing a computational result of an approximated fully-homomorphic encryption (FHE) scheme, wherein ciphertext x comprises a combination of an underlying number m and an accumulated computational error e,
iteratively,
(i) perform a bit extraction operation to extract a current most significant bit (MSB) x′ of ciphertext x,
(ii) calculate accuracy parameters input precision α, output precision β associated with x′,
(iii) apply a step function to said extracted MSB x′, based, at least in part, on said calculated accuracy parameters α, β, to reduce or remove said accumulated computational error e and to return a clean MSB b, and
(iv) repeat steps (i)-(iii) for all bits included in said underlying number m, and
reconstruct and output, from all of said returned clean MSBs b, said number m,
wherein m has fewer bits than x.
9. The system of claim 8 , wherein said number m is (i) an integer, or (ii) a fixed point element.
10. The system of claim 8 , wherein said accumulated computational error e of ciphertext x represents the result of one or more computational operations in said approximated FHE scheme.
11. The system of claim 10 , wherein said program instructions are further executable to (i) apply, after each of said one or more computational operations, a heuristic analysis to determine a size of said accumulated computational error e, and (ii) perform steps (i)-(iv) when said accumulated computational error e exceeds a predetermined threshold value.
12. The system of claim 8 , wherein said step function is a polynomial which provides a branch functionality.
13. The system of claim 8 , wherein said accuracy parameter α defines an available accuracy of an input to said step function, and said accuracy parameters β defines a required accuracy of an output of said step function.
14. The system of claim 8 , wherein said ciphertext x represents one of a set of index values associated with a plurality of entries in a lookup table, and wherein step (iii) applies a function which returns 1 when said ciphertext x is equal to one of said index values, and returns 0 otherwise.
15. A computer program product comprising a non-transitory computer-readable storage medium having program code embodied therewith, the program code executable by at least one hardware processor to:
receive, as input, a ciphertext x representing a computational result of an approximated fully-homomorphic encryption (FHE) scheme, wherein ciphertext x comprises a combination of an underlying number m and an accumulated computational error e;
iteratively,
(i) perform a bit extraction operation to extract a current most significant bit (MSB) x′ of ciphertext x,
(ii) calculate accuracy parameters input precision α, output precision β associated with x′,
(iii) apply a step function to said extracted MSB x′, based, at least in part, on said calculated accuracy parameters α, β, to reduce or remove said accumulated computational error e and to return a clean MSB b, and
(iv) repeat steps (i)-(iii) for all bits included in said underlying number m; and
reconstruct and output, from all of said returned clean MSBs b, said number m, wherein
m has fewer bits than x.
16. The computer program product of claim 15 , wherein said number m is (i) an integer, or (ii) a fixed point element.
17. The computer program product of claim 15 , wherein said accumulated computational error e of ciphertext x represents the result of one or more computational operations in said approximated FHE scheme.
18. The computer program product of claim 17 , wherein said program instructions are further executable to (i) apply, after each of said one or more computational operations, a heuristic analysis to determine a size of said accumulated computational error e, and (ii) perform steps (i)-(iv) when said accumulated computational error e exceeds a predetermined threshold value.
19. The computer program product of claim 15 , wherein said step function is a polynomial which provides a branch functionality.
20. The computer program product of claim 15 , wherein said accuracy parameter α defines an available accuracy of an input to said step function, and said accuracy parameters β defines a required accuracy of an output of said step function.