2019

Local Differential Privacy: a tutorial

Bebensee, Björn

Understand

In the past decade analysis of big data has proven to be extremely valuable in many contexts.

Local Differential Privacy (LDP) is a state-of-the-art approach which allows statistical computations while protecting each individual user's privacy.
Unlike Differential Privacy no trust in a central authority is necessary as noise is added to user inputs locally.
In this paper we give an overview over different LDP algorithms for problems such as locally private heavy hitter identification and spatial data collection.

Built on

Warner, S.L.: Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association 60
Original
1907
Earlier work this paper cites.
Evfimievski, A., Gehrke, J., Srikant, R.: Limiting privacy breaches in privacy preserving data mining. In: Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. pp. 211–222. ACM (2003)
2003
Earlier work this paper cites.
Cormode, G., Muthukrishnan, S.: An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms 55
2005
Earlier work this paper cites.
Dwork, C.: Differential privacy. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) Automata, Languages and Programming. pp. 1–12. Springer Berlin Heidelberg, Berlin, Heidelberg (2006)
2006
Earlier work this paper cites.
Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: Theory of cryptography conference. pp. 265–284. Springer (2006)
2006
Earlier work this paper cites.
Mishra, N., Sandler, M.: Privacy via pseudorandom sketches. In: Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. pp. 143–152. ACM (2006)
2006
Earlier work this paper cites.
Kasiviswanathan, S.P., Lee, H.K., Nissim, K., Raskhodnikova, S., Smith, A.: What can we learn privately? SIAM Journal on Computing 40
2011
Earlier work this paper cites.
Chan, T.H., Shi, E., Song, D.: Optimal lower bound for differentially private multi-party aggregation. In: European Symposium on Algorithms. pp. 277–288. Springer (2012)
2012
Earlier work this paper cites.
Cormode, G., Procopiuc, C., Srivastava, D., Shen, E., Yu, T.: Differentially private spatial decompositions. In: 2012 IEEE 28th International Conference on Data Engineering. pp. 20–31. IEEE (2012)
2012
Earlier work this paper cites.
Hsu, J., Khanna, S., Roth, A.: Distributed private heavy hitters. In: International Colloquium on Automata, Languages, and Programming. pp. 461–472. Springer (2012)
2012
Earlier work this paper cites.

Similar

Li, N., Qardaji, W., Su, D.: On sampling, anonymization, and differential privacy or, k-anonymization meets differential privacy. In: Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security. pp. 32–33. ACM (2012)
2012
Cited alongside, same era.
Duchi, J.C., Jordan, M.I., Wainwright, M.J.: Local privacy and statistical minimax rates. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. pp. 429–438. IEEE (2013)
2013
Cited alongside, same era.
Qardaji, W., Yang, W., Li, N.: Differentially private grids for geospatial data. In: 2013 IEEE 29th international conference on data engineering (ICDE). pp. 757–768. IEEE (2013)
2013
Cited alongside, same era.
Erlingsson, Ú., Pihur, V., Korolova, A.: Rappor: Randomized aggregatable privacy-preserving ordinal response. In: Proceedings of the 2014 ACM SIGSAC conference on computer and communications security. pp. 1054–1067. ACM (2014)
2014
Cited alongside, same era.
Bassily, R., Smith, A.: Local, private, efficient protocols for succinct histograms. In: Proceedings of the forty-seventh annual ACM symposium on Theory of computing. pp. 127–135. ACM (2015)
2015
Cited alongside, same era.
Chen, R., Li, H., Qin, A., Kasiviswanathan, S.P., Jin, H.: Private spatial data aggregation in the local setting. In: 2016 IEEE 32nd International Conference on Data Engineering (ICDE). pp. 289–300. IEEE (2016)
2016
Cited alongside, same era.
Nguyên, T.T., Xiao, X., Yang, Y., Hui, S.C., Shin, H., Shin, J.: Collecting and analyzing data from smart device users with local differential privacy. arXiv preprint arXiv:1606.05053 (2016)
Original
2016
Cited alongside, same era.
Qin, Z., Yang, Y., Yu, T., Khalil, I., Xiao, X., Ren, K.: Heavy hitter estimation over set-valued data with local differential privacy. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. pp. 192–203. ACM (2016)
2016
Cited alongside, same era.
Apple Inc., Differential Privacy Team: Learning with privacy at scale (2017)
2017
Cited alongside, same era.

Then

Avent, B., Korolova, A., Zeber, D., Hovden, T., Livshits, B.: { \{ BLENDER } \} : Enabling local search with a hybrid differential privacy model. In: 26th USENIX Security Symposium (USENIX Security 17). pp. 747–764 (2017)
2017
Later among the works it cites.
Bassily, R., Nissim, K., Stemmer, U., Thakurta, A.: Practical locally private heavy hitters. CoRR abs/1707.04982
Original
2017
Later among the works it cites.
Ding, B., Kulkarni, J., Yekhanin, S.: Collecting telemetry data privately. In: Advances in Neural Information Processing Systems. pp. 3571–3580 (2017)
2017
Later among the works it cites.
Qin, Z., Yu, T., Yang, Y., Khalil, I., Xiao, X., Ren, K.: Generating synthetic decentralized social graphs with local differential privacy. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. pp. 425–438. ACM (2017)
2017
Later among the works it cites.
Tang, J., Korolova, A., Bai, X., Wang, X., Wang, X.: Privacy loss in apple’s implementation of differential privacy on macos 10.12. arXiv preprint arXiv:1709.02753 (2017)
Original
2017
Later among the works it cites.
Thakurta, A.G., Vyrros, A.H., Vaishampayan, U.S., Kapoor, G., Freudinger, J., Prakash, V.V., Legendre, A., Duplinsky, S.: Emoji frequency detection and deep link frequency (Jul 11 2017), US Patent 9,705,908
2017
Later among the works it cites.
Wang, T., Blocki, J., Li, N., Jha, S.: Locally differentially private protocols for frequency estimation. In: 26th USENIX Security Symposium (USENIX Security 17). pp. 729–745 (2017)
2017
Later among the works it cites.
Bun, M., Nelson, J., Stemmer, U.: Heavy hitters and the structure of local privacy. In: Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. pp. 435–447. ACM (2018)
2018
Later among the works it cites.
Wang, T., Li, N., Jha, S.: Locally differentially private frequent itemset mining. In: 2018 IEEE Symposium on Security and Privacy (SP). pp. 127–143. IEEE (2018)
2018
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…