OGST - Debayan Gupta
“Partial Garbled Circuits: More Efficient Secure Computation Through Reuse of Encrypted Values”
Secure function evaluation, or SFE, allows multiple parties to jointly compute a function while maintaining input and output privacy. The two-party variant, known as 2P-SFE, was first introduced by Yao in the 1980’s and was largely a theoretical curiosity. 2P-SFE has become vastly more efficient in recent years, even on resource-constrained devices, because of advances in server-aided computation systems. However, there are still bottlenecks, particularly in the input-validation stage of a computation. Moreover, SFE research has not yet devoted sufficient attention to the important problem of retaining state after a computation has been performed so that expensive processing does not have to be repeated if a similar computation is done again.
This talk presents PartialGC, a garbled-circuit based SFE system that allows the reuse of encrypted values generated during a secure computation. We show that using PartialGC can reduce computation time by as much as 96% and bandwidth by as much as 98% in comparison with previous schemes for secure computation. We demonstrate the feasibility of our approach with a series of experiments. We also use PartialGC to build a privacy-preserving friend-finder application for Android. The reuse of previous inputs to allow stateful evaluation represents a new way of looking at SFE, further reduces computational barriers, and paves the way for true reusability.