TY - GEN

T1 - Functionally private approximations of negligibly-biased estimators

AU - Madeira, André

AU - Muthukrishnan, S.

PY - 2009

Y1 - 2009

N2 - We study functionally private approximations. An approximation function g is functionally private with respect to f if, for any input x, g(x) reveals no more information about x than f(x). Our main result states that a function f admits an efficiently-computable functionally private approximation g if there exists an efficiently-computable and negligibly-biased estimator for f. Contrary to previous generic results, our theorem is more general and has a wider application reach. We provide two distinct applications of the above result to demonstrate its flexibility. In the data stream model, we provide a functionally private approximation to the Lp-norm estimation problem, a quintessential application in streaming, using only polylogarithmic space in the input size. The privacy guarantees rely on the use of pseudo-randomfunctions (PRF) (a stronger cryptographic notion than pseudo-random generators) of which can be based on common cryptographic assumptions. The application of PRFs in this context appears to be novel and we expect other results to follow suit. Moreover, this is the first known functionally private streaming result for any problem. Our second application result states that every problem in some subclasses of #P of hard counting problems admit efficient and functionally private approximation protocols. This result is based on a functionally private approximation for the #DNF problem (or estimating the number of satisfiable truth assignments to a Boolean formula in disjunctive normal form), which is an application of our main theorem and previously known results.

AB - We study functionally private approximations. An approximation function g is functionally private with respect to f if, for any input x, g(x) reveals no more information about x than f(x). Our main result states that a function f admits an efficiently-computable functionally private approximation g if there exists an efficiently-computable and negligibly-biased estimator for f. Contrary to previous generic results, our theorem is more general and has a wider application reach. We provide two distinct applications of the above result to demonstrate its flexibility. In the data stream model, we provide a functionally private approximation to the Lp-norm estimation problem, a quintessential application in streaming, using only polylogarithmic space in the input size. The privacy guarantees rely on the use of pseudo-randomfunctions (PRF) (a stronger cryptographic notion than pseudo-random generators) of which can be based on common cryptographic assumptions. The application of PRFs in this context appears to be novel and we expect other results to follow suit. Moreover, this is the first known functionally private streaming result for any problem. Our second application result states that every problem in some subclasses of #P of hard counting problems admit efficient and functionally private approximation protocols. This result is based on a functionally private approximation for the #DNF problem (or estimating the number of satisfiable truth assignments to a Boolean formula in disjunctive normal form), which is an application of our main theorem and previously known results.

UR - http://www.scopus.com/inward/record.url?scp=79959761684&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79959761684&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.FSTTCS.2009.2329

DO - 10.4230/LIPIcs.FSTTCS.2009.2329

M3 - Conference contribution

AN - SCOPUS:79959761684

SN - 9783939897132

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 323

EP - 334

BT - Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009 - 29th Annual Conference, Proceedings

T2 - 29th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009

Y2 - 15 December 2009 through 17 December 2009

ER -