Local Differential Privacy: a tutorial

Bj\"orn Bebensee

arxiv: 1907.11908 · v1 · pith:4YAC6MWEnew · submitted 2019-07-27 · 💻 cs.CR

Local Differential Privacy: a tutorial

Bj\"orn Bebensee This is my paper

Pith reviewed 2026-05-24 14:51 UTC · model grok-4.3

classification 💻 cs.CR

keywords local differential privacydifferential privacyheavy hittersspatial data collectionprivacy preserving computationtutorial

0 comments

The pith

Local Differential Privacy lets each user add noise to their own data so aggregate statistics can be computed without trusting any central party.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper surveys existing algorithms that apply Local Differential Privacy to concrete tasks such as identifying frequent items and collecting spatial data. It shows how noise added at each user's device protects individual inputs while still allowing useful population-level results. A reader would care because the approach removes the need for a trusted server that might otherwise see raw sensitive information. The survey also flags open problems that limit current LDP deployments.

Core claim

Local Differential Privacy is presented as a technique in which each user perturbs their own input locally before sending it onward, enabling statistical computations on the collected data while providing formal privacy guarantees without any trusted central authority; the paper then details algorithms that realize this approach for heavy hitter identification and spatial data collection and closes with a discussion of remaining open problems.

What carries the argument

Local Differential Privacy, the privacy definition and associated mechanisms in which noise is added to each user's data at the source so that no central collector ever sees unperturbed values.

If this is right

Heavy hitter identification becomes possible under local privacy constraints without a trusted server.
Spatial data such as locations can be collected while each contributor retains local privacy.
Several open problems in LDP are identified as directions that must still be resolved.
The same local-noise approach can be applied to other statistical tasks beyond the two detailed examples.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Implementations of the surveyed algorithms could be directly tested on real device data streams to measure utility loss.
The open problems listed may connect to efficiency or composition questions when LDP is combined with other local mechanisms.
The tutorial structure suggests it could serve as a starting point for researchers new to applying LDP in distributed settings.

Load-bearing premise

The algorithms and problem statements summarized in the paper correctly represent the LDP literature as it stood in 2019.

What would settle it

A check that locates either a factual error in one of the algorithm descriptions or an important LDP paper published before mid-2019 that the survey omits.

Figures

Figures reproduced from arXiv: 1907.11908 by Bj\"orn Bebensee.

**Figure 1.** Figure 1: Illustration of the SVIM and SVSM protocols from [27]. Users (left) are partitioned into five groups. Aggregator (right) runs SVIM to identify frequent items with first three groups, then SVSM to identify frequent itemsets with last two groups. The SVIM protocol works similarly to LDPMiner but makes use of the privacy amplification effect to achieve a higher accuracy. The protocol works in four steps. Th… view at source ↗

read the original abstract

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. Finally, we will give an outlook on open problems in LDP.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

A 2019 tutorial that recaps existing LDP work with no new results or fixes to open problems.

read the letter

This paper is a tutorial from 2019 that overviews local differential privacy without adding any new results or fixing open issues. It walks through the basics and some applications but stays within the existing literature. It does a solid job explaining how LDP differs from the central model by having each user add noise locally. The parts on heavy hitter identification and spatial data collection bring together the main algorithms that were around then, and the outlook section flags some open problems that were relevant at the time. The structure is clear enough that it could serve as an entry point. The downside is that its value rests entirely on getting the summaries right. We can't tell from the abstract if there are any small inaccuracies in how the algorithms are presented, and the paper is now dated since privacy research has moved on since 2019. There are also no implementations or worked examples included that would help with practical use. This is the kind of thing a student or someone new to the area might find helpful as background reading. If you already know the LDP papers, it probably won't tell you anything you don't already know. I wouldn't recommend it for peer review as original work because it doesn't claim novelty. It could be okay in a survey track or as educational material, but the contribution is limited to collecting and organizing existing knowledge.

