License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2009.2329
URN: urn:nbn:de:0030-drops-23298
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2329/
Go to the corresponding LIPIcs Volume Portal

Madeira, André ; Muthukrishnan, S.

Functionally Private Approximations of Negligibly-Biased Estimators

pdf-format:
09005.MadeiraAndre.2329.pdf (0.2 MB)

Abstract

We study functionally private approximations.
An approximation function $g$ is {\em 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
$L_p$-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-random {\em
functions} (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 {\em any} problem.

Our second application result states that every problem in some subclasses of \SP of
hard counting problems admit efficient and functionally private approximation protocols.
This result is based on a functionally private approximation for the \SDNF
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.

BibTeX - Entry

@InProceedings{madeira_et_al:LIPIcs:2009:2329,
  author =	{Andr{\'e} Madeira and S. Muthukrishnan},
  title =	{{Functionally Private Approximations of Negligibly-Biased Estimators}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{323--334},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Ravi Kannan and K. Narayan Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2329},
  URN =		{urn:nbn:de:0030-drops-23298},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2329},
  annote =	{Keywords: Functional privacy, privacy, data streams, #P-complete}
}

Keywords: Functional privacy, privacy, data streams, #P-complete
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Issue Date: 2009
Date of publication: 14.12.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI