Title: Oblivious function evaluation with sub-linear complexity

Tuesday, November 30, 4:30-5:30, CORE 431

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.