Speaker: Kobbi Nissim , Ben-Gurion University

Date: Friday, November 01, 2013

Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G449

Event Type:

Room Description:

Host: Shafi Goldwasser

Contact: Holly A Jones,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:


One of the main issues of big data -- scalability -- can be addressed by trading accuracy with approximation. Approximation seems hence a compelling strategy also for achieving efficiency in the context of computations performed over sensitive data, as in secure multiparty computation protocols. Care must be taken, however, so that the trading of an exact computation with an approximation would not result in leakage of more than what is intended. In 2003, Feigenbaum et al. introduced the notion of private approximation: the result of a private approximation algorithm should reveal no additional information beyond what follows from the output of the function being approximated. Subsequent work resulted in mixed results: On one hand, there exist families of problems for which private approximations enable efficient protocols. On the other hand, the approach can be shown to fail w.r.t. other problems in a very strong sense: for these problems every efficient private approximation algorithm must leak information beyond the exact computation. The latter negative results motivated looking into notions of approximation that circumvent impossibility by permitting small (quantified and well defined) leakage. In the talk, we will introduce the notion of private approximation, motivate it and examine it (and some variants) as a strategy for secure computation over large datasets. We will review the main positive and negative results, and discuss some research directions.

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information Security Seminar Seminars Fall 2013 / Spring 2014.

Created by Holly A Jones Email at Monday, October 28, 2013 at 8:58 AM.