Implementations of differentially private analyses

Since the advent of differential privacy, a number of systems supporting differentially private data analyses have been implemented and deployed.

"Pinq" redirects here. It is not to be confused with Pink or Pinque.

Research Projects and Prototypes
  • PINQ: An API implemented in C#[1].
  • Airavat: A MapReduce-based system implemented in Java hardened with SELinux-like access control.[2]
  • Fuzz: Time-constant implementation in Caml Light of a domain-specific language.[3]
  • GUPT: Implementation of the sample-and-aggregate framework.[4]
  • KTELO: A framework and system for answering linear counting queries.[5]

Real-World Deployments
  • OnTheMap: Interactive tool for exploration of US commute patterns.[6][7]
  • PSI (Ψ): A Private data Sharing Interface developed as part of the Harvard University Privacy Tools Project.[10]
  • Application usage statistics in Microsoft Windows 10.[12]
  • Flex: A SQL-based system developed for internal Uber analytics.[13][14]
  • TensorFlow Privacy: An open-source library for differentially private machine learning.[15][16]
  • Census 2020 synthetic microdata.[17]

Attacks on Implementations

In addition to standard defects of software artifacts that can be identified using testing or fuzzing, implementations of differentially private mechanisms may suffer from the following vulnerabilities:

  • Subtle algorithmic or analytical mistakes.[18][19]
  • Timing side-channel attacks.[3] In contrast with timing attacks against implementations of cryptographic algorithms that typically have low leakage rate and must be followed with non-trivial cryptanalysis, a timing channel may lead to a catastrophic compromise of a differentially private system, since a targeted attack can be used to exfiltrate the very bit that the system is designed to hide.
  • Leakage through floating-point arithmetic.[20] Differentially private algorithms are typically presented in the language of probability distributions, which most naturally lead to implementations using floating-point arithmetic. The abstraction of floating-point arithmetic is leaky, and without careful attention to details, a naive implementation may fail to provide differential privacy. (This is particularly the case for ε-differential privacy, which does not allow any probability of failure, even in the worst case.) For example, the support of a textbook sampler of the Laplace distribution (required, for instance, for the Laplace mechanism) is less than 80% of all double-precision floating point numbers; moreover, the support for distributions with different means are not identical. A single sample from a naïve implementation of the Laplace mechanism allows distinguishing between two adjacent datasets with probability more than 35%.
  • Timing channel through floating-point arithmetic.[21] Unlike operations over integers that are typically constant-time on modern CPUs, floating-point arithmetic exhibits significant input-dependent timing variability.[22] Handling of subnormals can be particularly slow, as much as by ×100 compared to the typical case.[23]
gollark: Too bad.
gollark: It doesn't. It obeys the same rules as humans.
gollark: Humans are better at this, with a little practice.
gollark: v1 literally had to have a hardcoded patch to stop it not noticing instant loss/win situations.
gollark: ?????

