Private Approximations and Big Data

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.