Expression Rewriting for Optimizing Secure Computation

In theory secure computation offers a solution for privacy in many collaborative applications. However, in practice poor efficiency of the protocols prevents their use. Hand-crafted protocols are more efficient than those implemented in com-pilers, but they require significantly more development effort in programming and verification. Recently, Kerschbaum in-troduced an automatic compiler optimization technique for secure computations that can make compilers as efficient as hand-crafted protocols. This optimization relies on the structure of the secure computation program. The program-mer has to implement the program in such a way, such that the optimization can yield the optimal performance. In this paper we present an algorithm that rewrites the program – most notably its expressions – optimizing their efficiency in secure computation protocols. We give a heuristic for whole-program optimization and show the resulting performance gains using examples from the literature