Calibrating Noise to Sensitivity in Private Data Analysis

• p. 3 Section 1.1, Examples of Sensitivity-Based Analysis

  used noise proportional to the dimension; the new analysis permits noise of size O(1)

• p. 9 Section 3.2, Histograms and Disjoint Analyses

  the noise added in the original framework to each coordinate is O(√d/ϵ)

• p. 3 Examples of Sensitivity-Based Analysis

  used noise proportional to the dimension

• p. 9 Histograms

  the noise added in the original framework to each coordinate is O(

Only the authors can say what is right here.

Judge's note: On p.9 the paper says the earlier framework [6] adds O(√d/ϵ) to each histogram coordinate, a factor of √d in the output dimension d. On p.10 the covariance case (d² queries) gives an O(d) factor, where d is the dimension of v, not of the d²-dimensional output. So the blanket 'proportional to the dimension' in the Introduction does not match the histogram analysis it summarises, unless it means variance or the underlying vector dimension. No statement in the paper resolves this, so the authors need to clarify.

Second check: another model agreed

• p. 15 Proof of Theorem 3

  over ri+1, Z(Dri) is within statistical difference σ of Z(D)

• p. 15 Proof of Theorem 3

  over ri+1, Z(Dri)

• p. 15 Proof of Theorem 3

  Z(Dri) is within statistical difference σ of Z(D)

Only the authors can say what is right here.

Judge's note: On the page 15 image, the preceding sentence identifies Z(D_{r_{i+1}}) as the (i+1)-st hybrid step, and the probability is taken over r_{i+1}. Z(D_{r_i}) does not depend on r_{i+1}, so the subscript is an index slip. Applying Lemma 2 to Z with r = r_{i+1} gives the intended statement, so the theorem stands.

Second check: another model agreed

• p. 16 Proof of Lemma 2

  4∛(12ϵ²2^{−d}), for at least a 1−α fraction of the pairs (r, b)

• p. 15 Lemma 2 statement

  SD (Z(Dr) , Z(D)) ≤ O

• p. 16 Proof of Lemma 2

  for at least a 1−α fraction of the pairs (r, b)

• p. 16 end of Lemma 2 proof

  4∛(12ε²2^{-d})

Only the authors can say what is right here.

Judge's note: Page 16 image. With δ³ = 2ϵ̃²/(α2^d) and ϵ̃ < 2ϵ, 4δ < 4∛(8ϵ²/(α2^d)). The printed δ instead gives 4∛(8αϵ²2^{−d}). Neither matches 4∛(12ϵ²2^{−d}), which has no α and constant 12 rather than 8. Lemma 2's statement (p.15) keeps α, and the proof of Theorem 3 uses σ = O(∛(nϵ²2^{−d})) with α = 1/(6n). The stated lemma therefore stands, and only the last line of the proof is inconsistent.

Second check: another model agreed

• p. 20 Proof of Claim 3, part (1)

  Noting that dH(x1, x2) ≤ k

• p. 20 Proof of Claim 3 part (2)

  not (k, ϵ′)-indistinguishable

• p. 15 Proof of Theorem 3

  over ri+1, Z(Dri)

• p. 20

  Noting that dH(x1, x2) ≤k we get a contradiction

Only the authors can say what is right here.

Judge's note: Page 20 image: part (1) constructs x0 and x1 and compares them in Eqn. (10); no x2 is defined. Part (2) writes ϵ′, but Eqn. (11) and the claim use ϵ. Both are notation slips with an evident intended reading (d_H(x0,x1), ϵ). The Z(D_{r_i}) pointer in this cluster belongs to C022.

Second check: another model agreed

• p. 2 Introduction

  beyond the orignal motivation

• p. 2 Introduction, paragraph on "holistic" functions

  beyond the orignal motivation of a purely statistical

Judge's note: The page 2 crop shows the misspelling in the typeset text, so it is not an extraction artefact.

Second check: none (judge only)

• p. 13 Remark 2 after Theorem 3

  yields O(1/n)-close distributions O(1/n) on neighboring databases

• p. 2 Intro

  beyond the orignal motivation

• p. 7 Non-negligible Leakage

  non-negligible or leakage is inherent

• p. 13

  but yields O(1/n)-close distributions O(1/n) on neighboring databases

Judge's note: All three slips are visible on the page images of pp.13, 2 and 7. None is an extraction artefact. The θ(1) point is handled separately under C018.

Second check: none (judge only)

• p. 3 Section 1.1, Examples of Sensitivity-Based Analysis

  (e.g minimum cut size in a network)

Judge's note: The crop shows 'e.g' with no closing period.

Second check: none (judge only)

• p. 5 Definitional Work

  Evfimievsky et al. [12]

• p. 17 Reference [12]

  Alexandre V. Evfimievski

• p. 5 Related Work, Definitional Work paragraph

  Evfimievsky et al. [12] noted

• p. 17 References, entry [12]

  Alexandre V. Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant

Judge's note: Both spellings are visible in the images, so the paper is internally inconsistent. Which spelling is correct (the reference-list form 'Evfimievski' is the usual one) rests on outside knowledge, but the inconsistency itself is in the files.

Second check: none (judge only)

• p. 5 Definitional Work, k-anonymity paragraph

  isolation [7, 8]) have also been