Referee Report

0 major / 1 minor

Summary. The manuscript is a tutorial on Local Differential Privacy (LDP). It defines LDP as a mechanism in which each user perturbs their own data locally before transmission, eliminating the need for a trusted central curator. The paper surveys existing LDP algorithms for tasks including heavy-hitter identification and spatial data collection, and concludes with a discussion of open problems.

Significance. If the algorithmic summaries are accurate and complete as of 2019, the tutorial could provide a useful consolidated introduction to LDP techniques for researchers entering the area. The work contains no original theorems, proofs, or experiments; its value therefore rests entirely on the clarity and fidelity of its exposition of prior results.

minor comments (1)

[Abstract] Abstract: the claim that the paper gives 'an overview over different LDP algorithms' is too vague; a sentence listing the specific problems treated (heavy hitters, spatial collection) and the level of technical detail would help readers assess suitability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their review and positive recommendation of minor revision. The report contains no specific major comments requiring point-by-point response.

Circularity Check

0 steps flagged

Tutorial overview with no derivations or predictions

full rationale

The paper is explicitly a tutorial providing an overview of existing LDP algorithms for heavy hitters, spatial data collection, and open problems, with no original theorems, proofs, empirical claims, fitted parameters, or derivation chains. No load-bearing steps reduce to self-citations or inputs by construction; the content is summarization of prior work as of 2019, which is self-contained against external benchmarks and carries no circularity risk.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No new claims, parameters, axioms, or entities are introduced; the paper is an expository summary of prior work on local differential privacy.

pith-pipeline@v0.9.0 · 5595 in / 890 out tokens · 17173 ms · 2026-05-24T14:51:53.302164+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages · 3 internal anchors

[1]

Apple Inc., Diﬀerential Privacy Team: Learning with privacy at scale (2017)

work page 2017
[2]

In: 26th USENIX Security Symposium (USENIX Security 17)

Avent, B., Korolova, A., Zeber, D., Hovden, T., Livshits, B.: {BLENDER}: En- abling local search with a hybrid diﬀerential privacy model. In: 26th USENIX Security Symposium (USENIX Security 17). pp. 747–764 (2017)

work page 2017
[3]

Practical Locally Private Heavy Hitters

Bassily, R., Nissim, K., Stemmer, U., Thakurta, A.: Practical locally private heavy hitters. CoRR abs/1707.04982 (2017), http://arxiv.org/abs/1707.04982

work page internal anchor Pith review Pith/arXiv arXiv 2017
[4]

In: Proceedings of the forty-seventh annual ACM symposium on Theory of computing

Bassily, R., Smith, A.: Local, private, eﬃcient protocols for succinct histograms. In: Proceedings of the forty-seventh annual ACM symposium on Theory of computing. pp. 127–135. ACM (2015)

work page 2015
[5]

In: Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

Bun, M., Nelson, J., Stemmer, U.: Heavy hitters and the structure of local pri- vacy. In: Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. pp. 435–447. ACM (2018)

work page 2018
[6]

In: European Symposium on Algorithms

Chan, T.H., Shi, E., Song, D.: Optimal lower bound for diﬀerentially private multi- party aggregation. In: European Symposium on Algorithms. pp. 277–288. Springer (2012)

work page 2012
[7]

In: 2016 IEEE 32nd International Conference on Data Engineering (ICDE)

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)

work page 2016
[8]

Journal of Algorithms 55(1), 58–75 (2005)

Cormode, G., Muthukrishnan, S.: An improved data stream summary: the count- min sketch and its applications. Journal of Algorithms 55(1), 58–75 (2005)

work page 2005
[9]

In: 2012 IEEE 28th International Conference on Data Engineering

Cormode, G., Procopiuc, C., Srivastava, D., Shen, E., Yu, T.: Diﬀerentially pri- vate spatial decompositions. In: 2012 IEEE 28th International Conference on Data Engineering. pp. 20–31. IEEE (2012)

work page 2012
[10]

In: Ad- vances in Neural Information Processing Systems

Ding, B., Kulkarni, J., Yekhanin, S.: Collecting telemetry data privately. In: Ad- vances in Neural Information Processing Systems. pp. 3571–3580 (2017)

work page 2017
[11]

In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science

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)

work page 2013
[12]

In: Bugliesi, M., Preneel, B., Sassone, V., We- gener, I

Dwork, C.: Diﬀerential privacy. In: Bugliesi, M., Preneel, B., Sassone, V., We- gener, I. (eds.) Automata, Languages and Programming. pp. 1–12. Springer Berlin Heidelberg, Berlin, Heidelberg (2006)

work page 2006
[13]

In: Theory of cryptography conference

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)

work page 2006
[14]

In: Proceedings of the 2014 ACM SIGSAC conference on computer and communications security

Erlingsson, ´U., 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)

work page 2014
[15]

In: Proceedings of the twenty-second ACM SIGMOD- SIGACT-SIGART symposium on Principles of database systems

Evﬁmievski, 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)

work page 2003
[16]

In: International Colloquium on Automata, Languages, and Programming

Hsu, J., Khanna, S., Roth, A.: Distributed private heavy hitters. In: International Colloquium on Automata, Languages, and Programming. pp. 461–472. Springer (2012)

work page 2012
[17]

Kasiviswanathan, S.P., Lee, H.K., Nissim, K., Raskhodnikova, S., Smith, A.: What can we learn privately? SIAM Journal on Computing 40(3), 793–826 (2011)

work page 2011
[18]

In: Proceedings of the 7th ACM Local Diﬀerential Privacy: a tutorial 17 Symposium on Information, Computer and Communications Security

Li, N., Qardaji, W., Su, D.: On sampling, anonymization, and diﬀerential privacy or, k-anonymization meets diﬀerential privacy. In: Proceedings of the 7th ACM Local Diﬀerential Privacy: a tutorial 17 Symposium on Information, Computer and Communications Security. pp. 32–33. ACM (2012)

work page 2012
[19]

In: Proceedings of the twenty-ﬁfth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

Mishra, N., Sandler, M.: Privacy via pseudorandom sketches. In: Proceedings of the twenty-ﬁfth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. pp. 143–152. ACM (2006)

work page 2006
[20]

Collecting and Analyzing Data from Smart Device Users with Local Differential Privacy

Nguyˆ en, T.T., Xiao, X., Yang, Y., Hui, S.C., Shin, H., Shin, J.: Collecting and an- alyzing data from smart device users with local diﬀerential privacy. arXiv preprint arXiv:1606.05053 (2016)

work page internal anchor Pith review Pith/arXiv arXiv 2016
[21]

In: 2013 IEEE 29th international conference on data engineering (ICDE)

Qardaji, W., Yang, W., Li, N.: Diﬀerentially private grids for geospatial data. In: 2013 IEEE 29th international conference on data engineering (ICDE). pp. 757–768. IEEE (2013)

work page 2013
[22]

In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security

Qin, Z., Yang, Y., Yu, T., Khalil, I., Xiao, X., Ren, K.: Heavy hitter estimation over set-valued data with local diﬀerential privacy. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. pp. 192–

work page 2016
[23]

In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security

Qin, Z., Yu, T., Yang, Y., Khalil, I., Xiao, X., Ren, K.: Generating synthetic decentralized social graphs with local diﬀerential privacy. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. pp. 425–438. ACM (2017)

work page 2017
[24]

Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12

Tang, J., Korolova, A., Bai, X., Wang, X., Wang, X.: Privacy loss in apple’s imple- mentation of diﬀerential privacy on macos 10.12. arXiv preprint arXiv:1709.02753 (2017)

work page internal anchor Pith review Pith/arXiv arXiv 2017
[25]

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

work page 2017
[26]

