Abstract
The standard method for designing a secure computation protocol for function f first transforms f into either a circuit or a RAM program and then applies a generic secure computation protocol that either handles boolean gates or translates the RAM program into oblivious RAM instructions respectively.
In this work, we show a large class of functions for which a different algorithmic approach to secure computation results in more efficient protocols. The first such examples of this technique was presented by Aggrawal, Mishra, and Pinkas (J. of Cryptology, 2010) for computing the median; later, Brickell and Shmatikov (Asiacrypt 2005) showed a similar technique for minimum spanning tree and a variant of shortest paths.
We generalize the technique in both of those works and show that it applies for a large class of problems including matroid optimizations, sub-modular optimization, convex hulls, and other scheduling problems. The crux of our technique is to securely reduce these problems to secure comparison operations. We then describe general properties under which simulation-based security can be achieved for honest-but-curious and covert adversary models.