Pith. sign in

REVIEW 4 major objections 5 minor 59 references

Composition for Pufferfish Privacy

T0 review · 4 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash

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

Pith's one-line read Pufferfish privacy composes only when mechanisms are constrained by differential-privacy-style inequalities, and the paper gives an a(b)-influence-curve recipe that converts any per-entry differentially private mechanism into a composable P

desk verdict Solid theory with a real new tool (a(b)-influence), but the abstract oversells and the experiments lean on a fitted prior that isn't a conservative privacy guarantee. read the letter →

arxiv 2602.02718 v2 pith:LWRBLU5E submitted 2026-02-02 cs.CR

Jiamu Bai , Guanlin He , Xin Gu , Daniel Kifer , Kiwan Maeng This is my paper · ORCID
classification cs.CR
keywords Pufferfishprivacydifferentialcompositionposterior-baseda(b)-influencecurvecollapseMarkovchainexponentialmechanism
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

Pufferfish privacy protects correlated data by requiring that a Bayesian attacker's beliefs about secrets change little after seeing the output, but until now it did not compose: mechanisms that leak nothing in a single run could reveal the whole dataset when run twice. This paper proves that for Pufferfish mechanisms to compose linearly, they must also satisfy differential-privacy-style inequalities—called NfC constraints—and that the only such constraints that survive post-processing are DP inequalities themselves. On the constructive side, the paper introduces the a(b)-influence curve, which upper-bounds how much a secret can leak through the database entries outside a chosen b-entry region. Any mechanism satisfying per-entry ε_DP-differential privacy with ε_DP ≤ (ε_puffer − a)/b then satisfies ε_puffer-Pufferfish privacy, and multiple releases compose sub-linearly because the correlation penalty a is paid once. A sympathetic reader would care because this makes correlated-data privacy reusable for many sequential queries, and the paper demonstrates the payoff by building an exponential-mechanism Pufferfish algorithm for noisy top-k queries on Markov-chain data.

What carries the argument

The load-bearing object is the a(b)-influence curve (Definition 7). For a fixed family of priors Θ and secret pairs S, it answers: after optimally marking b entries as the high-influence region H and the rest as low-influence L, what is the worst-case log-ratio—over priors and secrets—of the probability of observing the low-influence entries under one secret versus the other? The curve a(b) is an upper bound on this number over all secret pairs, it is monotonically non-increasing, and it plays the role that sensitivity plays in DP: an upper bound suffices for a guarantee, while a tighter bound yields better utility. It is the mechanism that converts a per-entry group-privacy loss bε_DP into

What would settle it

Fit a first-order Markov chain to the training portion of a real sequence dataset and compute the tight a(b) curve from Theorem 8. Then generate a test sequence from a process with a long-range latent correlation not captured by that chain, run a per-entry DP mechanism with ε_DP = (ε_puffer − a)/b, and check whether some secret's posterior odds ratio exceeds exp(ε_puffer). Exceeding it would demonstrate that the sufficiency claim fails once the prior family is misspecified. Alternatively, search for a mechanism satisfying a non-DP NfC constraint (a convex combination with two nonzero entries)

Watch

Extended reading notes

Core claim

The central claim is a necessary-and-sufficient characterization of composable Pufferfish privacy. Necessarily, if a collection of mechanisms satisfies ε_puffer-Pufferfish and composes linearly, then for every secret pair and dataset there is a convex combination of counterfactual datasets such that the log-likelihood inequality of Equation 1 holds; these NfC constraints generalize DP's inequalities, and Theorem 5 shows that any non-redundant set of them that is post-processing invariant must consist entirely of DP-style constraints. Sufficiently, given a point (a,b) on the a(b)-influence curve of the prior family Θ, any per-entry ε_DP-differential privacy mechanism with ε_DP ≤ (ε_puffer − a

Load-bearing premise

The guarantee holds only for the family of priors Θ used to compute the a(b)-influence curve, so the curator must be able to supply a valid upper bound a(b) for the true data-generating process; if the real correlations fall outside Θ or the bound is too small, the Pufferfish privacy claim does not follow.

