Recursive algorithms with delayed computations performed in a homomorphically encrypted space
A device, system and method for securely executing recursive computations over encrypted data in a homomorphically encrypted (HE) space. For a recursive algorithm with sequentially dependent recursive iterations, executing the recursive algorithm in parallel by computing multiple recursive iterations simultaneously over multiple parallel execution iterations and not in sequential order. Each parallel execution iteration may compute a partial HE solution of multiple sequential recursive iterations comprising a known HE part and leaves empty a placeholder call slot for an unknown HE part. Placeholder call slots remain empty and are filled at delayed times at a later parallel execution iteration from when the known part of the same HE computation is computed. A final HE solution is computed in fewer multiple parallel execution iterations than the number of sequential recursive iterations, thereby accelerating the recursive algorithm in HE space.
1. A method for securely executing recursive computations over encrypted data in a homomorphically encrypted space, the method comprising:
for a recursive algorithm in which each sequential recursive iteration depends on a complete homomorphically encrypted solution from a previous recursive iteration, executing the recursive algorithm in parallel by computing multiple recursive iterations simultaneously over multiple parallel execution iterations and not in sequential order,
wherein each of a plurality of the parallel execution iterations computes a partial homomorphically encrypted solution of multiple sequential recursive iterations comprising a part of the homomorphically encrypted computation that is known and leaves empty a placeholder call slot in place of a part of the computation that is unknown that depends on a complete homomorphically encrypted solution from a previous recursive iteration,
wherein the placeholder call slots remain empty and are filled at delayed times at a later parallel execution iteration from when the known part of the same homomorphically encrypted computation is computed, and
wherein the multiple parallel execution iterations cumulatively compute a final homomorphically encrypted solution to the recursive algorithm in fewer multiple parallel execution iterations than the number of sequential recursive iterations, such that the final homomorphically encrypted solution to the recursive algorithm when decrypted is equivalent to executing the recursive algorithm on unencrypted data.
2. The method of claim 1 , wherein the multiple parallel execution iterations are arranged in a tree structure, such that:
distal leaf nodes represent an initial parallel execution iteration,
each row of successively proximal leaf nodes represents a subsequent parallel execution iteration linking the placeholder call slots in the proximal leaf nodes by branches to the homomorphically encrypted solutions in other leaf nodes from which they depend, and
a root node, connected to a plurality of leaf nodes, represents the final homomorphically encrypted solution to the recursive algorithm.
3. The method of claim 1 , wherein the multiple parallel execution iterations are arranged in a circuit structure.
4. The method of claim 1 comprising computing each homomorphically encrypted solution in an mth parallel execution iteration to depend on a predetermined number, q, of homomorphically encrypted solutions from a previous m−1th parallel execution iteration.
5. The method of claim 4 comprising, when the recursive algorithm has i recursive sequential iterations, computing the final homomorphically encrypted solution of the recursive algorithm in m=log q (i+1) parallel execution iterations.
6. The method of claim 5 comprising, when the recursive algorithm has i recursive sequential iterations, computing a total of
i
+
1
q
m
partial homomorphically encrypted solutions in each mth parallel execution iteration.
7. The method claim 4 , wherein
∑
k
=
1
m
i
+
1
q
k
recursive sequential iterations are executed in m parallel execution iterations.
8. The method of claim 1 comprising filling empty placeholder call slots out of the order of the parallel execution iterations, wherein an empty placeholder call slot depends on a complete homomorphically encrypted solution computed in a concurrent or subsequent parallel execution iterations.
9. The method of claim 8 , wherein the empty placeholder call slot is connected to the dependent complete homomorphically encrypted solution via a loop in the concurrent parallel execution iteration or a reverse call function from the subsequent parallel execution iteration.
10. A system for securely executing recursive computations over encrypted data in a homomorphically encrypted space, the system comprising:
one or more processors configured to, for a recursive algorithm in which each sequential recursive iteration depends on a complete homomorphically encrypted solution from a previous recursive iteration, execute the recursive algorithm on the encrypted data in parallel by computing multiple recursive iterations simultaneously over multiple parallel execution iterations and not in sequential order,
wherein each of a plurality of the parallel execution iterations computes a partial homomorphically encrypted solution of multiple sequential recursive iterations comprising a part of the homomorphically encrypted computation that is known and leaves empty a placeholder call slot in place of a part of the computation that is unknown that depends on a complete homomorphically encrypted solution from a previous recursive iteration,
wherein the placeholder call slots remain empty and are filled at delayed times at a later parallel execution iteration from when the known part of the same homomorphically encrypted computation is computed,
wherein the multiple parallel execution iterations cumulatively compute a final homomorphically encrypted solution to the recursive algorithm in fewer multiple parallel execution iterations than the number of sequential recursive iterations, such that the final homomorphically encrypted solution to the recursive algorithm when decrypted is equivalent to executing the recursive algorithm on unencrypted data; and
one or more memories configured to store the final homomorphically encrypted solution to the recursive algorithm.
11. The system of claim 10 , wherein the one or more processors are configured to send an external party device the final homomorphically encrypted solution, wherein the external party device stores one or more secret decryption keys in memory to decrypt the final homomorphically encrypted solution.
12. The system of claim 10 , wherein the multiple parallel execution iterations arranged in a tree structure, such that:
distal leaf nodes represent an initial parallel execution iteration,
each row of successively proximal leaf nodes represents a subsequent parallel execution iteration linking the placeholder call slots in the proximal leaf nodes by branches to the homomorphically encrypted solutions in other leaf nodes from which they depend, and
a root node, connected to a plurality of leaf nodes, represents the final homomorphically encrypted solution to the recursive algorithm.
13. The system of claim 10 , wherein the multiple parallel execution iterations are arranged in a circuit structure.
14. The system of claim 10 , wherein the one or more processors are configured to compute each homomorphically encrypted solution in an mth parallel execution iteration to depend on a predetermined number, q, of homomorphically encrypted solutions from a previous m−1th parallel execution iteration.
15. The system of claim 14 , wherein, when the recursive algorithm has i recursive sequential iterations, the one or more processors are configured to compute the final homomorphically encrypted solution of the recursive algorithm in m=log q (i+1) parallel execution iterations.
16. The system of claim 15 , wherein, when the recursive algorithm has i recursive sequential iterations, the one or more processors are configured to compute a total of
i
+
1
q
m
partial homomorphically encrypted solutions in each mth parallel execution iteration.
17. The system of claim 14 , wherein the one or more processors are configured to execute
∑
k
=
1
m
i
+
1
q
k
recursive sequential iterations in m parallel execution iterations.
18. The system of claim 10 , wherein the one or more processors are configured to fill empty placeholder call slots out of the order of the parallel execution iterations, wherein an empty placeholder call slot depends on a complete homomorphically encrypted solution computed in a concurrent or subsequent parallel execution iterations.
19. The system of claim 18 , wherein the empty placeholder call slot is connected to the dependent complete homomorphically encrypted solution via a loop in the concurrent parallel execution iteration or a reverse call function from the subsequent parallel execution iteration.
20. A non-transitory computer-readable storage medium encoded with instructions that, when executed, cause one or more processors to:
for a recursive algorithm in which each sequential recursive iteration depends on a complete homomorphically encrypted solution from a previous recursive iteration, execute the recursive algorithm in parallel by computing multiple recursive iterations simultaneously over multiple parallel execution iterations and not in sequential order,
wherein each of a plurality of the parallel execution iterations computes a partial homomorphically encrypted solution of multiple sequential recursive iterations comprising a part of the homomorphically encrypted computation that is known and leaves empty a placeholder call slot in place of a part of the computation that is unknown that depends on a complete homomorphically encrypted solution from a previous recursive iteration,
wherein the placeholder call slots remain empty and are filled at delayed times at a later parallel execution iteration from when the known part of the same homomorphically encrypted computation is computed, and
wherein the multiple parallel execution iterations cumulatively compute a final homomorphically encrypted solution to the recursive algorithm in fewer multiple parallel execution iterations than the number of sequential recursive iterations, such that the final homomorphically encrypted solution to the recursive algorithm when decrypted is equivalent to executing the recursive algorithm on unencrypted data.