Secure Computation via Greedy Algorithms
- 講者Muthuramakrishnan Venkitasubramaniam 教授 (University of Rochester, USA)
邀請人：鐘楷閔 - 時間2015-03-12 (Thu.) 10:30 ~ 12:30
- 地點資訊所新館107演講廳
摘要
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.