Differential Privacy on Finite Computers
We consider the problem of designing and analyzing differentially private algorithms that can be implemented on discrete models of computation in strict polynomial time, motivated by known attacks on floating point implementations of real-arithmetic differentially private algorithms (Mironov, CCS 20...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Labor Dynamics Institute
2019-09-01
|
| Series: | The Journal of Privacy and Confidentiality |
| Subjects: | |
| Online Access: | https://journalprivacyconfidentiality.org/index.php/jpc/article/view/679 |
| _version_ | 1811286786402418688 |
|---|---|
| author | Victor Balcer Salil Vadhan |
| author_facet | Victor Balcer Salil Vadhan |
| author_sort | Victor Balcer |
| collection | DOAJ |
| description | We consider the problem of designing and analyzing differentially private algorithms that can be implemented on discrete models of computation in strict polynomial time, motivated by known attacks on floating point implementations of real-arithmetic differentially private algorithms (Mironov, CCS 2012) and the potential for timing attacks on expected polynomial-time algorithms.
As a case study, we examine the basic problem of approximating the histogram of a categorical dataset over a possibly large data universe X.
The classic Laplace Mechanism (Dwork, McSherry, Nissim, Smith, TCC 2006 and J. Privacy \& Confidentiality 2017) does not satisfy our requirements, as it is based on real arithmetic, and natural discrete analogues, such as the Geometric Mechanism (Ghosh, Roughgarden, Sundarajan, STOC 2009 and SICOMP 2012), take time at least linear in |X|, which can be exponential in the bit length of the input.
In this paper, we provide strict polynomial-time discrete algorithms for approximate histograms whose simultaneous accuracy (the maximum error over all bins) matches that of the Laplace Mechanism up to constant factors, while retaining the same (pure) differential privacy guarantee.
One of our algorithms produces a sparse histogram as output.
Its ``"per-bin accuracy" (the error on individual bins) is worse than that of the Laplace Mechanism by a factor of log|X|, but we prove a lower bound showing that this is necessary for any algorithm that produces a sparse histogram.
A second algorithm avoids this lower bound, and matches the per-bin accuracy of the Laplace Mechanism, by producing a compact and efficiently computable representation of a dense histogram; it is based on an (n+1)-wise independent implementation of an appropriately clamped version of the Discrete Geometric Mechanism. |
| first_indexed | 2024-04-13T03:07:05Z |
| format | Article |
| id | doaj.art-ff80f289751a4caea86e45985703ad32 |
| institution | Directory Open Access Journal |
| issn | 2575-8527 |
| language | English |
| last_indexed | 2024-04-13T03:07:05Z |
| publishDate | 2019-09-01 |
| publisher | Labor Dynamics Institute |
| record_format | Article |
| series | The Journal of Privacy and Confidentiality |
| spelling | doaj.art-ff80f289751a4caea86e45985703ad322022-12-22T03:05:14ZengLabor Dynamics InstituteThe Journal of Privacy and Confidentiality2575-85272019-09-019210.29012/jpc.679Differential Privacy on Finite ComputersVictor Balcer0Salil Vadhan1Harvard UniversityHarvard UniversityWe consider the problem of designing and analyzing differentially private algorithms that can be implemented on discrete models of computation in strict polynomial time, motivated by known attacks on floating point implementations of real-arithmetic differentially private algorithms (Mironov, CCS 2012) and the potential for timing attacks on expected polynomial-time algorithms. As a case study, we examine the basic problem of approximating the histogram of a categorical dataset over a possibly large data universe X. The classic Laplace Mechanism (Dwork, McSherry, Nissim, Smith, TCC 2006 and J. Privacy \& Confidentiality 2017) does not satisfy our requirements, as it is based on real arithmetic, and natural discrete analogues, such as the Geometric Mechanism (Ghosh, Roughgarden, Sundarajan, STOC 2009 and SICOMP 2012), take time at least linear in |X|, which can be exponential in the bit length of the input. In this paper, we provide strict polynomial-time discrete algorithms for approximate histograms whose simultaneous accuracy (the maximum error over all bins) matches that of the Laplace Mechanism up to constant factors, while retaining the same (pure) differential privacy guarantee. One of our algorithms produces a sparse histogram as output. Its ``"per-bin accuracy" (the error on individual bins) is worse than that of the Laplace Mechanism by a factor of log|X|, but we prove a lower bound showing that this is necessary for any algorithm that produces a sparse histogram. A second algorithm avoids this lower bound, and matches the per-bin accuracy of the Laplace Mechanism, by producing a compact and efficiently computable representation of a dense histogram; it is based on an (n+1)-wise independent implementation of an appropriately clamped version of the Discrete Geometric Mechanism.https://journalprivacyconfidentiality.org/index.php/jpc/article/view/679AlgorithmsDifferential PrivacyDiscrete ComputationHistograms |
| spellingShingle | Victor Balcer Salil Vadhan Differential Privacy on Finite Computers The Journal of Privacy and Confidentiality Algorithms Differential Privacy Discrete Computation Histograms |
| title | Differential Privacy on Finite Computers |
| title_full | Differential Privacy on Finite Computers |
| title_fullStr | Differential Privacy on Finite Computers |
| title_full_unstemmed | Differential Privacy on Finite Computers |
| title_short | Differential Privacy on Finite Computers |
| title_sort | differential privacy on finite computers |
| topic | Algorithms Differential Privacy Discrete Computation Histograms |
| url | https://journalprivacyconfidentiality.org/index.php/jpc/article/view/679 |
| work_keys_str_mv | AT victorbalcer differentialprivacyonfinitecomputers AT salilvadhan differentialprivacyonfinitecomputers |