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 compilers, but they require significantly more development effort in programming and verification. Recently, Kerschbaum introduced 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 programmer 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.