Statistical Privacy

Dennis Breutigam; R\"udiger Reischuk

REVIEW 2 major objections 4 minor 17 references

Statistical Privacy

T0 review · 2 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read For property queries, this paper derives exact formulas for the statistical-privacy curve, showing that the entropy of the database distribution alone can guarantee strong privacy when the attacker knows the distribution but not the…

desk verdict The distributional-privacy curves for property queries are a useful contribution, but Theorem 1's threshold is misprinted and the 'exact formulas' claim needs a repair. read the letter →

arxiv 2501.12893 v2 pith:W5L2U4HM submitted 2025-01-22 cs.CR

Dennis Breutigam , Rüdiger Reischuk This is my paper · ORCID

classification cs.CR

keywords statisticalprivacydifferentialpropertyqueriescurvesubsamplingLaplacenoiseGaussianutilityloss

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 studies statistical privacy, a middle ground between releasing data unprotected and differential privacy's worst-case assumption that an attacker knows almost every entry. In this model the attacker knows the distribution that generated the database but not which entries it contains, and the paper asks how much privacy that residual uncertainty buys. For counting queries that ask what fraction of entries satisfy a property, it derives exact formulas for the privacy curve $\delta(\varepsilon)$ that compares the output distribution when one targeted entry is positive versus negative. The formulas show that database entropy alone provides meaningful privacy, and that the guarantee degrades only when the property probability $\pi$ is very close to $0$ or $1$. The paper also quantifies how subsampling and Laplace or Gaussian noise amplify privacy, what utility they cost, and how much smaller the resulting $\delta$ is than in differential privacy.

What carries the argument

The load-bearing object is the privacy curve $\delta_{\nu_1,\nu_2}(\varepsilon)$, built from the privacy loss random variable $L(z)=\ln(\nu_1(z)/\nu_2(z))$; it gives the smallest $\delta$ for which two conditional output distributions are $(\varepsilon,\delta)$-indistinguishable. For a property query the two distributions are $\mu_+$, where the critical entry satisfies the property, and $\mu_-$, where it does not. Under the paper's independence and common-probability assumptions the number of positive entries is binomial, so the likelihood ratio $Q_+(j)$ becomes a rational function of $j$ and $\pi$, and the thresholds where $Q_+(j)=e^\varepsilon$ are solved explicitly. That explicit threshold calculation, together with the entropy bound $nH(\pi)$, is what carries the exact formulas for $\delta(\varepsilon)$.

What would settle it

Compute the true statistical-privacy $\delta(\varepsilon)$ for a property query on a database of size $n=1000$ whose entries are generated by a positively correlated two-state Markov chain with $\pi=0.5$; if for some $\varepsilon>0$ the value falls below the paper's Theorem 2 formula, the independence assumption on which the exact formulas rest is falsified.

Watch

Extended reading notes

Core claim

The central claim is that exact statistical-privacy curves can be computed for property queries. Theorem 2 states that when entries are independent and each satisfies the property with probability $\pi$, pure statistical privacy has $\delta(\varepsilon)=\max\{\delta_+(\varepsilon),\delta_-(\varepsilon)\}$, given by explicit binomial sums with thresholds $j_+^\star$ and $j_-^\star$. Theorem 1 extends the same structure to subsampling with rate $\lambda$, replacing $n$ by $n\lambda$ in the formulas. Because the thresholds sit a constant fraction away from the binomial mean, Chernoff's bound makes $\delta(\varepsilon)$ decrease exponentially in $n$; for small $\varepsilon$ the dependence is roughly exponential in $\varepsilon^2$. The paper's numerical computations conclude that, for the same $\varepsilon$, statistical privacy gives much smaller $\delta$ than differential privacy except for very small or very large $\pi$, and that Gaussian noise and subsampling at matched utility loss perform nearly identically while Laplace noise is noticeably worse.

Load-bearing premise

The exact privacy curves and the entropy bound $nH(\pi)$ rest on the assumption that all database entries are independent and each satisfies the queried property with the same probability $\pi$; with correlated entries or entry-dependent probabilities, the binomial formulas no longer apply.

Editorial extensions

If this is right

