@article {15190,
title = {Secure computation with sublinear amortized work},
year = {2011},
month = {2011///},
institution = {Cryptology ePrint Archive, Report 2011/482},
abstract = {Traditional approaches to secure computation begin by representing the function f beingcomputed as a circuit. For any function f that depends on each of its inputs, this implies
a protocol with complexity at least linear in the input size. In fact, linear running time is
inherent for secure computation of non-trivial functions, since each party must {\textquotedblleft}touch{\textquotedblright} every
bit of their input lest information about other party{\textquoteright}s input be leaked. This seems to rule out
many interesting applications of secure computation in scenarios where at least one of the inputs
is huge and sublinear-time algorithms can be utilized in the insecure setting; private database
search is a prime example.
We present an approach to secure two-party computation that yields sublinear-time proto-
cols, in an amortized sense, for functions that can be computed in sublinear time on a random
access machine (RAM). Furthermore, a party whose input is {\textquotedblleft}small{\textquotedblright} is required to maintain
only small state. We provide a generic protocol that achieves the claimed complexity, based on
any oblivious RAM and any protocol for secure two-party computation. We then present an
optimized version of this protocol, where generic secure two-party computation is used only for
evaluating a small number of simple operations.
},
author = {Gordon,D. and Katz, Jonathan and Kolesnikov,V. and Malkin,T. and Raykova,M. and Vahlis,Y.}
}