We first describe how programs written in a small Turing-complete instruction set can be executed with encrypted data and point out inefficiencies in this methodology. We then provide examples of transforming (a) the greatest common divisor (GCD) problem using Euclid’s algorithm and (b) the 3-Satisfiability (3SAT) problem using a recursive backtracking algorithm into a path-levelized form to which FHE can be applied. We describe how path levelization reduces control flow ambiguity and improves encrypted computation efficiency. Using these techniques and data-dependent loops as a starting point, we then build support for hierarchical programs made up of phases, where each phase corresponds to a fixed point computation that can be used to further improve the efficiency of encrypted computation.
In our setting, the adversary learns an estimate of the number of steps required to complete the computation, which we show is the least amount of leakage possible.
Category / Keywords: cryptographic protocols / fully-homomorphic-encryption, program control flow, compilation Date: received 10 May 2012 Contact author: cwfletch at mit edu Available format(s): PDF | BibTeX Citation Version: 20120517:044840 (All versions of this report) Discussion forum: Show discussion | Start new discussion