For a fixed $\varepsilon$, statistical privacy yields a substantially smaller $\delta$ than differential privacy on the same property query, except when $\pi$ is very close to $0$ or $1$ where the database entropy nearly vanishes.
The privacy parameter $\delta$ shrinks exponentially in the database size $n$; equivalently, increasing $n$ by a factor $\beta$ lowers the achievable $\varepsilon$ by roughly $\sqrt{\beta}$ at the same $\delta$.
Subsampling with rate $\lambda$ and Gaussian noise chosen to match the same utility loss produce nearly identical $\delta$-values in the paper's numerical comparisons, while Laplace noise at the same utility loss is about 20% worse.
Rare properties, such as a 1% disease rate, have weak statistical privacy on their own, so external noise matters most there; heavy noise, however, destroys utility.
The exact formulas give practitioners a direct way to choose a mechanism's noise scale or sample size to hit a target privacy level, a step the paper argues is needed to apply privacy-enhancing techniques in practice.

Reading between the lines

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

A natural next step is to relax the identical-probability assumption to entry-dependent probabilities $\pi_j$; the formulas would then depend on the variance of the weighted sum of independent Bernoulli variables rather than on $n\pi(1-\pi)$, and this is not tested in the paper.
The paper's conjecture that subsampling never increases $\delta$ for property queries, if proved, would give a clean analogue of the differential-privacy amplification theorem; the paper only supports it with a few plotted parameter settings.
The close numerical match between Gaussian noise and subsampling at equal utility loss suggests that, for small $\varepsilon$, privacy amplification is governed mainly by the variance of the released estimator rather than by the specific mechanism family; uniform or other mean-zero noise could be tested to see whether the pattern persists.

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.

Desk Editor's Note

read the letter

Quick take on arXiv:2501.12893. The paper gives explicit privacy curves for property queries when the adversary knows the generative distribution but not the rows. That is genuinely useful: differential privacy's worst-case adversary is often too pessimistic, and this distributional setting is concrete enough to compute with. The binomial derivations for the pure and subsampling cases are coherent, the utility-loss comparisons are sensible, and the plots give a practical sense of how much entropy buys you. The paper also positions itself cleanly relative to noiseless privacy and distributional differential privacy rather than overselling novelty.

The soft spot is real and specific. Theorem 1's printed positive threshold is j*_+ = n*pi_F*min{lambda, lambda+R}, where R=(e^eps-1)/(1+e^eps*pi_F/(1-pi_F)). Since R>0, the min is always lambda, so j*_+ collapses to the mean n*pi_F*lambda. The derivation just before the theorem defines j*_+ as (1+gamma**_+)*pi_F*m with the cap at m=n*lambda, which gives min{n*lambda, n*pi_F*(lambda+R)}. The first term in the printed min should be n*lambda, not n*pi_F*lambda. So the "exact" subsampling curve in Theorem 1 is misstated whenever the upper crossing exceeds the sample size, and the subsequent sum is then not the delta of Definition 5. This is a load-bearing typo, not cosmetic, because the abstract claims exact formulas and Section 4.1 is built around that formula.

Smaller issues: the Gaussian bounds in Lemma 6 are approximations with no error bounds, and the paper's own text says "approximated" and "no simple analytical formula," so the abstract overstates coverage. The independence and equal-probability assumption is structural and stated, which is fine as a modeling restriction, but it should be flagged prominently when the curves are used. The end conjecture is clearly labeled.

Bottom line: the conceptual contribution is solid and most derivations are careful, but Theorem 1 as printed is wrong. If the cap is fixed, the paper deserves serious referee time. I would send it to review with the expectation that the authors repair Theorem 1 and soften "exact" to "explicit, with numerical approximation where noted." I would not cite the formula in its current form.

Referee Report

2 major / 4 minor

Summary. This paper introduces 'statistical privacy' as a distributional alternative to differential privacy: the adversary knows the data-generating distribution but not the realized entries. For symmetric property queries on n independent entries with a common positive probability π, the authors derive closed-form expressions for the privacy curve δ(ε), analyze the privacy amplification and utility loss of subsampling, and give approximate bounds for additive Laplace and Gaussian noise. They compare the resulting parameters with differential privacy numerically and conclude that the entropy of the database distribution provides substantial privacy amplification except when π is very close to 0 or 1.

Significance. The question addressed here is well motivated, and the i.i.d./equal-π setting is analyzed with care. The explicit binomial formulas for the pure and subsampled cases are concrete and checkable, the utility-loss comparison between subsampling and noise is a useful contribution, and the paper is transparent about the main restrictions: independence and identical π are stated where used, and the noise bounds are explicitly approximate. The central claim is, however, not yet correct as printed: Theorem 1 contains a load-bearing error in the capped threshold j⋆+, so the stated subsampling privacy curve is not the δ of Definition 5. The derivation immediately preceding the theorem supplies the missing cap, so the error is fixable, but the present text does not deliver the 'exact formula' promised in the abstract.

major comments (2)

[§4.1, Theorem 1] The displayed threshold j⋆+ = min{λ, λ + (e^ε − 1)/(1 + e^ε π_F/(1 − π_F))} · n π_F is incorrect. Since the second argument of the min is always larger than λ, the printed j⋆+ is always n π_F λ, i.e. the expected number of positive elements in the subsample. The derivation just before the theorem gives the correct cap j⋆+ = min{n λ, n π_F (λ + (e^ε − 1)/(1 + e^ε π_F/(1 − π_F)))}, equivalently min{m, (1 + γ⋆+) π_F m} with m = n λ. With the printed formula, the sum defining δ+(ε) includes indices j for which Q+(j) ≤ e^ε, so the expression is not δ_{F,SAMP,μ+,μ−}(ε) from Definition 5 and may be smaller than the true privacy-loss value or even negative. Because Theorem 1 is the paper's central exact formula for subsampling, this error must be corrected.
[§4.1 and §4.2] The exactness claim in the abstract should be qualified: the exact formulas hold for the pure and subsampling privacy curves under the stated independence and identical-π assumptions, while the Gaussian and Laplace results of §4.3 are approximate (Lemma 6 uses '≈'). In particular, Theorem 2 is stated only for ε ≤ ln 2, and this restriction is essential for the printed pure-curve thresholds; the abstract and conclusion should not suggest that unconditional exact formulas are obtained for all noise mechanisms and all ε.

minor comments (4)

[§4.1, Theorem 1] The paper should state explicitly that λ n is assumed to be an integer, since the formulas use binomial coefficients (n λ − 1 choose j); otherwise the summation bounds need floor and ceiling functions.
[§4.1, Theorem 1] The summation limits involving j⋆+ and j⋆− should be written as ceilings and floors, respectively; the current rendering ("l j⋆ + m") is confusing.
[§5] The numerical comparisons are not fully reproducible: the text reports Mathematica computations but does not give all parameter values, the number of terms used in the sums, or the code/data; adding this would strengthen the empirical claims.
[§5] There are minor typos, e.g. 'x-achses' should be 'x-axes' and 'independend' should be 'independent'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the privacy curves are derived directly from the paper's stated binomial model and definitions, not from fitted values or self-citations.

full rationale

The derivation chain is self-contained. Definition 4 defines statistical privacy by comparing conditional distributions, and Definition 5 defines the privacy curve directly from the same conditional likelihood ratio; Lemma 2 is a rewriting of the max-over-sets condition as the integral in (3), not a result that presupposes the target formulas. Theorems 1 and 2 are obtained by substituting the binomial marginal distributions that follow from the paper's explicit independence and common-pi assumption into that integral, so no parameter is fitted to data and no external benchmark is used as an input. The cited works on differential privacy, subsampling, and distributional privacy are contextual and comparative, not load-bearing for the algebraic derivation of the formulas. The apparent issue in the printed threshold j*_+ in Theorem 1, which caps at the mean n*pi*lambda rather than at the crossing point of Q_+(j)=e^epsilon, is a correctness or typographical concern about the stated formula, not a circularity: it does not make the result equivalent to its inputs by construction. The independence and equal-pi assumptions are strong and limit the setting, but they are declared assumptions rather than conclusions smuggled from the target result.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central formulas are derived from the binomial distribution that follows from independent entries with identical property probability. No parameters are fitted; π, n, λ, ψ are inputs. The main structural assumptions are independence, identical π, and the restriction to single symmetric property queries.

assumptions (6)