In: 26th USENIX Security Symposium (USENIX Security 17)

Wang, T., Blocki, J., Li, N., Jha, S.: Locally diﬀerentially private protocols for frequency estimation. In: 26th USENIX Security Symposium (USENIX Security 17). pp. 729–745 (2017)

work page 2017
[27]

In: 2018 IEEE Symposium on Security and Privacy (SP)

Wang, T., Li, N., Jha, S.: Locally diﬀerentially private frequent itemset mining. In: 2018 IEEE Symposium on Security and Privacy (SP). pp. 127–143. IEEE (2018)

work page 2018
[28]

Journal of the American Statistical Association 60(309), 63–69 (1965)

Warner, S.L.: Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association 60(309), 63–69 (1965)

work page 1965

[1] [1]

Apple Inc., Diﬀerential Privacy Team: Learning with privacy at scale (2017)

work page 2017

[2] [2]

In: 26th USENIX Security Symposium (USENIX Security 17)

Avent, B., Korolova, A., Zeber, D., Hovden, T., Livshits, B.: {BLENDER}: En- abling local search with a hybrid diﬀerential privacy model. In: 26th USENIX Security Symposium (USENIX Security 17). pp. 747–764 (2017)

work page 2017

[3] [3]

Practical Locally Private Heavy Hitters

Bassily, R., Nissim, K., Stemmer, U., Thakurta, A.: Practical locally private heavy hitters. CoRR abs/1707.04982 (2017), http://arxiv.org/abs/1707.04982

work page internal anchor Pith review Pith/arXiv arXiv 2017

[4] [4]

In: Proceedings of the forty-seventh annual ACM symposium on Theory of computing

Bassily, R., Smith, A.: Local, private, eﬃcient protocols for succinct histograms. In: Proceedings of the forty-seventh annual ACM symposium on Theory of computing. pp. 127–135. ACM (2015)

work page 2015

[5] [5]

In: Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

Bun, M., Nelson, J., Stemmer, U.: Heavy hitters and the structure of local pri- vacy. In: Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems. pp. 435–447. ACM (2018)

work page 2018

[6] [6]

In: European Symposium on Algorithms

Chan, T.H., Shi, E., Song, D.: Optimal lower bound for diﬀerentially private multi- party aggregation. In: European Symposium on Algorithms. pp. 277–288. Springer (2012)

work page 2012

[7] [7]

In: 2016 IEEE 32nd International Conference on Data Engineering (ICDE)

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)

work page 2016

[8] [8]

Journal of Algorithms 55(1), 58–75 (2005)

Cormode, G., Muthukrishnan, S.: An improved data stream summary: the count- min sketch and its applications. Journal of Algorithms 55(1), 58–75 (2005)

work page 2005

[9] [9]

In: 2012 IEEE 28th International Conference on Data Engineering

Cormode, G., Procopiuc, C., Srivastava, D., Shen, E., Yu, T.: Diﬀerentially pri- vate spatial decompositions. In: 2012 IEEE 28th International Conference on Data Engineering. pp. 20–31. IEEE (2012)

work page 2012

[10] [10]

In: Ad- vances in Neural Information Processing Systems

Ding, B., Kulkarni, J., Yekhanin, S.: Collecting telemetry data privately. In: Ad- vances in Neural Information Processing Systems. pp. 3571–3580 (2017)

work page 2017

[11] [11]

In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science

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)

work page 2013

[12] [12]

In: Bugliesi, M., Preneel, B., Sassone, V., We- gener, I

Dwork, C.: Diﬀerential privacy. In: Bugliesi, M., Preneel, B., Sassone, V., We- gener, I. (eds.) Automata, Languages and Programming. pp. 1–12. Springer Berlin Heidelberg, Berlin, Heidelberg (2006)

work page 2006

[13] [13]

In: Theory of cryptography conference

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)

work page 2006

[14] [14]

In: Proceedings of the 2014 ACM SIGSAC conference on computer and communications security

