Secure Computation with Sublinear Amortized Work

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

Speaker Details

Mariana is a PhD student at Columbia University working in the areas of cryptography and security with Tal Malkin and Steve Bellovin. Her research focuses on secure computation and more specifically on improving efficiency that aims to make secure multiparty computation protocols usable in practice. This includes considering new computational models, specific functionalities, relaxed security notions. The last two years she was an intern with the crypto group at MSR, and this summer she is working in the security group.

Date:
Speakers:
Mariana Raykova
Affiliation:
Columbia University
    • Portrait of Jeff Running

      Jeff Running