domain assumption The entries of the database are independent.
Section 2: 'In many cases it is still realistic to assume that the entries are independent which will be assumed in the following.' All binomial formulas and the entropy bounds nH(π) rely on this.
domain assumption For the explicit formulas, every entry has the same probability π of fulfilling the property.
Section 4, start: 'To keep the mathematical formulas manageable we restrict the analysis to the case that the probability π for fulfilling the property is identical for all entries.' Theorems 1, 2 and Lemmas 4-10 use identical π.
domain assumption The adversary knows the exact generating distribution µ and only that (plus the query answer).
Definition 4 and Section 1: statistical privacy assumes the adversary has 'passive partial knowledge' and knows the distribution. If the adversary has additional side information, the entropy is reduced.
domain assumption Queries are symmetric functions of the entries; property queries are counting queries.
Section 2 restricts to symmetric functions to avoid revealing single entries. The analysis is for property queries only.
domain assumption The analysis is restricted to single queries, not composition.
Section 2: 'This paper is restricted to the case of single queries. Composition in the statistical setting is even more complex...' All theorems treat a single query.
domain assumption For Gaussian noise, the binomial distribution of the query is approximated by a normal distribution.
Lemma 6 uses 'for larger n the binomial distribution can be approximated by the Gaussian distribution' without quantified error bounds. The δ formulas in Lemma 6 and 10 are approximate.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Statistical Privacy." pith.science (2026). https://pith.science/paper/W5L2U4HM

@misc{pith2026250112893,
  author       = {Pith},
  title        = {Pith review of: Statistical Privacy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/W5L2U4HM}},
  note         = {Machine review of arXiv:2501.12893}
}

read the original abstract

To analyze the privacy guarantee of personal data in a database that is subject to queries it is necessary to model the prior knowledge of a possible attacker. Differential privacy considers a worst-case scenario where he knows almost everything, which in many applications is unrealistic and requires a large utility loss. This paper considers a situation called statistical privacy where an adversary knows the distribution by which the database is generated, but no exact data of all (or sufficient many) of its entries. We analyze in detail how the entropy of the distribution guarantes privacy for a large class of queries called property queries. Exact formulas are obtained for the privacy parameters. We analyze how they depend on the probability that an entry fulfills the property under investigation. These formulas turn out to be lengthy, but can be used for tight numerical approximations of the privacy parameters. Such estimations are necessary for applying privacy enhancing techniques in practice. For this statistical setting we further investigate the effect of adding noise or applying subsampling and the privacy utility tradeoff. The dependencies on the parameters are illustrated in detail by a series of plots. Finally, these results are compared to the differential privacy model.

Figures

Figures reproduced from arXiv: 2501.12893 by the authors.

**Figure 3.** δ parameter with respect to π for noise levels ν1 = 1 and ν2 = 3 [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗

**Figure 6.** The ratio of the δ parameters for DP versus SP für n = 100 [PITH_FULL_IMAGE:figures/full_fig_p019_6.png] view at source ↗

Figures from the paper (1 more)

**Figure 7.** Figure 7: Results for n = 1000, π = 0.5 and ε = 0.1 the blue curve gives the δ-values for subsampling a database of size n for ε ′ = log(1 + λ(e ε − 1)); note that δ increases when decreasing λ up to a certain point because ε ′ gets smaller, the yellow curve shows the values fo…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 14 canonical work pages

[1]

In: Proc

Abadi, M., Chu, A., Goodfellow, I., McMahan, H., Mironov, I., Talwar, K., Zhang, L.: Deep learning with differential privacy. In: Proc. ACM CC. pp. 308–318 (2016)

work page 2016
[2]

Balle, B., Barthe, G., Gaboardi, M.: Privacy profiles and amplification by subsam- pling. J. Privacy and Confidentiality10(1) (2020). https://doi.org/10.29012/ jpc.726

work page 2020
[3]

In: Proc

Bassily, R., Groce, A., Katz, J., Smith, A.: Coupled-worlds privacy: Exploiting adversarial uncertainty in statistical data privacy. In: Proc. 54. FOCS. p. 439–448 (2013). https://doi.org/10.1109/FOCS.2013.54

work page doi:10.1109/focs.2013.54 2013
[4]

In: Proc

Bhaskar, R., Bhowmick, A., Goyal, V., Laxman, S., Thakurta, A.: Noiseless database privacy. In: Proc. ASIACRYPT 2011. pp. 215–232. Springer LNCS 7073 (2011)

work page 2011
[5]

https://desfontain.es/blog/real-world-differential-privacy.html (2021)

Desfontaines, D.: A list of real-world uses of differential privacy. https://desfontain.es/blog/real-world-differential-privacy.html (2021)

work page 2021
[6]

Desfontaines, D., Mohammadi, E., Krahmer, E., Basin, D.: Differential privacy with partial knowledge (2020)

work page 2020
[7]

Desfontaines, D., Pejo, B.: Sok: Differential privacies – a taxonomy of differential privacy variants and extensions (2022)

work page 2022
[8]

Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. J. Privacy and Confidentiality3, 17–51 (2016)

work page 2016

Show all 17 references

[9]

Foun- dations and Trends® in Theoretical Computer Science 9(3–4), 211–407 (2014)

Dwork, C., Roth, A.: The algorithmic foundations of differential privacy. Foun- dations and Trends® in Theoretical Computer Science 9(3–4), 211–407 (2014). https://doi.org/10.1561/0400000042

2014 doi
[10]

In: Proc

Imola, I., Chaudhuri, K.: Privacy amplification via Bernoulli sampling. In: Proc. 38. Int. Conf. on Machine Learning (2021)

2021
[11]

https://www.nist.gov/blogs/cybersecurity-insights/differential-privacy-future- work-open-challenges (1 2022), an official website of the United States government

Joseph, N., David, D.: Differential privacy: Future work & open challenges. https://www.nist.gov/blogs/cybersecurity-insights/differential-privacy-future- work-open-challenges (1 2022), an official website of the United States government

2022
[12]

Kifer, D., Lin, B.: An axiomatic view of statistical privacy and utility. J. Privacy and Confidentiality 4, 5–49 (2012)

2012
[13]

Cryptol- ogy ePrint Archive (2018)

Meiser, S.: Approximate and probabilistic differential privacy definitions. Cryptol- ogy ePrint Archive (2018)

2018
[14]

Mironov,I.:Renyidifferentialprivacy.In:Proc.30.ComputerSecurityFoundations Symposium (2017)

2017
[15]

In: Proc

Sommer, D., Meiser, S., Mohammadi, E.: Privacy loss classes: The central limit the- orem in differential privacy. In: Proc. Privacy Enhancing Technologies Symposium. vol. 2019 (2), pp. 245–269 (2019).https://doi.org/10.2478/popets-2019-0029

2019 doi
[16]

In: arXiv:2210.00597 (2022)

Steinke, T.: Composition of differential privacy and privacy amplification by sub- sampling. In: arXiv:2210.00597 (2022)

2022 arXiv
[17]

In: Proc

Wang, Y., Balle, B., Kasiviswanathan, S.: Subsampled Renyi differential privacy and analytical moments accountant. In: Proc. 22. AISTATS (2019)

2019

Pith tools

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

[1] [1]

In: Proc

Abadi, M., Chu, A., Goodfellow, I., McMahan, H., Mironov, I., Talwar, K., Zhang, L.: Deep learning with differential privacy. In: Proc. ACM CC. pp. 308–318 (2016)

work page 2016

[2] [2]

Balle, B., Barthe, G., Gaboardi, M.: Privacy profiles and amplification by subsam- pling. J. Privacy and Confidentiality10(1) (2020). https://doi.org/10.29012/ jpc.726

work page 2020

[3] [3]

In: Proc

Bassily, R., Groce, A., Katz, J., Smith, A.: Coupled-worlds privacy: Exploiting adversarial uncertainty in statistical data privacy. In: Proc. 54. FOCS. p. 439–448 (2013). https://doi.org/10.1109/FOCS.2013.54

work page doi:10.1109/focs.2013.54 2013

[4] [4]

In: Proc

Bhaskar, R., Bhowmick, A., Goyal, V., Laxman, S., Thakurta, A.: Noiseless database privacy. In: Proc. ASIACRYPT 2011. pp. 215–232. Springer LNCS 7073 (2011)

work page 2011

[5] [5]

https://desfontain.es/blog/real-world-differential-privacy.html (2021)

Desfontaines, D.: A list of real-world uses of differential privacy. https://desfontain.es/blog/real-world-differential-privacy.html (2021)

work page 2021

[6] [6]

Desfontaines, D., Mohammadi, E., Krahmer, E., Basin, D.: Differential privacy with partial knowledge (2020)

work page 2020

[7] [7]

Desfontaines, D., Pejo, B.: Sok: Differential privacies – a taxonomy of differential privacy variants and extensions (2022)

work page 2022

[8] [8]

Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. J. Privacy and Confidentiality3, 17–51 (2016)

work page 2016