Practical privacy: the SuLQ framework. We consider a statistical database in which a trusted administrator introduces noise to the query responses with the goal of maintaining privacy of individual database entries. In such a database, a query consists of a pair (S, f) where S is a set of rows in the database and f is a function mapping database rows to {0, 1}. The true answer is ΣiεS f(di), and a noisy version is released as the response to the query. Results of Dinur, Dwork, and Nissim show that a strong form of privacy can be maintained using a surprisingly small amount of noise -- much less than the sampling error -- provided the total number of queries is sublinear in the number of database rows. We call this query and (slightly) noisy reply the SuLQ (Sub-Linear Queries) primitive. The assumption of sublinearity becomes reasonable as databases grow increasingly large.We extend this work in two ways. First, we modify the privacy analysis to real-valued functions f and arbitrary row types, as a consequence greatly improving the bounds on noise required for privacy. Second, we examine the computational power of the SuLQ primitive. We show that it is very powerful indeed, in that slightly noisy versions of the following computations can be carried out with very few invocations of the primitive: principal component analysis, k means clustering, the Perceptron Algorithm, the ID3 algorithm, and (apparently!) all algorithms that operate in the in the statistical query learning model [11].

This software is also peer reviewed by journal TOMS.

References in zbMATH (referenced in 111 articles )

Showing results 1 to 20 of 111.
Sorted by year (citations)

1 2 3 4 5 6 next

  1. Beimel, Amos; Nissim, Kobbi; Stemmer, Uri: Private learning and sanitization: pure vs. approximate differential privacy (2016)
  2. Bun, Mark; Zhandry, Mark: Order-revealing encryption and the hardness of private learning (2016)
  3. Choromanska, Anna; Choromanski, Krzysztof; Jagannathan, Geetha; Monteleoni, Claire: Differentially-private learning of low dimensional manifolds (2016)
  4. Kowalczyk, Lucas; Malkin, Tal; Ullman, Jonathan; Zhandry, Mark: Strong hardness of privacy from weak traitor tracing (2016)
  5. Ullman, Jonathan: Answering $n^2+o(1)$ counting queries with differential privacy is hard (2016)
  6. Balcan, Maria Florina; Feldman, Vitaly: Statistical active learning algorithms for noise tolerance and differential privacy (2015)
  7. Benkaouz, Yahya; Erradi, Mohammed: A distributed protocol for privacy preserving aggregation with non-permanent participants (2015)
  8. Feldman, Vitaly; Xiao, David: Sample complexity bounds on differentially private learning via communication complexity (2015)
  9. Ghosh, Arpita; Roth, Aaron: Selling privacy at auction (2015)
  10. Abraham, Ittai; Gavoille, Cyril; Gupta, Anupam; Neiman, Ofer; Talwar, Kunal: Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs (2014)
  11. Agarwal, Pankaj K.; Sharathkumar, R.: Approximation algorithms for bipartite matching with metric and geometric costs (2014)
  12. Aggarwal, Divesh; Dodis, Yevgeniy; Lovett, Shachar: Non-malleable codes from additive combinatorics (extended abstract) (2014)
  13. Alistarh, Dan; Censor-Hillel, Keren; Shavit, Nir: Are lock-free concurrent algorithms practically wait-free? (2014)
  14. Andoni, Alexandr; Nikolov, Aleksandar; Onak, Krzysztof; Yaroslavtsev, Grigory: Parallel algorithms for geometric graph problems (2014)
  15. Artemenko, Sergei; Shaltiel, Ronen: Pseudorandom generators with optimal seed length for non-Boolean poly-size circuits (2014)
  16. Awasthi, Pranjal; Balcan, Maria Florina; Long, Philip M.: The power of localization for efficiently learning linear separators with noise (2014)
  17. Babichenko, Yakov: Query complexity of approximate Nash equilibria (2014)
  18. Barak, Boaz; Kelner, Jonathan A.; Steurer, David: Rounding sum-of-squares relaxations (2014)
  19. Beimel, Amos; Brenner, Hai; Kasiviswanathan, Shiva Prasad; Nissim, Kobbi: Bounds on the sample complexity for private learning and private data release (2014)
  20. Belazzougui, Djamal: Linear time construction of compressed text indices in compact space (2014)

1 2 3 4 5 6 next