Reuse It Or Lose It: More Efficient Secure Computation Through Reuse of Encrypted Values
This work addresses efficiency and state management issues in secure computation, particularly for resource-constrained devices, though it is incremental as it builds on existing SFE methods.
The paper tackles the bottleneck of input validation and lack of state retention in two-party secure function evaluation (SFE) by introducing PartialGC, a system that reuses encrypted values from garbled-circuit computations, reducing computation time by up to 96% and bandwidth by up to 98% compared to previous outsourcing schemes.
Two-party secure function evaluation (SFE) has become significantly more feasible, 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 paper presents PartialGC, an SFE system that allows the reuse of encrypted values generated during a garbled-circuit 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 outsourcing schemes for secure computation. We demonstrate the feasibility of our approach with two sets of experiments, one in which the garbled circuit is evaluated on a mobile device and one in which it is evaluated on a server. 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 and further reduces computational barriers.