Local Differential Privacy: a tutorial

Bj\"orn Bebensee

Local Differential Privacy: a tutorial

T0 review · 0 major / 1 minor · reviewed 2026-05-24 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Local Differential Privacy lets each user add noise to their own data so aggregate statistics can be computed without trusting any central party.

desk verdict A 2019 tutorial that recaps existing LDP work with no new results or fixes to open problems. read the letter →

arxiv 1907.11908 v1 pith:4YAC6MWE submitted 2019-07-27 cs.CR

Björn Bebensee This is my paper · ORCID

classification cs.CR

keywords localdifferentialprivacyheavyhittersspatialdatacollectionpreservingcomputationtutorial

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

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.

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.

Watch

Extended reading notes

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.

Load-bearing premise

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

Editorial extensions

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.

Reading between the lines

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

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 · score 0.0 of 10

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.

Assumptions & free parameters 0 free parameters · 0 assumptions · 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.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Local Differential Privacy: a tutorial." pith.science (2026). https://pith.science/paper/4YAC6MWE

@misc{pith2026190711908,
  author       = {Pith},
  title        = {Pith review of: Local Differential Privacy: a tutorial},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4YAC6MWE}},
  note         = {Machine review of arXiv:1907.11908}
}

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.

Figures

Figures reproduced from arXiv: 1907.11908 by the authors.

**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. The users ar… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Auditing of Unlearning Algorithms
cs.LG 2026-07 accept novelty 6.0 of 10

An auditor based on membership inference attacks computes valid lower bounds on the unlearning parameter ε, empirically separating certified unlearning methods (small bounds) from heuristic ones (large bounds).
Aggregating Data for Optimal and Private Learning
cs.LG 2024-11 conditional novelty 6.0 of 10

For multiple instance regression and learning from label proportions, optimal data bagging for linear regression reduces approximately to k-means clustering over labels or features, and the mechanisms can be made labe...
Statistic Maximal Leakage
cs.IT 2024-11 conditional novelty 5.0 of 10

Statistic maximal leakage is a new prior-independent, secret-specific privacy measure with additive composition and an efficient min-cost flow computation for deterministic mechanisms.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages · cited by 3 Pith papers

[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 Pith review 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

Show all 28 references

[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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

2006
[20]

arXiv preprint arXiv:1606.05053 (2016)

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)

2016 arXiv
[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)

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–

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)

2017
[24]

arXiv preprint arXiv:1709.02753 (2017)

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)

2017 arXiv
[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

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)

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)

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)

1965

Pith tools

Reviewed May 24, 2026 · model on record in the stance chip above.

[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 Pith review 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