Secure Computation with Sublinear Amortized Work

Speaker  Mariana Raykova

Host  Seny Kamara

Affiliation  Columbia University

Duration  01:16:08

Date recorded  8 July 2011

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

©2011 Microsoft Corporation. All rights reserved.
> Secure Computation with Sublinear Amortized Work