Erlingsson, ´U., 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)

work page 2014

[15] [15]

In: Proceedings of the twenty-second ACM SIGMOD- SIGACT-SIGART symposium on Principles of database systems

Evﬁmievski, 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)

work page 2003

[16] [16]

In: International Colloquium on Automata, Languages, and Programming

Hsu, J., Khanna, S., Roth, A.: Distributed private heavy hitters. In: International Colloquium on Automata, Languages, and Programming. pp. 461–472. Springer (2012)

work page 2012

[17] [17]

Kasiviswanathan, S.P., Lee, H.K., Nissim, K., Raskhodnikova, S., Smith, A.: What can we learn privately? SIAM Journal on Computing 40(3), 793–826 (2011)

work page 2011

[18] [18]

In: Proceedings of the 7th ACM Local Diﬀerential Privacy: a tutorial 17 Symposium on Information, Computer and Communications Security

Li, N., Qardaji, W., Su, D.: On sampling, anonymization, and diﬀerential privacy or, k-anonymization meets diﬀerential privacy. In: Proceedings of the 7th ACM Local Diﬀerential Privacy: a tutorial 17 Symposium on Information, Computer and Communications Security. pp. 32–33. ACM (2012)

work page 2012

[19] [19]

In: Proceedings of the twenty-ﬁfth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

Mishra, N., Sandler, M.: Privacy via pseudorandom sketches. In: Proceedings of the twenty-ﬁfth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. pp. 143–152. ACM (2006)

work page 2006

[20] [20]

Collecting and Analyzing Data from Smart Device Users with Local Differential Privacy

Nguyˆ en, T.T., Xiao, X., Yang, Y., Hui, S.C., Shin, H., Shin, J.: Collecting and an- alyzing data from smart device users with local diﬀerential privacy. arXiv preprint arXiv:1606.05053 (2016)

work page internal anchor Pith review Pith/arXiv arXiv 2016

[21] [21]

In: 2013 IEEE 29th international conference on data engineering (ICDE)

Qardaji, W., Yang, W., Li, N.: Diﬀerentially private grids for geospatial data. In: 2013 IEEE 29th international conference on data engineering (ICDE). pp. 757–768. IEEE (2013)

work page 2013

[22] [22]

In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security

Qin, Z., Yang, Y., Yu, T., Khalil, I., Xiao, X., Ren, K.: Heavy hitter estimation over set-valued data with local diﬀerential privacy. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. pp. 192–

work page 2016

[23] [23]

In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security

Qin, Z., Yu, T., Yang, Y., Khalil, I., Xiao, X., Ren, K.: Generating synthetic decentralized social graphs with local diﬀerential privacy. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. pp. 425–438. ACM (2017)

work page 2017

[24] [24]

Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12

Tang, J., Korolova, A., Bai, X., Wang, X., Wang, X.: Privacy loss in apple’s imple- mentation of diﬀerential privacy on macos 10.12. arXiv preprint arXiv:1709.02753 (2017)

work page internal anchor Pith review Pith/arXiv arXiv 2017

[25] [25]

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

work page 2017

[26] [26]

In: 26th USENIX Security Symposium (USENIX Security 17)

Wang, T., Blocki, J., Li, N., Jha, S.: Locally diﬀerentially private protocols for frequency estimation. In: 26th USENIX Security Symposium (USENIX Security 17). pp. 729–745 (2017)

work page 2017

[27] [27]

In: 2018 IEEE Symposium on Security and Privacy (SP)

Wang, T., Li, N., Jha, S.: Locally diﬀerentially private frequent itemset mining. In: 2018 IEEE Symposium on Security and Privacy (SP). pp. 127–143. IEEE (2018)

work page 2018

[28] [28]

Journal of the American Statistical Association 60(309), 63–69 (1965)

Warner, S.L.: Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association 60(309), 63–69 (1965)

work page 1965