Editorial extensions

If this is right

  • Any per-entry DP mechanism—Laplace, exponential, randomized response—becomes a composable Pufferfish mechanism once a point (a,b) on the influence curve is chosen; the paper demonstrates this with an exponential mechanism for noisy top-k queries that outperforms the Laplace-only prior mechanism.
  • The composition formula is sub-additive: releasing k Pufferfish mechanisms costs max_ℓ a_ℓ + Σ_ℓ (ε_puffer,ℓ − a_ℓ), which is always no more than Σ_ℓ ε_puffer,ℓ; the correlation penalty is paid only once.
  • The NfC theorem rules out a whole class of posterior-based mechanisms: any Pufferfish mechanism that avoids DP-style inequalities cannot guarantee linear composition, because privacy collapse can occur with as few as two runs.
  • For Markov-chain priors the a(b)-influence curve has a closed form (Theorem 8), so practitioners can compute exact or tight upper bounds and translate DP mechanisms without extra estimation error.
  • The translation is prior-agnostic in structure: it works for arbitrary tabular datasets and arbitrary Θ, so the recipe is not limited to Markov chains or Laplace noise.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: The paper treats the influence curve as an input supplied by the curator; an immediate next step would be to design automated, conservative estimators of a(b) from data or domain knowledge, since the guarantee is only as good as the upper bound used.
  • Editorial extension: The sufficiency theorem is stated for per-entry pure DP; translating (ε,δ)-DP or Rényi-DP mechanisms through the same curve could yield tighter or more flexible Pufferfish composition for approximate mechanisms.
  • Editorial extension: The privacy-collapse examples suggest a diagnostic: mechanisms whose output distributions across runs are nearly disjoint on the same secret are dangerous; this could be formalized as a testable property—checking the overlap of per-secret output supports—before deployment.
  • Editorial extension: If the curve decays quickly—as it does for weak Markov dependence—the framework predicts that correlated-data queries can be answered almost as cheaply as independent-record queries; this is testable by comparing the accuracy of a Pufferfish-translated exponential mechanism against plain DP on synthetic Markov chains with varying autocorrelation.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper addresses the lack of composition guarantees for Pufferfish privacy. It first constructs mechanisms whose single-run posterior leakage is zero but which reveal the dataset after two or three runs (Section 4). It then proves a necessary condition for a collection of Pufferfish mechanisms to compose linearly: the NfC constraints (Theorem 4), obtained via LP duality. Theorem 5 shows that among non-redundant NfC constraints, only DP-style one-hot constraints are post-processing invariant. On the sufficiency side, the paper introduces an a(b)-influence curve and proves that any per-entry εDP-DP mechanism can be translated into an εpuffer-Pufferfish mechanism (Theorem 6), and that such translated mechanisms compose sub-additively (Theorem 7). The framework is illustrated on binary Markov-chain and Gaussian priors and evaluated on two real-world temporal datasets for Top-K queries, where the proposed exponential-mechanism-based Pufferfish method outperforms MQM and group-DP baselines.

Significance. If the proofs hold, this is a valuable theoretical contribution. The NfC characterization is nontrivial, the LP-duality argument is carefully presented, and Theorem 5 gives a clean explanation for why DP-style inequalities are the natural post-processing-stable constraints to add. The a(b)-influence translation generalizes Song et al.'s Laplace-only MQM to arbitrary DP mechanisms and arbitrary priors, which is a useful practical recipe. The privacy-collapse examples are instructive and clearly motivate the paper. However, the advertised 'necessary and sufficient conditions' go beyond what is proved, and the experimental instantiation uses a narrow, data-fitted prior set that is not justified as a conservative Θ. These issues are fixable but require substantive revision.

major comments (4)
  1. [Abstract and Section 8] The paper advertises 'necessary and sufficient conditions' for linear composition. The body establishes two separate results: Theorem 4 gives a necessary condition (NfC), and Theorems 6–7 give sufficient conditions via per-entry DP and an a(b)-influence curve. No theorem shows that the NfC constraints are sufficient, nor that the sufficient conditions are necessary. The overclaim appears in the abstract ('necessary and sufficient conditions that must be added') and in Section 8 ('necessary and sufficient conditions for linear composition'). Please rephrase to 'necessary conditions, and separate sufficient conditions'.
  2. [Section 7.1.4 and Theorems 6–7] The experimental Pufferfish guarantee is instantiated with Θ equal to a single Markov chain fitted to the first 400 days of the same confidential dataset (Foursquare) or to the training participants (Capture24). Theorems 6–7 guarantee εpuffer-Pufferfish only for priors in Θ. If the true process is not the fitted chain, or if the transition matrix has sampling error, the reported εpuffer is not a privacy bound. The paper provides no confidence set, sensitivity analysis, or conservative family, and it does not state whether the training portion used to fit Θ is treated as public. This gap is load-bearing for the empirical claims; please either construct a conservative Θ (e.g., a neighborhood around the estimate) or clearly delimit the claim as a demonstration conditional on the fitted prior.
  3. [Section 7 vs. Section 6.3] The only analytical a(b)-influence result for Markov chains (Theorem 8) is for a binary chain. The experiments use a 78-state chain (Foursquare) and an 11-state chain (Capture24), but the paper never states how a(b) is computed or upper-bounded for these chains, nor does the appendix provide an algorithm. Without this, the εDP values used in the comparisons are not reproducible and the claimed utility gains are not verifiable. Please provide the computation used for general Markov chains (or state that a binary approximation was used, with justification).
  4. [Theorem 7] The proof assumes that the joint probability of outputs is the product of the individual mechanism probabilities given the dataset (see the step after Eq. (4) where max/min of the product is bounded by a product of exp(b1 εDPℓ)). This holds for independent/simultaneous mechanisms but not for adaptive compositions, unless a sequential conditioning argument is supplied. The text says 'applied sequentially' and the paper discusses composition in the DP sense, which usually covers adaptivity. If the claim is only for non-adaptive composition, it should say so explicitly; if adaptivity is intended, the proof must be extended.
minor comments (5)
  1. [Appendix C] The proof labeled 'Proof of Theorem 8' appears twice; the second proof is for Theorem 9 and is only a sketch. Please provide a complete proof or clearly mark Theorem 9 as a heuristic claim.
  2. [Theorem 3] The epsilon expression should use absolute values around the logarithms; as written, terms such as log(U_T/L_F) can be negative when U_T < L_F, but epsilon must be nonnegative.
  3. [Algorithms 1–2] The branch aℓ ≥ εpuffer sets εDPℓ = εpuffer/|I|; this corresponds to group DP with b = |I| and a(|I|) = 0, but this is not explained in the text. Please justify this fallback explicitly.
  4. [Definition 7] The statement that the a(b)-influence curve is 'monotonically non-increasing' is true for the tight a★(b) after optimization, but an arbitrary upper-bounding curve a(b) need not be monotone. Clarify that the curve is chosen to be non-increasing.
  5. [Theorem 4 statement] The statement contains the typo '0 ≤ 𝑒𝑝𝑠𝑖𝑙𝑜𝑛 < ∞'; it should be '0 ≤ ε < ∞'.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the theoretical derivation is self-contained; self-citations are definitional and non-load-bearing.

full rationale

