Document Open Access Logo

Differential Privacy on Finite Computers

Authors Victor Balcer, Salil Vadhan

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.43.pdf
  • Filesize: 0.65 MB
  • 21 pages

Document Identifiers

Author Details

Victor Balcer
Salil Vadhan

Cite As Get BibTex

Victor Balcer and Salil Vadhan. Differential Privacy on Finite Computers. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 43:1-43:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ITCS.2018.43

Abstract

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. We use a case study: 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.

Subject Classification

Keywords
  • Algorithms
  • Differential Privacy
  • Discrete Computation
  • Histograms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Victor Balcer and Salil P. Vadhan. Differential privacy on finite computers. CoRR, abs/1709.05396, 2017. URL: http://arxiv.org/abs/1709.05396.
  2. Amos Beimel, Hai Brenner, Shiva Prasad Kasiviswanathan, and Kobbi Nissim. Bounds on the sample complexity for private learning and private data release. Machine learning, 94(3):401-437, 2014. Google Scholar
  3. Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to noninteractive database privacy. J. ACM, 60(2):12:1-12:25, 2013. URL: http://dx.doi.org/10.1145/2450142.2450148.
  4. Mark Bun, Kobbi Nissim, and Uri Stemmer. Simultaneous private learning of multiple concepts. In Madhu Sudan, editor, Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 369-380. ACM, 2016. URL: http://dx.doi.org/10.1145/2840728.2840747.
  5. Bryan Cai, Constantinos Daskalakis, and Gautam Kamath. Priv'it: Private and sample efficient identity testing. CoRR, abs/1703.10127, 2017. URL: http://arxiv.org/abs/1703.10127.
  6. Karthekeyan Chandrasekaran, Justin Thaler, Jonathan Ullman, and Andrew Wan. Faster private release of marginals on small databases. In Moni Naor, editor, Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014, pages 387-402. ACM, 2014. URL: http://dx.doi.org/10.1145/2554797.2554833.
  7. Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, and Homin K. Lee. Submodular functions are noise stable. In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, pages 1586-1592, Philadelphia, PA, USA, 2012. Society for Industrial and Applied Mathematics. Google Scholar
  8. Thomas H Cormen. Introduction to algorithms. MIT press, 2009. Google Scholar
  9. Graham Cormode, Cecilia M. Procopiuc, Divesh Srivastava, and Thanh T. L. Tran. Differentially private summaries for sparse data. In Alin Deutsch, editor, 15th International Conference on Database Theory, ICDT '12, Berlin, Germany, March 26-29, 2012, pages 299-311. ACM, 2012. URL: http://dx.doi.org/10.1145/2274576.2274608.
  10. Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Eurocrypt, volume 4004, pages 486-503. Springer, 2006. Google Scholar
  11. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In TCC, volume 3876, pages 265-284. Springer, 2006. Google Scholar
  12. Cynthia Dwork, Aleksandar Nikolov, and Kunal Talwar. Efficient algorithms for privately releasing marginals via convex relaxations. Discrete & Computational Geometry, 53(3):650-673, 2015. URL: http://dx.doi.org/10.1007/s00454-015-9678-x.
  13. Ivan Gazeau, Dale Miller, and Catuscia Palamidessi. Preserving differential privacy under finite-precision semantics. In Luca Bortolussi and Herbert Wiklicky, editors, Proceedings 11th International Workshop on Quantitative Aspects of Programming Languages and Systems, QAPL 2013, Rome, Italy, March 23-24, 2013., volume 117 of EPTCS, pages 1-18, 2013. URL: http://dx.doi.org/10.4204/EPTCS.117.1.
  14. Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. Universally utility-maximizing privacy mechanisms. SIAM Journal on Computing, 41(6):1673-1693, 2012. Google Scholar
  15. Anupam Gupta, Aaron Roth, and Jonathan Ullman. Iterative constructions and private data release. Theory of Cryptography, pages 339-356, 2012. Google Scholar
  16. Moritz Hardt, Guy N. Rothblum, and Rocco A. Servedio. Private data release via learning thresholds. In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '12, pages 168-187, Philadelphia, PA, USA, 2012. Society for Industrial and Applied Mathematics. Google Scholar
  17. Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 705-714. ACM, 2010. URL: http://dx.doi.org/10.1145/1806689.1806786.
  18. Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793-826, 2011. Google Scholar
  19. Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alexandros Ntoulas. Releasing search queries and clicks privately. In Juan Quemada, Gonzalo León, Yoëlle S. Maarek, and Wolfgang Nejdl, editors, Proceedings of the 18th International Conference on World Wide Web, WWW 2009, Madrid, Spain, April 20-24, 2009, pages 171-180. ACM, 2009. URL: http://dx.doi.org/10.1145/1526709.1526733.
  20. Jacobus Hendricus van Lint. Introduction to coding theory. Springer, 1982. Google Scholar
  21. Ilya Mironov. On significance of the least significant bits for differential privacy. In Ting Yu, George Danezis, and Virgil D. Gligor, editors, the ACM Conference on Computer and Communications Security, CCS'12, Raleigh, NC, USA, October 16-18, 2012, pages 650-661. ACM, 2012. URL: http://dx.doi.org/10.1145/2382196.2382264.
  22. Arnold Schönhage. Schnelle multiplikation von polynomen über körpern der charakteristik 2. Acta Informatica, 7(4):395-398, 1977. Google Scholar
  23. Justin Thaler, Jonathan Ullman, and Salil Vadhan. Faster algorithms for privately releasing marginals. In International Colloquium on Automata, Languages, and Programming, pages 810-821. Springer, 2012. Google Scholar
  24. Jonathan Ullman and Salil P. Vadhan. Pcps and the hardness of generating private synthetic data. In TCC, volume 6597, pages 400-416. Springer, 2011. Google Scholar
  25. Joachim Von Zur Gathen and Jürgen Gerhard. Modern computer algebra. Cambridge university press, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact