Paper 2012/266

Compilation Techniques for Efficient Encrypted Computation

Christopher Fletcher, Marten van Dijk, and Srinivas Devadas

Abstract

Fully homomorphic encryption (FHE) techniques 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 a compiler that, given programs with complex control flow, generates efficient code suitable for the application of FHE schemes. 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
fully-homomorphic-encryptionprogram control flowcompilation
Contact author(s)
cwfletch @ mit edu
History
2012-05-17: received
Short URL
https://ia.cr/2012/266
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/266,
      author = {Christopher Fletcher and Marten van Dijk and Srinivas Devadas},
      title = {Compilation Techniques for Efficient Encrypted Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2012/266},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/266}},
      url = {https://eprint.iacr.org/2012/266}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.