{"id":"e2d89d79-7225-4ba8-9852-ed4593acb381","arxiv_id":"2501.12893","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For counting queries on databases with independent entries, the paper derives exact privacy curves for pure statistical privacy, subsampling, and additive noise, and shows that the data distribution's entropy can sharply reduce privacy loss relative to differential privacy.","lead":"This paper analyzes 'statistical privacy', in which an adversary knows only the distribution that generated a database, and derives exact formulas for how much private information leaks through counting queries. It shows that this more realistic threat model can provide much better privacy with less noise than differential privacy, which assumes an adversary who knows almost everything.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's printed positive threshold caps at the mean instead of the sample size, so the stated subsampling privacy curve is not the δ of Definition 5.","rationale":"The paper's central claim is that exact privacy curves can be computed for property queries in the statistical privacy setting. The independence assumption is explicit and is a scope limitation rather than an internal inconsistency, so I do not treat it as the most load-bearing objection. The concrete threat is Theorem 1 as printed: its capped threshold is inconsistent with the derivation in the same section. Because Theorem 1 is the main technical result for subsampling, and subsampling is one of the paper's primary mechanisms, a reader cannot verify the advertised privacy amplification from the stated formula. This is an internal error, not a disagreement with consensus. The reader noted the threshold error in the rationale but made the independence assumption the stated weakest point; hence partial agreement. Lemma 6's Gaussian formulas are also approximate and weaken the abstract's 'exact formulas' claim, but that is secondary to the incorrectly stated subsampling theorem. The correct cap follows from the prior derivation, so the issue is fixable, and the existing CONDITIONAL verdict remains appropriate.","tokens_in":16647,"tokens_out":24920,"duration_ms":252587,"concrete_test":"Instantiate the two thresholds for n=1000, λ=0.1, π_F=0.5, ε=0.01. The definition-derived threshold is min{100, 1000·0.5·(0.1+R/D)} ≈52.5; Theorem 1's printed threshold is 1000·0.5·min{0.1,0.105}≈50. Compute S_j = Prµ+(j) − e^εPrµ-(j) and compare Σ_{j>52} S_j with Σ_{j>50} S_j. The latter includes j=51,52 with Q_+(j)<e^ε, so the two sums differ and the printed sum is not the δ_+(ε) of Equation (3). This directly checks whether the printed cap is wrong.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.1 defines the positive threshold correctly as j*_+ = min{m, (1+γ*_+)π_F m} with γ*_+ = λ^{-1}(e^ε−1)/(1+e^ε π_F/(1−π_F)), i.e. j*_+ = min{λn, nπ_F(λ+R/D)} with R=(e^ε−1)/(1+e^ε π_F/(1−π_F)) and D=1. Theorem 1 instead prints j*_+ = nπ_F·min{λ, λ+R/D}. Since R/D>0 for ε>0, the printed value is always nπ_F λ, the mean of the subsample count, not the upper-tail crossing point. The subsequent sum over j>j*_+ then includes values j for which Q_+(j)<e^ε, producing an expression that is not equal to the privacy curve of Definition 5; depending on parameters the printed sum can be smaller than the true δ or even negative, while the curve is nonnegative. The derivation immediately before the theorem supports the corrected cap, so the central 'exact formula' for subsampling is misstated as printed.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":66,"tokens_out":13722,"duration_ms":138492,"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":[{"comment":"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.","section":"§4.1, Theorem 1"},{"comment":"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 ε.","section":"§4.1 and §4.2"}],"minor_comments":[{"comment":"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.","section":"§4.1, Theorem 1"},{"comment":"The summation limits involving j⋆+ and j⋆− should be written as ceilings and floors, respectively; the current rendering (\"l j⋆ + m\") is confusing.","section":"§4.1, Theorem 1"},{"comment":"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.","section":"§5"},{"comment":"There are minor typos, e.g. 'x-achses' should be 'x-axes' and 'independend' should be 'independent'.","section":"§5"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nSmaller 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.\n\nBottom 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.","headline":"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.","tokens_in":17360,"tokens_out":3528,"would_cite":false,"duration_ms":35772,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["statistical privacy","differential privacy","property queries","privacy curve","subsampling","Laplace noise","Gaussian noise","utility loss"],"falsifier":"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.","tokens_in":16427,"feed_emoji":"🔒","tokens_out":9991,"duration_ms":91889,"temperature":0.7,"pith_summary":"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.","feed_headline":"Exact formulas show entropy alone can guarantee privacy","feed_subtitle":"For property queries, a database distribution's own randomness buys strong privacy when the attacker lacks exact entries.","key_machinery":"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)$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces privacy profiles and the subsampling amplification bound used as the differential-privacy comparison baseline.","marker":"[2]"},{"why":"Defines noiseless privacy, the pure-setting model against which the paper positions its statistical privacy.","marker":"[4]"},{"why":"Introduces distributional differential privacy, the closest prior model from which the paper's direct conditional-distribution comparison differs.","marker":"[3]"},{"why":"Defines differential privacy with partial knowledge, the background-knowledge model that motivates statistical privacy.","marker":"[6]"},{"why":"Supplies the Laplace noise mechanism and the sensitivity calibration used as the differential-privacy baseline.","marker":"[8]"},{"why":"States the differential-privacy worst-case definition and foundations that the paper argues are overly pessimistic.","marker":"[9]"},{"why":"Defines the privacy loss random variable used to construct the privacy curve.","marker":"[15]"}],"fun_headline_variants":["Exact formulas quantify entropy as a privacy shield","Entropy alone yields tight exponential privacy bounds","Statistical privacy: when distribution knowledge suffices","For property queries, entropy sets exact privacy curves"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Exact formulas quantify entropy as a privacy shield","Entropy alone yields tight exponential privacy bounds","Statistical privacy: when distribution knowledge suffices","For property queries, entropy sets exact privacy curves"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000191,"raw_usage":{"total_tokens":1338,"prompt_tokens":932,"completion_tokens":406,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":548,"completion_tokens_details":{"reasoning_tokens":349}},"tokens_in":548,"tokens_out":406,"duration_ms":5169,"temperature":1.0,"reasoning_tokens":349,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T16:40:57.339699+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces privacy profiles and the subsampling amplification bound used as the differential-privacy comparison baseline."},{"cited_title":"In: Proc","cited_arxiv_id":null,"evidence_quote":"Defines noiseless privacy, the pure-setting model against which the paper positions its statistical privacy."},{"cited_title":"In: Proc","cited_arxiv_id":null,"evidence_quote":"Introduces distributional differential privacy, the closest prior model from which the paper's direct conditional-distribution comparison differs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines differential privacy with partial knowledge, the background-knowledge model that motivates statistical privacy."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Laplace noise mechanism and the sensitivity calibration used as the differential-privacy baseline."}],"review_version":1}