Differential Privacy of Mathematical Functions

Differential privacy is a privacy notion in statistical databases. However, we find that the notion can be extended to mathematical functions. By studying the differential privacy problem of a simple mathematical function we find two differentially private mechanisms which are applicable for almost all query functions. By using these mechanisms each query function can have custom-designed mechanisms, which implies that our mechanisms are not based on (global or local) sensitivitybased methods—some methods extensively used to construct differentially private mechanisms. Our mechanisms are so flexible that they can be used to balance the accuracy of the outputs of different datasets. We also present some interesting impossibility results of differential privacy. The above results motivate us to explore the mathematical treatment of differential privacy. We present an abstract model of differential privacy in which a differential privacy problem is modeled as finding a randomized mapping between two metric spaces. Some basic structures of differential privacy are presented, such as the {I i }i, {Ri }i sequences. Some of the properties of these structures, such as the convergence, are also discussed (for some special cases). Finally, we apply our theoretical results to the subgraph counting problem and the linear query problem. The experiments show that our mechanisms (in most cases) have more accurate results than the state of the art mechanisms. ar X iv :1 70 2. 02 72 1v 1 [ cs .C R ] 9 F eb 2 01 7

• Publication year

  2017

• Venue

  arXiv.org

• Publication date

  2017-02-09

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1702.02721
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Private Release of Graph Statistics using Ladder Functions

  2015cited by this paper
• The matrix mechanism: optimizing linear counting queries under differential privacy

  2015cited by this paper
• PrivBayes: private data release via bayesian networks

  2014cited by this paper
• Differential privacy in metric spaces: Numerical, categorical and functional data under the one roof

  2014cited by this paper
• Analyze gauss: optimal bounds for privacy-preserving principal component analysis

  2014cited by this paper
• The Algorithmic Foundations of Differential Privacy

  2014cited by this paper
• Efficient Algorithm for Privately Releasing Smooth Queries

  2013cited by this paper
• Optimal Noise Adding Mechanisms for Approximate Differential Privacy

  2013cited by this paper
• Analyzing Graphs with Node Differential Privacy

  2013cited by this paper
• Recursive mechanism: towards node differential privacy and unrestricted joins

  2013cited by this paper
• Broadening the Scope of Differential Privacy Using Metrics

  2013cited by this paper
• Optimal error of query sets under the differentially-private matrix mechanism

  2012cited by this paper
• The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy

  2012cited by this paper
• Functional Mechanism: Regression Analysis under Differential Privacy

  2012cited by this paper
• Differentially private sequential data publication via variable-length n-grams

  2012cited by this paper
• The Optimal Noise-Adding Mechanism in Differential Privacy

  2012cited by this paper
• Accurate and efficient private release of datacubes and contingency tables

  2012cited by this paper
• The geometry of differential privacy: the sparse and approximate cases

  2012influential reference
• Exploiting Metric Structure for Efficient Private Query Release

  2012cited by this paper
• Lower Bounds in Differential Privacy

  2011cited by this paper
• Publishing set-valued data via differential privacy

  2011cited by this paper
• Beating randomized response on incoherent matrices

  2011cited by this paper
• Private analysis of graph structure

  2011cited by this paper
• Iterative Constructions and Private Data Release

  2011cited by this paper
• A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis

  2010cited by this paper
• A Simple and Practical Algorithm for Differentially Private Data Release

  2010cited by this paper
• Impossibility of Differentially Private Universally Optimal Mechanisms

  2010cited by this paper
• Interactive privacy via the median mechanism

  2009cited by this paper
• On the geometry of differential privacy

  2009cited by this paper
• Smooth sensitivity and sampling in private data analysis

  2007influential reference
• Pseudorandom Bits for Polynomials

  2007influential reference
• Differential Privacy

  2006influential reference
• Algorithmic applications of low-distortion geometric embeddings

  2001influential reference

• No citing papers are available for this paper.