Nearly optimal private convolution

DOI10.1007/978-3-642-40450-4_38MaRDI QIDQ2849335zbMATH OpenOpenAlexFDO

Authors Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov

Publication date 17 September 2013

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

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

Mathematics Subject Classification ID

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

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.

Recommendations

• The algorithmic foundations of differential privacy
• Differential privacy on finite computers
• Private data release via learning thresholds
• Privacy-preserving statistical estimation with optimal convergence rates

Cited in

(5)

• Lower bounds on the error of query sets under the differentially-private matrix mechanism
• Computational differential privacy from lattice-based cryptography
• \textsc{OptStream}: releasing time series privately
• EPIC: efficient private image classification (or: learning from the masters)
• Aggregation of time-series data under differential privacy

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)