The paper's central derivation—Theorems 4 through 7—is a sequence of conditional mathematical proofs, not a fitted prediction. Theorem 4 derives the NfC constraints from the definition of linear Pufferfish composition via linear programming duality; it does not assume the conclusion. Theorem 6 establishes εpuffer = b·εDP + a(b) directly from per-entry group privacy and the definition of the a(b)-influence curve (Definition 7). The a(b) curve is defined independently as a worst-case log-likelihood ratio over priors and secrets, and the theorem's proof combines that bound with group privacy; it is a proof, not a restatement of the definition. Theorem 7 then proves sub-additive composition from the same ingredients. The experimental prior (Section 7.1.4) is fitted to training data, but this affects only the applicability of the Pufferfish guarantee to the real data-generating process; it is not a circular step in the derivation of the theorems. The self-citation to Pufferfish [31] supplies the framework definition and the known non-composition warning; however, the paper independently demonstrates privacy collapse in Section 4, so the self-citation is not load-bearing for the central claim. The NfC and a(b) results are new and do not reduce to prior work. Overall, no target quantity is predicted from fitted values within the proof chain, so the paper is not circular; the score reflects only minor non-load-bearing self-citation.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The paper introduces the a(b)-influence curve as a mathematical object, not an ontological entity. The central theorems rely on standard convex/LP tools and the domain assumption that the curator can specify a valid prior family and bound the influence curve.

free parameters (3)
  • Markov chain transition parameters (p,q or full transition matrix) = fitted from training data (Foursquare first 400 days; Capture24 training participants)
    The a(b)-influence curve used in evaluation is computed from the fitted transition matrix; utility results depend on this fitted prior.
  • smoothing tolerance τ = 1e-5
    Chosen by hand for numerical stability in Section D.2.
  • Gaussian kernel length ℓ, region length δ, and support γ in synthetic example = ℓ∈{0.5,1,2,3,5}, γ=5, δ=0.1
    Synthetic example parameters for a(b)-influence visualization; not central to the main theorem.
assumptions (5)
  • domain assumption Finite dataset domain and finite mechanism output ranges (Theorem 4)
    The proof of Theorem 4 assumes finite (but arbitrarily large) dataset sets and finite output ranges, stated in Section 5.1.
  • standard math Strong duality of linear programs
    Used in the proof of Theorem 4 to convert primal LPs to dual LPs (Section 5.1 proof).
  • standard math Group privacy property of differential privacy
    Used in Theorems 6 and 7 to bound the effect of changing b entries (Section 6.2).
  • domain assumption The prior family Θ and the a(b)-influence bound are known and valid for the data
    Theorem 6's sufficiency is conditional on Θ satisfying a(b)-influence; in experiments Θ is a fitted Markov chain.
  • domain assumption Markov chain prior in experiments
    Section 7.1.4 assumes temporal data are generated by a first-order Markov chain and fits the transition matrix from training data.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Composition for Pufferfish Privacy." pith.science (2026). https://pith.science/paper/LWRBLU5E

@misc{pith2026260202718,
  author       = {Pith},
  title        = {Pith review of: Composition for Pufferfish Privacy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LWRBLU5E}},
  note         = {Machine review of arXiv:2602.02718}
}
abstract

When creating public data products out of confidential datasets, inferential/posterior-based privacy definitions, such as Pufferfish, provide compelling privacy semantics for data with correlations. However, such privacy definitions are rarely used in practice because they do not always compose. For example, it is possible to design algorithms for these privacy definitions that have no leakage when run once but reveal the entire dataset when run more than once. We prove necessary and sufficient conditions that must be added to ensure linear composition for Pufferfish mechanisms, hence avoiding such privacy collapse. These extra conditions turn out to be differential privacy-style inequalities, indicating that achieving both the interpretable semantics of Pufferfish for correlated data and composition benefits requires adopting differentially private mechanisms to Pufferfish. We show that such translation is possible through a concept called the $a(b)$-influence curve, and many existing differentially private algorithms can be translated with our framework into a composable Pufferfish algorithm. We illustrate the benefit of our new framework by designing composable Pufferfish algorithms for Markov chains that significantly outperform prior work.

Figures

Figures reproduced from arXiv: 2602.02718 by the authors.

