Secure Computation with Sublinear Amortized Work

Опубликовано 17 августа 2016, 2:44

We present the first protocol for secure two-party computation that allows a client and a server to evaluate an arbitrary function f with an amortized poly-logarithmic computational overhead over the insecure version of f. For functions that can be computed in sublinear time, this yields the first general secure protocol with sublinear amortized complexity. We provide a generic and simple protocol that achieves the asymptotic improvement, as well as a vastly optimized practical protocol, using new techniques for oblivious memory access, and relying on existing two-party computation protocols to evaluate a small number of carefully selected simple operations. We achieve orders of magnitude performance improvements, even on todayΓÇÖs moderate input sizes, for (amortized) execution of important tasks, such as binary search on a large dataset ΓÇô a core building block for secure DB access, location-based services, etc. In general, our approach will likely be advantageous in amortized computations where the serverΓÇÖs input is large, and the clientΓÇÖs input and the computed program are small. Joint work with Dov Gordon, Jonathan Katz, Vladimir Kolesnikov, Tal Malkin, Yevgeniy Vahlis