References
  1. McSherry, Frank (1 September 2010). "Privacy integrated queries" (PDF). Communications of the ACM. 53 (9): 89–97. doi:10.1145/1810891.1810916.
  2. Roy, Indrajit; Setty, Srinath T.V.; Kilzer, Ann; Shmatikov, Vitaly; Witchel, Emmett (April 2010). "Airavat: Security and Privacy for MapReduce" (PDF). Proceedings of the 7th Usenix Symposium on Networked Systems Design and Implementation (NSDI).
  3. Haeberlen, Andreas; Pierce, Benjamin C.; Narayan, Arjun (2011). "Differential Privacy Under Fire". 20th USENIX Security Symposium.
  4. Mohan, Prashanth; Thakurta, Abhradeep; Shi, Elaine; Song, Dawn; Culler, David E. "GUPT: Privacy Preserving Data Analysis Made Easy". Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. pp. 349–360. doi:10.1145/2213836.2213876.
  5. Zhang, Dan; McKenna, Ryan; Kotsogiannis, Ios; Hay, Michael; Machanavajjhala, Ashwin; Miklau, Gerome (June 2018). "KTELO: A Framework for Defining Differentially-Private Computations". SIGMOD'18: 2018 International Conference on Management of Data: 115–130. arXiv:1808.03555. doi:10.1145/3183713.3196921.
  6. "OnTheMap".
  7. Machanavajjhala, Ashwin; Kifer, Daniel; Abowd, John; Gehrke, Johannes; Vilhuber, Lars (April 2008). "Privacy: Theory meets Practice on the Map". 2008 IEEE 24th International Conference on Data Engineering: 277–286. doi:10.1109/ICDE.2008.4497436. ISBN 978-1-4244-1836-7.
  8. Erlingsson, Úlfar. "Learning statistics with privacy, aided by the flip of a coin".
  9. Erlingsson, Úlfar; Pihur, Vasyl; Korolova, Aleksandra (November 2014). "RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response". Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security: 1054–1067. arXiv:1407.6981. Bibcode:2014arXiv1407.6981E. doi:10.1145/2660267.2660348.
  10. Gaboardi, Marco; Honaker, James; King, Gary; Nissim, Kobbi; Ullman, Jonathan; Vadhan, Salil; Murtagh, Jack (June 2016). "PSI (Ψ): a Private data Sharing Interface".
  11. Differential Privacy Team (December 2017). "Learning with Privacy at Scale". Apple Machine Learning Journal. 1 (8).
  12. Ding, Bolin; Kulkarni, Janardhan; Yekhanin, Sergey (December 2017). "Collecting Telemetry Data Privately". 31st Conference on Neural Information Processing Systems: 3574–3583. arXiv:1712.01524. Bibcode:2017arXiv171201524D.
  13. Tezapsidis, Katie (Jul 13, 2017). "Uber Releases Open Source Project for Differential Privacy".
  14. Johnson, Noah; Near, Joseph P.; Song, Dawn (January 2018). "Towards Practical Differential Privacy for SQL Queries". Proceedings of the VLDB Endowment. 11 (5): 526–539. arXiv:1706.09479. doi:10.1145/3187009.3177733.
  15. Radebaugh, Carey; Erlingsson, Ulfar (March 6, 2019). "Introducing TensorFlow Privacy: Learning with Differential Privacy for Training Data".
  16. "TensorFlow Privacy". 2019-08-09.
  17. Abowd, John M. (August 2018). "The U.S. Census Bureau Adopts Differential Privacy". Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining: 2867. doi:10.1145/3219819.3226070. ISBN 9781450355520.
  18. McSherry, Frank (25 February 2018). "Uber's differential privacy .. probably isn't".
  19. Lyu, Min; Su, Dong; Li, Ninghui (1 February 2017). "Understanding the sparse vector technique for differential privacy". Proceedings of the VLDB Endowment. 10 (6): 637–648. arXiv:1603.01699. doi:10.14778/3055330.3055331.
  20. Mironov, Ilya (October 2012). "On Significance of the Least Significant Bits for Differential Privacy" (PDF). Proceedings of the 2012 ACM Conference on Computer and Communications Security (ACM CCS). ACM: 650–661. doi:10.1145/2382196.2382264. ISBN 9781450316514.
  21. Andrysco, Marc; Kohlbrenner, David; Mowery, Keaton; Jhala, Ranjit; Lerner, Sorin; Shacham, Hovav (May 2015). "On Subnormal Floating Point and Abnormal Timing". 2015 IEEE Symposium on Security and Privacy: 623–639. doi:10.1109/SP.2015.44. ISBN 978-1-4673-6949-7.
  22. Kohlbrenner, David; Shacham, Hovav (August 2017). "On the Effectiveness of Mitigations Against Floating-point Timing Channels". Proceedings of the 26th USENIX Conference on Security Symposium. USENIX Association: 69–81.
  23. Dooley, Isaac; Kale, Laxmikant (September 2006). "Quantifying the interference caused by subnormal floating-point values" (PDF). Proceedings of the Workshop on Operating System Interference in High Performance Applications.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.