Nearly optimal private convolution

DOI10.1007/978-3-642-40450-4_38zbMATH Open1394.68111arXiv1301.6447OpenAlexW2125178505MaRDI QIDQ2849335FDOQ2849335

Authors: Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov 

Publication date: 17 September 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We study computing the convolution of a private input $x$ with a public input $h$, while satisfying the guarantees of $(epsilon,delta)$-differential privacy. Convolution is a fundamental operation, intimately related to Fourier Transforms. In our setting, the private input may represent a time series of sensitive events or a histogram of a database of confidential personal information. Convolution then captures important primitives including linear filtering, which is an essential tool in time series analysis, and aggregation queries on projections of the data. We give a nearly optimal algorithm for computing convolutions while satisfying $(epsilon,delta)$-differential privacy. Surprisingly, we follow the simple strategy of adding independent Laplacian noise to each Fourier coefficient and bounding the privacy loss using the composition theorem of Dwork, Rothblum, and Vadhan. We derive a closed form expression for the optimal noise to add to each Fourier coefficient using convex programming duality. Our algorithm is very efficient -- it is essentially no more computationally expensive than a Fast Fourier Transform. To prove near optimality, we use the recent discrepancy lowerbounds of Muthukrishnan and Nikolov and derive a spectral lower bound using a characterization of discrepancy in terms of determinants.

Full work available at URL: https://arxiv.org/abs/1301.6447

Recommendations

• The algorithmic foundations of differential privacy
• The geometry of differential privacy: the sparse and approximate cases
• Differential privacy on finite computers
• Private data release via learning thresholds
• Privacy-preserving statistical estimation with optimal convergence rates

Mathematics Subject Classification ID

Cryptography (94A60) Database theory (68P15) Numerical methods for discrete and fast Fourier transforms (65T50)

Cited In (3)

• Lower bounds on the error of query sets under the differentially-private matrix mechanism
• The geometry of differential privacy: the small database and approximate cases
• EPIC: efficient private image classification (or: learning from the masters)

This page was built for publication: Nearly optimal private convolution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2849335)