We consider the following oblivious function evaluation problem: party $\D$ (a ``database'') has input $x$, and party $\U$ (a ``user'') holds a function $f$. The parties wish to engage in a protocol where $\U$ learns $f(x)$, and $\D$ learns nothing. In particular, $\D$ does not learn $f$ nor the data locations that were queried to compute $f$. General solutions for solving this problem are known, but require, from both parties, complexity that is at least linear in $n=|x|$ (and in the description size of $f$). This is quite imposing on the user in typical cases where $x$ is large and $f$ is relatively simple, and in particular depends only on few locations in $x$.

We describe protocols for this problem where the user's complexity is proportional only to the number, $m$, of locations that are accessed by $f$, plus the description size of $f$ (as a function of $m$ inputs), plus sub-linear dependence on $n$. In particular, in typical cases where $m$ is small enough and $f$ is not too complex, the user incurs complexity that is sub-linear in $n$. Some of our protocols are based on the cubic residuosity assumption, and others on the hardness of distinguishing discrete logarithms, both modulo a composite with unknown factorization.

Our results extend, in a natural way, known works on oblivious transfer, and, more recently, on private information retrieval (PIR). These works are largely concentrated on the problem of learning the contents of specific locations of the database. In particular, the departure point for our protocols is the recent work on PIR by Kushilevitz and Ostrovsky.

This is joint work with Ran Canetti and Ravi Kumar.