Nearly optimal private convolution

Nadia Fawaz, S. Muthukrishnan, Aleksandar Nikolov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

We study algorithms for computing the convolution of a private input x with a public input h, while satisfying the guarantees of (ε, δ)-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 an algorithm for computing convolutions which satisfies (ε, δ)-differentially privacy and is nearly optimal for every public h, i.e. is instance optimal with respect to the public input. We prove optimality via spectral lower bounds on the hereditary discrepancy of convolution matrices. Our algorithm is very efficient - it is essentially no more computationally expensive than a Fast Fourier Transform.

Original languageEnglish (US)
Title of host publicationAlgorithms, ESA 2013 - 21st Annual European Symposium, Proceedings
Pages445-456
Number of pages12
DOIs
StatePublished - Sep 24 2013
Event21st Annual European Symposium on Algorithms, ESA 2013 - Sophia Antipolis, France
Duration: Sep 2 2013Sep 4 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8125 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other21st Annual European Symposium on Algorithms, ESA 2013
CountryFrance
CitySophia Antipolis
Period9/2/139/4/13

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Nearly optimal private convolution'. Together they form a unique fingerprint.

Cite this