Figure 1
Figure 1. An illustration of 𝑋𝑅, 𝑋𝑄, 𝑋𝑁 in Markov Chain. Song et al. [46] focused on a specific case where each entry of the database has a dependency described by a Markovian-structure graph 𝐺 [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. 𝑎(𝑏)-influence curves under different priors: (a) bi￾nary Markov chains and (b) multivariate Gaussian priors. on all variables in L influences 𝑋𝑖 only through these two closest low-influence nodes, and the leakage through L reduces to the leakage through those two nodes. Thus, finding an optimal 𝑎(𝑏)-influence curve becomes a one￾dimensional optimization problem of finding (𝑑𝐿, 𝑑𝑅) that maxi￾mizes the leakage. The m… view at source ↗
Figure 3
Figure 3. Example illustration with W𝜖 = M1,M2,M3, with each mechanism having 3, 2, and 4 unique outputs. In this illustration, 𝑘 = 4 vectors are picked. for each 𝜃 ∈ Θ and secret pair (𝑠1,𝑠2) ∈ 𝑆. For any positive integer 𝑟, by multiplying each 𝑐𝑖 by 𝑟 gives: 𝜖 ≥ log  P𝑛 ℓ=1 Pr𝜃 (Dℓ | 𝑠1) Q 𝑘 𝑖=1 𝑣𝑖[ℓ] 𝑟𝑐𝑖 1/ P 𝑗 𝑟𝑐 𝑗  P𝑛 ℓ=1 Pr𝜃 (Dℓ |𝑠2) Q 𝑘 𝑖=1 𝑣𝑖[ℓ] 𝑟𝑐𝑖 1/ P 𝑗 𝑟𝑐 𝑗 = log  P𝑛 ℓ=1 Pr𝜃 (Dℓ | 𝑠1) Q 𝑘 𝑖=1 [PITH_FULL_IMAG… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

59 extracted references · 1 canonical work pages

  1. [1]

    Odd O Aalen, Vernon T Farewell, Daniela De Angelis, Nicholas E Day, and O Nöel Gill. 1997. A Markov model for HIV disease progression including the effect of HIV diagnosis and treatment: application to AIDS prediction in England and Wales.Statistics in medicine16, 19 (1997), 2191–2210

    1997

  2. [2]

    John M. Abowd, Robert Ashmead, Ryan Cumings-Menon, Simson Garfinkel, Micah Heineck, Christine Heiss, Robert Johns, Daniel Kifer, Philip Leclerc, Ash- win Machanavajjhala, Brett Moran, William Sexton, Matthew Spence, and Pavel Zhuravlev. forthcoming. Preprint https://www.census.gov/library/working- papers/2022/adrm/CED-WP-2022-002.html. The 2020 Census Dis...

    2022

  3. [3]

    Raef Bassily, Adam Groce, Jonathan Katz, and Adam Smith. 2013. Coupled-worlds privacy: Exploiting adversarial uncertainty in statistical data privacy. In2013 IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE, 439–448

    2013

  4. [4]

    Raghav Bhaskar, Abhishek Bhowmick, Vipul Goyal, Srivatsan Laxman, and Abhradeep Thakurta. 2011. Noiseless database privacy. InInternational Con- ference on the Theory and Application of Cryptology and Information Security. Springer, 215–232

    2011

  5. [5]

    Guy Blanc, William Pires, and Toniann Pitassi. 2025. Differential privacy from axioms.arXiv preprint arXiv:2511.21876(2025)

    arXiv 2025

  6. [6]

    2006.Convex Analysis and Nonlinear Optimization: Theoryand Examples

    Jonathan Borwein and Adrian Lewis. 2006.Convex Analysis and Nonlinear Optimization: Theoryand Examples. Springer

    2006

  7. [7]

    Yang Cao, Masatoshi Yoshikawa, Yonghui Xiao, and Li Xiong. 2017. Quantifying differential privacy under temporal correlations. In2017 IEEE 33rd International Conference on Data Engineering (ICDE). IEEE, 821–832

    2017

  8. [8]

    Shing Chan, Yuan Hang, Catherine Tong, Aidan Acquah, Abram Schonfeldt, Jonathan Gershuny, and Aiden Doherty. 2024. CAPTURE-24: A large dataset of wrist-worn activity tracker data collected in the wild for human activity recognition.Scientific Data11, 1 (2024), 1135

    2024

Show all 59 references
  1. [9]

    S Chan Chang, R Walmsley, J Gershuny, T Harms, E Thomas, K Milton, P Kelly, C Foster, A Wong, N Gray, et al. 2021. Capture-24: Activity tracker dataset for Composition for Pufferfish Privacy human activity recognition. (2021)

    2021

  2. [10]

    Damien Desfontaines, Esfandiar Mohammadi, Elisabeth Krahmer, and David Basin. 2019. Differential privacy with partial knowledge.arXiv preprint arXiv:1905.00650(2019)

    2019 arXiv

  3. [11]

    Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017. Collecting Telemetry Data Privately. InProceedings of the 31st International Conference on Neural Information Processing Systems(Long Beach, California, USA)(NIPS’17). Curran Associates Inc., USA, 3574–3583. http://dl....

    2017

  4. [12]

    Ni Ding. 2022. Kantorovich mechanism for pufferfish privacy. InInternational Conference on Artificial Intelligence and Statistics. PMLR, 5084–5103

    2022

  5. [13]

    Ni Ding. 2024. Approximation of pufferfish privacy for Gaussian priors.IEEE Transactions on Information Forensics and Security19 (2024), 5630–5640

    2024

  6. [14]

    Zeyu Ding, Yuxin Wang, Yingtai Xiao, Guanhong Wang, Danfeng Zhang, and Daniel Kifer. 2023. Free gap estimates from the exponential mechanism, sparse vector, noisy max and related algorithms.The VLDB Journal32, 1 (2023), 23–48

    2023

  7. [15]

    Irit Dinur and Kobbi Nissim. 2003. Revealing information while preserving privacy. InProceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART sym- posium on Principles of database systems. 202–210

    2003

  8. [16]

    Cynthia Dwork. 2006. Differential privacy. InInternational colloquium on au- tomata, languages, and programming. Springer, 1–12

    2006

  9. [17]

    Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. 2006. Our data, ourselves: Privacy via distributed noise generation. InAnnual international conference on the theory and applications of cryptographic techniques. Springer, 486–503

    2006

  10. [18]

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Cali- brating noise to sensitivity in private data analysis. InTheory of cryptography conference. Springer, 265–284

    2006

  11. [19]

    Cynthia Dwork, Aaron Roth, et al. 2014. The algorithmic foundations of differ- ential privacy.Foundations and trends®in theoretical computer science9, 3–4 (2014), 211–407

    2014

  12. [20]

    Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. 2014. RAPPOR: Ran- domized Aggregatable Privacy-Preserving Ordinal Response. InProceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security (Scottsdale, Arizona, USA)(CCS ’14). ACM, New York, NY, ...

    2014

  13. [21]

    Farhad Farokhi. 2021. Noiseless privacy: Definition, guarantees, and applications. IEEE Transactions on Big Data9, 1 (2021), 51–62

    2021

  14. [22]

    Arpita Ghosh and Robert Kleinberg. 2016. Inferential privacy guarantees for differentially private mechanisms.arXiv preprint arXiv:1603.01508(2016)

    2016 arXiv

  15. [23]

    Google. [n.d.]. Tensorflow Privacy Github. https://github.com/tensorflow/ privacy

  16. [24]

    Xi He, Ashwin Machanavajjhala, and Bolin Ding. 2014. Blowfish privacy: Tuning privacy-utility trade-offs using policies. InProceedings of the 2014 ACM SIGMOD international conference on Management of data. 1447–1458

    2014

  17. [25]

    Ron S Jarmin, John M Abowd, Robert Ashmead, Ryan Cumings-Menon, Nathan Goldschlag, Michael B Hawes, Sallie Ann Keller, Daniel Kifer, Philip Leclerc, Jerome P Reiter, et al. 2023. An in-depth examination of requirements for dis- closure risk assessment.Proceedings of the Nation...

    2023

  18. [26]

    Kalervo Järvelin and Jaana Kekäläinen. 2002. Cumulated gain-based evaluation of IR techniques.ACM Transactions on Information Systems (TOIS)20, 4 (2002), 422–446

    2002

  19. [27]

    Near, and Dawn Song

    Noah Johnson, Joseph P. Near, and Dawn Song. 2018. Towards practical differ- ential privacy for SQL queries.Proc. VLDB Endow.11, 5 (Jan. 2018), 526–539. https://doi.org/10.1145/3187009.3177733

    2018

  20. [28]

    Johnson, Joseph P

    Noah M. Johnson, Joseph P. Near, Joseph M. Hellerstein, and Dawn Song. 2018. Chorus: Differential Privacy via Query Rewriting.CoRRabs/1809.07750 (2018). arXiv:1809.07750 http://arxiv.org/abs/1809.07750

    2018 arXiv

  21. [29]

    Peter Kairouz, Sewoong Oh, and Pramod Viswanath. 2015. The composition theorem for differential privacy. InInternational conference on machine learning. PMLR, 1376–1385

    2015

  22. [30]

    Daniel Kifer and Ashwin Machanavajjhala. 2011. No free lunch in data privacy. InProceedings of the 2011 ACM SIGMOD International Conference on Management of data. 193–204

    2011

  23. [31]

    Daniel Kifer and Ashwin Machanavajjhala. 2014. Pufferfish: A framework for mathematical privacy definitions.ACM Transactions on Database Systems (TODS) 39, 1 (2014), 1–36

    2014

  24. [32]

    2009.Probabilistic graphical models: principles and techniques

    Daphne Koller and Nir Friedman. 2009.Probabilistic graphical models: principles and techniques. MIT press

    2009

  25. [33]

    Wenjuan Liang, Hong Chen, Ruixuan Liu, Yuncheng Wu, and Cuiping Li. 2020. A pufferfish privacy mechanism for monitoring web browsing behavior under temporal correlations.Computers & Security92 (2020), 101754

    2020

  26. [34]

    Changchang Liu, Supriyo Chakraborty, and Prateek Mittal. 2016. Dependence makes you vulnberable: Differential privacy under dependent tuples.. InNDSS, Vol. 16. 21–24

    2016

  27. [35]

    Ashwin Machanavajjhala, Daniel Kifer, John Abowd, Johannes Gehrke, and Lars Vilhuber. 2008. Privacy: Theory meets Practice on the Map. In2008 IEEE 24th International Conference on Data Engineering. 277–286. https://doi.org/10.1109/ ICDE.2008.4497436

    2008

  28. [36]

    Frank McSherry and Kunal Talwar. 2007. Mechanism design via differential privacy. In48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07). IEEE, 94–103

    2007

  29. [37]

    Frank D McSherry. 2009. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. InProceedings of the 2009 ACM SIGMOD International Conference on Management of data. 19–30

    2009

  30. [38]

    Casey Meehan and Kamalika Chaudhuri. 2021. Location trace privacy under con- ditional priors. InInternational Conference on Artificial Intelligence and Statistics. PMLR, 2881–2889

    2021

  31. [39]

    Solomon Messing, Bogdan State, Chaya Nayak, Gary King, and Nate Persily

  32. [40]

    Joel C Miller. 2009. Spread of infectious disease through clustered populations. Journal of the Royal Society Interface6, 41 (2009), 1121–1134

    2009

  33. [41]

    Ilya Mironov. 2017. Rényi differential privacy. In2017 IEEE 30th computer security foundations symposium (CSF). IEEE, 263–275

    2017

  34. [42]

    Alex Pentland and Andrew Liu. 1999. Modeling and prediction of human behavior. Neural computation11, 1 (1999), 229–242

    1999

  35. [43]

    Clément Pierquin, Aurélien Bellet, Marc Tommasi, and Matthieu Boussard. 2024. Rényi pufferfish privacy: General additive noise mechanisms and privacy ampli- fication by iteration via shift reduction lemmas. InInternational Conference on Machine Learning (ICML 2024)

    2024

  36. [44]

    Masoumeh Shafieinejad, Huseyin Inan, Marcello Hasegawa, and Robert Sim

  37. [45]

    Shuang Song and Kamalika Chaudhuri. 2017. Composition properties of infer- ential privacy for time-series data. In2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE, 814–821

    2017

  38. [46]

    Shuang Song, Yizhen Wang, and Kamalika Chaudhuri. 2017. Pufferfish privacy mechanisms for correlated data. InProceedings of the 2017 ACM International Conference on Management of Data. 1291–1306

    2017

  39. [47]

    Apple Differential Privacy Team. 2017. Learning with Privacy at Scale.Apple Machine Learning Journal1, 8 (2017)

    2017

  40. [48]

    Michael Carl Tschantz, Shayak Sen, and Anupam Datta. 2020. SoK: Differential privacy as a causal property. In2020 IEEE Symposium on Security and Privacy (SP). IEEE, 354–371

    2020

  41. [49]

    Stanley L Warner. 1965. Randomized response: A survey technique for eliminat- ing evasive answer bias.Journal of the American statistical association60, 309 (1965), 63–69

    1965

  42. [50]

    Zheng Xu, Yanxiang Zhang, Galen Andrew, Christopher Choquette, Peter Kairouz, Brendan Mcmahan, Jesse Rosenstock, and Yuanbo Zhang. 2023. Feder- ated Learning of Gboard Language Models with Differential Privacy. InProceed- ings of the 61st Annual Meeting of the Association for ...

    2023 doi

  43. [51]

    Bin Yang, Issei Sato, and Hiroshi Nakagawa. 2015. Bayesian differential privacy on correlated data. InProceedings of the 2015 ACM SIGMOD international conference on Management of Data. 747–762

    2015

  44. [52]

    Dingqi Yang, Daqing Zhang, Longbiao Chen, and Bingqing Qu. 2015. Nation- telescope: Monitoring and visualizing large-scale collective behavior in lbsns. Journal of Network and Computer Applications55 (2015), 170–180

    2015

  45. [53]

    Dingqi Yang, Daqing Zhang, and Bingqing Qu. 2016. Participatory cultural mapping based on collective behavior data in location-based social networks. ACM Transactions on Intelligent Systems and Technology (TIST)7, 3 (2016), 1–23

    2016

  46. [54]

    Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, et al. 2021. Opacus: User-friendly differential privacy library in PyTorch.arXiv preprint arXiv:2109.12298(2021)

    2021 arXiv

  47. [55]

    Tao Zhang, Bradley A Malin, Netanel Raviv, and Yevgeniy Vorobeychik. 2025. Differential Confounding Privacy and Inverse Composition. In2025 IEEE Inter- national Symposium on Information Theory (ISIT). IEEE, 1–6

    2025

  48. [56]

    Tao Zhang and Yevgeniy Vorobeychik. 2025. Sliced Rényi Pufferfish Privacy: Directional Additive Noise Mechanism and Private Learning with Gradient Clipping.arXiv preprint arXiv:2512.01115(2025)

    2025

  49. [57]

    1𝑎”,“2𝑎”)|𝑠 1,𝜃) Pr(output is= (“1𝑎

    Wanrong Zhang, Olga Ohrimenko, and Rachel Cummings. 2022. Attribute privacy: Framework and mechanisms. InProceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency. 757–766. Jiamu Bai, Guanlin He, Xin Gu, Daniel Kifer, Kiwan Maeng Table 6: A detailed ...

    2022

  50. [2018]

    InFacebook URL Shares

    URLs Dataset for RFP.pdf. InFacebook URL Shares. Harvard Dataverse. https://doi.org/10.7910/DVN/EIAACS/PMQG9X

    doi

  51. [2021]

    On privacy and confidentiality of communications in organizational graphs.arXiv preprint arXiv:2105.13418(2021)

    2021 arXiv

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.