Efficient Private Query Release via Polynomial Approximation
Francesco Aldà · arXiv (Cornell University) · 2015
We investigate the problem of privately answering queries on databases consisting of points in $[0,1]^{\ell}$. We prove the following results. First, we show that there exists a computationally efficient $\varepsilon$-differentially private mechanism that releases a query class parametrized by additively separable H\older continuous functions. Second, we show that, if the query class is instead parametrized by additively separable analytic functions, the accuracy can be significantly boosted. Moreover, both our mechanisms operate in the non-interactive setting, i.e. they output a fixed data structure which can be used to answer all the queries of interest without further accessing the sensitive database.