TY - GEN

T1 - Towards an interpreter for efficient encrypted computation

AU - Fletcher, C.

AU - Van Dijk, M.

AU - Devadas, S.

PY - 2012

Y1 - 2012

N2 - Fully homomorphic encryption FHEtechniques are capable of performing encrypted computation on Boolean circuits, i.e., the user specifies encrypted inputs to the program, and the server computes on the encrypted inputs. Applying these techniques to general programs with recursive procedures and data-dependent loops has not been a focus of attention. In this paper, we take a first step toward building an interpreter that, given programs with complex control flow, schedules efficient code suitable for the application of FHE schemes. We first describe how programs written in a small Turingcomplete instruction set can be executed with encrypted data and point out inefficiencies in this methodology. We then provide examples of scheduling athe greatest common divisor GCD problem using Euclid's algorithm and bthe 3-Satisfiability 3SATproblem using a recursive backtracking algorithm into path-levelized FHE computations. 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.

AB - Fully homomorphic encryption FHEtechniques are capable of performing encrypted computation on Boolean circuits, i.e., the user specifies encrypted inputs to the program, and the server computes on the encrypted inputs. Applying these techniques to general programs with recursive procedures and data-dependent loops has not been a focus of attention. In this paper, we take a first step toward building an interpreter that, given programs with complex control flow, schedules efficient code suitable for the application of FHE schemes. We first describe how programs written in a small Turingcomplete instruction set can be executed with encrypted data and point out inefficiencies in this methodology. We then provide examples of scheduling athe greatest common divisor GCD problem using Euclid's algorithm and bthe 3-Satisfiability 3SATproblem using a recursive backtracking algorithm into path-levelized FHE computations. 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.

UR - http://www.scopus.com/inward/record.url?scp=84869809968&partnerID=8YFLogxK

U2 - 10.1145/2381913.2381928

DO - 10.1145/2381913.2381928

M3 - Conference contribution

T3 - Proceedings of the ACM Conference on Computer and Communications Security

SP - 83

EP - 94

BT - CCSW'12 - Proceedings of the Cloud Computing Security Workshop

T2 - 2012 ACM Workshop on Cloud Computing Security Workshop, CCSW 2012

Y2 - 19 October 2012 through 19 October 2012

ER -