Secure Computation with Sublinear Amortized Work
21 February 2011
Consider searching over a sorted database containing n records. This can be accomplished easily in O(log n) time using, e.g., binary search. Yet generic secure computation applied to this task (where, say, a client holds an element and a server holds the database, and only the client should learn whether its element is in the database), even in the semi-honest setting, would start by expressing the computation as a circuit of size at least n, resulting in a protocol of complexity omega (n). In fact, any secure protocol for this task must have complexity omega (n) since the server must touch every bit of the database or else it learns something about the client's input. The same is true for any non-trivial function that depends on every bit of its input. We show that secure computation with sublinear (amortized) work is possible in a setting where the client and server perform multiple evaluations of the function f of interest. Crucially, our protocols express f in the RAM (random-access machine) model of computation which more closely corresponds to real-world program execution. We build on oblivious-RAM techniques to show that secure computation of f is possible with only polylogarithmic overhead (in an amortized sense) compared to the time for computing f on a RAM. Our main technical contribution is a highly optimized RAM compiler, which outperforms standard approaches for practical-size databases.