• p. 5 Related Work, paragraph on k-anonymity and isolation

  tion against isolation [7, 8]) have also been in the eye of privacy research

Judge's note: The crop shows the stray ')' and no '(' earlier in the sentence.

Second check: none (judge only)

• p. 6 Example 1

  the sums f(x) and f(x′) differs by one

Judge's note: The full page 6 image confirms the wording.

Second check: none (judge only)

• p. 7 Non-negligible Leakage paragraph

  non-negligible or leakage is inherent

• p. 7 Non-negligible Leakage paragraph

  However, non-negligible or leakage is inherent

• p. 7

  However, non-negligible or leakage is inherent for

Judge's note: The page 7 image shows the text as quoted.

Second check: none (judge only)

• p. 7 Example 3

  viewed as an real number

Judge's note: The page 7 image confirms the wording.

Second check: none (judge only)

• p. 8 Example 3, continued

  is called a histogram for B1, ..., Bm

• p. 7 Example 3

  joint bins B1, ..., Bd

• p. 8 Example 3

  called a histogram for B1, ..., Bm

• p. 8

  called a histogram for B1, ..., Bm.

Judge's note: Pages 7 and 8 show d bins and f : D^n → Z^d, followed by 'B1,...,Bm'. On p.11, m denotes the number of graph vertices. This is an index slip.

Second check: none (judge only)

• p. 13 Remark 2

  When m = θ(1) this is

Judge's note: The page 13 image shows a lowercase θ. Elsewhere the paper uses capital Ω and O for asymptotic notation. Cosmetic.

Second check: none (judge only)

• p. 13 Theorem 3 statement

  ϵ-indistinguishablenon-interactive

Judge's note: The page 13 image shows the two words run together in the typeset text.

Second check: none (judge only)

• p. 14 Section 4.1, first word

  ”Randomized response” refers

Judge's note: The page 14 image shows ” at the start, whereas the paper uses “ ” correctly elsewhere (e.g. “how many people…”).

Second check: none (judge only)

• p. 14 Proposition 2

  Suppose that San is a ϵ-indistinguishable

Judge's note: The page 14 image confirms 'a ϵ-indistinguishable'. Page 13 writes 'an ϵ-indistinguishable', so this is an inconsistent article. Cosmetic.

Second check: none (judge only)

• p. 15 Proof of Theorem 3

  The ϵ-indistinguishabilityof San

Judge's note: The run-together words are visible on the page 15 image.

Second check: none (judge only)

• p. 15 Proof of Theorem 3, first sentence

  this is close the transcript distribution

Judge's note: Visible on the page 15 image.

Second check: none (judge only)

• p. 20 Proof of Claim 3, part (2)

  assume San is not (k, ϵ′)-indistinguishable

• p. 20 Proof of Claim 3 (2)

  not (k, ϵ′)-indistinguishable

Judge's note: I checked the page image p020 and crop C031-a. Claim 3 states that a mechanism is (k, ϵ)-indistinguishable iff it is (k, ϵ)-semantically-secure, so both sides use the same ϵ. Part (2) assumes the mechanism is not (k, ϵ′)-indistinguishable, but the condition that follows, Eqn. (11) |ln(...)| > ϵ, uses ϵ. So does the bound in (13), ln(1−α+αe^ϵ). The text layer has only this one occurrence of ϵ′, and it is not defined anywhere. This is a notational typo with an evident fix (ϵ′ → ϵ), and the proof's logic is unaffected.

Second check: none (judge only)