Additive Randomized Encodings

Speaker: Yuval Ishai , Technion

Date: Tuesday, November 14, 2023

Time: 4:15 PM to 5:30 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: G-449 KIVA

Event Type: Seminar

Room Description: G-449 KIVA

Host: Henry Corrigan-Gibbs , CSAIL MIT


Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:,

Reminder Subject: TALK: Yuval Ishai: 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.

Research Areas:
Algorithms & Theory

Impact Areas:

See other events that are part of the Theory of Computation (ToC) Seminar 2023.

Created by Nathan Higgins Email at Monday, October 23, 2023 at 11:11 AM.