Additive Randomized Encodings

A secure computation protocol for f(x_1,...,x_n) enables n parties to
evaluate f on their local inputs x_i while hiding everything except the
output. A useful special case, which is often easier to solve, is when f
computes addition in a finite Abelian group G. Can we reduce the general
case to this special case by first locally mapping each x_i to x'_i in G,
and then securely computing the sum of all x'_i?

Such a reduction is captured by the abstract notion of *additive randomized
encoding* (ARE). An ARE of f(x_1,...,x_n) is an n-tuple of randomized local
mappings g_i(x_i) whose sum reveals the output of f but hides (essentially)
everything else about the inputs. I will present positive results, negative
results, and open questions about the existence of ARE with either
information-theoretic or computational security.

As an application of our positive results, we obtain (under a standard
cryptographic assumption) the first non-interactive secure computation
protocol for general functions f in the shuffle model, where parties can
post messages on an anonymous bulletin board. This implies a general
utility-preserving compiler from differential privacy in the central model
to (computational) differential privacy in the shuffle model.

Joint work with Shai Halevi, Eyal Kushilevitz, and Tal Rabin

Milk and Cookies at 4pm, Seminar to start at 4:15pm.